ARC075 - C

C - Bugged

問題ページ

DP で解いた．editorial 曰くオーバーキルらしい．

• 後ろ向きに iteration を回すことで空間計算量を落とす一般的なテク
• j % 10 == 0 の場合のスキップを忘れない

このあたりに注意した．

int main() {
 
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int N;
    cin >> N;
 
    vector<bool> dp(11111, false);
    dp[0] = true;
 
    for (int i = 0; i < N; i++) {
        int s; cin >> s;
        for (int j = 10000; j >= 0; j--) {
            if (dp[j]) dp[j + s] = true;
        }
    }
 
    for (int j = 10000; j >= 0; j--) {
        if (dp[j] && j % 10) {
            cout << j << endl;
            return 0;
        }
    }
    cout << 0 << endl;
 
    return 0;
}

Submission #2529596 - AtCoder Regular Contest 075