結果

提出番号 2198
提出者 shibh308
言語 C++
提出日時 2019-02-05 11:00:35
問題名 (18)おまんじゅうわけわけ
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 2ms 8464KB
2 AC 100% 2ms 8336KB
3 AC 100% 2ms 8144KB
4 AC 100% 27ms 7872KB
5 AC 100% 27ms 8160KB
6 AC 100% 23ms 8400KB
7 AC 100% 27ms 7888KB
8 AC 100% 23ms 8160KB
9 AC 100% 26ms 7872KB

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e18+7;

signed main(){
    int n;
    cin >> n;
    vector<int> dp(3, -MOD);
    dp[0] = 0;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        vector<int> nex(3, -MOD);
        for(int j = 0; j < 3; ++j)
            if(dp[j] != -MOD){
                nex[j] = max(nex[j], dp[j]);
                nex[(j + x) % 3] = max(nex[(j + x) % 3], dp[j] + x);
            }
        dp = move(nex);
    }
    cout << (dp[0] ? dp[0] : -1) << endl;
}