Submission #1366211


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    int N;
    cin >> N;
    vector<i64> A(N);
    vector<char> op(N);
    op[0]='+';
    cin >> A[0];
    rep(i,1,N) cin >> op[i] >> A[i];

    static i64 memo[100001][3];
    static bool done[100001][3];
    fill_n((i64*)memo,100001*3,-inf64);
    fill_n((bool*)done,100001*3,false);
    function<i64(int,int)> rec=[&](int i,int j){
        auto &res=memo[i][j];
        if(done[i][j]) return res;
        done[i][j]=true;
        if(i==N) return res=0;
        int s=op[i]=='-';
        rep(j_,0,j+1){
            res=max(res,((j_+s)%2==0?1:-1)*A[i]+rec(i+1,j_));
            if(s) res=max(res,((j_+s)%2==0?1:-1)*A[i]+rec(i+1,(j_+1==3?1:j_+1)));
        }
        return res;
    };
    cout << rec(0,0) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Submission Info

Submission Time
Task E - Addition and Subtraction Hard
User walkre
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1496 Byte
Status AC
Exec Time 29 ms
Memory 16384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 29
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_alladd_01.txt, subtask_1_alladd_02.txt, subtask_1_alladd_03.txt, subtask_1_alladd_04.txt, subtask_1_allsub_01.txt, subtask_1_allsub_02.txt, subtask_1_allsub_03.txt, subtask_1_allsub_04.txt, subtask_1_cont_01.txt, subtask_1_cont_02.txt, subtask_1_cont_03.txt, subtask_1_cont_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_killer_03.txt, subtask_1_killer_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_max_03.txt, subtask_1_max_04.txt, subtask_1_min_01.txt, subtask_1_min_02.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt, subtask_1_rand_04.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2944 KB
sample_02.txt AC 2 ms 2944 KB
sample_03.txt AC 2 ms 2944 KB
subtask_1_alladd_01.txt AC 21 ms 16256 KB
subtask_1_alladd_02.txt AC 21 ms 16256 KB
subtask_1_alladd_03.txt AC 21 ms 16256 KB
subtask_1_alladd_04.txt AC 21 ms 16384 KB
subtask_1_allsub_01.txt AC 29 ms 16256 KB
subtask_1_allsub_02.txt AC 29 ms 16256 KB
subtask_1_allsub_03.txt AC 29 ms 16256 KB
subtask_1_allsub_04.txt AC 29 ms 16256 KB
subtask_1_cont_01.txt AC 16 ms 10112 KB
subtask_1_cont_02.txt AC 12 ms 8320 KB
subtask_1_cont_03.txt AC 11 ms 7424 KB
subtask_1_cont_04.txt AC 4 ms 3968 KB
subtask_1_killer_01.txt AC 24 ms 15360 KB
subtask_1_killer_02.txt AC 17 ms 11520 KB
subtask_1_killer_03.txt AC 24 ms 15744 KB
subtask_1_killer_04.txt AC 17 ms 11648 KB
subtask_1_max_01.txt AC 27 ms 16256 KB
subtask_1_max_02.txt AC 27 ms 16256 KB
subtask_1_max_03.txt AC 27 ms 16256 KB
subtask_1_max_04.txt AC 27 ms 16256 KB
subtask_1_min_01.txt AC 2 ms 2944 KB
subtask_1_min_02.txt AC 2 ms 2944 KB
subtask_1_rand_01.txt AC 18 ms 11008 KB
subtask_1_rand_02.txt AC 20 ms 12544 KB
subtask_1_rand_03.txt AC 5 ms 4096 KB
subtask_1_rand_04.txt AC 10 ms 6912 KB