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 |
|
|
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 |