Submission #19724139

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
using vec_int = vector<int>;
using P = pair<int,int>;
using T = tuple<int,int,int>;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

signed main(){
    int N; cin>>N;
    vec_int a(N); rep(i,N)cin>>a.at(i);

    vec_int DP(N+1, -1000000000);
    DP.at(0) = 0;

    for(int i=0;i<N;i++){
        DP.at(i+1) = max(DP.at(i+1), DP.at(i)); //i+1に何もおかなかったとき
        // i+1においてかつ、i+2+3j, i+3+3kに置いたとき
        int pos = i+2;
        while(pos<N){
            int max_val = -1000;
            int pos2 = i+1;
            while(pos2<pos){
                max_val = max(a.at(pos2), max_val);
                pos2 += 3;
            }
            DP.at(pos+1) = max(DP.at(pos+1), a.at(i)+max_val+a.at(pos));
            pos+=3;
        }
    }
    cout<<DP.at(N)<<endl;


    return 0;
}

Submission Info

Judge Result