Submission #1366207
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=1e15; 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 | 0 |
Code Size | 1464 Byte |
Status | WA |
Exec Time | 27 ms |
Memory | 14720 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 20 ms | 14720 KB |
subtask_1_alladd_02.txt | AC | 20 ms | 14720 KB |
subtask_1_alladd_03.txt | AC | 20 ms | 14720 KB |
subtask_1_alladd_04.txt | AC | 20 ms | 14720 KB |
subtask_1_allsub_01.txt | AC | 26 ms | 14720 KB |
subtask_1_allsub_02.txt | AC | 27 ms | 14720 KB |
subtask_1_allsub_03.txt | AC | 27 ms | 14720 KB |
subtask_1_allsub_04.txt | AC | 27 ms | 14720 KB |
subtask_1_cont_01.txt | AC | 15 ms | 9344 KB |
subtask_1_cont_02.txt | AC | 12 ms | 7680 KB |
subtask_1_cont_03.txt | AC | 10 ms | 6912 KB |
subtask_1_cont_04.txt | AC | 4 ms | 3840 KB |
subtask_1_killer_01.txt | WA | 23 ms | 13952 KB |
subtask_1_killer_02.txt | WA | 17 ms | 10624 KB |
subtask_1_killer_03.txt | WA | 24 ms | 14208 KB |
subtask_1_killer_04.txt | WA | 17 ms | 10624 KB |
subtask_1_max_01.txt | WA | 26 ms | 14720 KB |
subtask_1_max_02.txt | WA | 26 ms | 14720 KB |
subtask_1_max_03.txt | WA | 26 ms | 14720 KB |
subtask_1_max_04.txt | WA | 26 ms | 14720 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 | WA | 16 ms | 10112 KB |
subtask_1_rand_02.txt | WA | 19 ms | 11392 KB |
subtask_1_rand_03.txt | WA | 5 ms | 3968 KB |
subtask_1_rand_04.txt | WA | 9 ms | 6400 KB |