Submission #1072791
Source Code Expand
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
#define MAXN 100000
#define INF 1000000000000000000LL
using namespace std;
//(i+j)=(i^j)+2*(i&j)
//(i+j)=(i&j)+(i|j)
//(i|j)=(i^j)+(i&j)
struct node
{
bool is_add;
int num;
}a[MAXN+80];
int n;
long long dp[MAXN+80][2];//0 min 1 max
long long DP(int s,bool f)
{
if((f&&dp[s][f]>-INF/2)||((!f)&&dp[s][f]<INF/2))
return dp[s][f];
if(s==n)
return dp[s][0]=dp[s][1]=(a[s].is_add?1:(-1))*a[s].num;
int i;
long long S=a[s].num;
for(i=s+1;i<=n;i++)
{
dp[s][0]=min(dp[s][0],(f?1:(-1))*S+DP(i,0));
dp[s][1]=max(dp[s][1],(f?1:(-1))*S+DP(i,1));
if(f==0)
{
dp[s][0]=min(dp[s][0],-S-DP(i,1));
dp[s][1]=max(dp[s][1],-S-DP(i,0));
}
S+=(a[i].is_add?1:(-1))*a[i].num;
}
return dp[s][f];
}
int main()
{
int i;
char c;
scanf("%d%d",&n,&a[1].num);
a[1].is_add=1;
for(i=1;i<n;i++)
{
while((c=getchar())!=EOF&&c^'+'&&c^'-');
a[i+1].is_add=(c=='+');
scanf("%d",&a[i+1].num);
}
for(i=1;i<=n;i++)
dp[i][0]=INF,dp[i][1]=-INF;
cout<<DP(1,1);
return 0;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:55:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&a[1].num);
^
./Main.cpp:61:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i+1].num);
^
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 |
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 |
3 ms |
256 KB |
sample_02.txt |
WA |
3 ms |
256 KB |
sample_03.txt |
AC |
3 ms |
256 KB |
subtask_1_alladd_01.txt |
TLE |
2103 ms |
10368 KB |
subtask_1_alladd_02.txt |
TLE |
2102 ms |
10368 KB |
subtask_1_alladd_03.txt |
TLE |
2102 ms |
10368 KB |
subtask_1_alladd_04.txt |
TLE |
2103 ms |
10368 KB |
subtask_1_allsub_01.txt |
TLE |
2102 ms |
10368 KB |
subtask_1_allsub_02.txt |
TLE |
2103 ms |
10368 KB |
subtask_1_allsub_03.txt |
TLE |
2103 ms |
10368 KB |
subtask_1_allsub_04.txt |
TLE |
2103 ms |
10368 KB |
subtask_1_cont_01.txt |
TLE |
2102 ms |
5760 KB |
subtask_1_cont_02.txt |
TLE |
2102 ms |
4352 KB |
subtask_1_cont_03.txt |
TLE |
2102 ms |
3712 KB |
subtask_1_cont_04.txt |
AC |
562 ms |
1024 KB |
subtask_1_killer_01.txt |
TLE |
2102 ms |
9728 KB |
subtask_1_killer_02.txt |
TLE |
2102 ms |
6784 KB |
subtask_1_killer_03.txt |
TLE |
2102 ms |
10112 KB |
subtask_1_killer_04.txt |
TLE |
2102 ms |
6912 KB |
subtask_1_max_01.txt |
TLE |
2102 ms |
10368 KB |
subtask_1_max_02.txt |
TLE |
2102 ms |
10368 KB |
subtask_1_max_03.txt |
TLE |
2103 ms |
10368 KB |
subtask_1_max_04.txt |
TLE |
2103 ms |
10368 KB |
subtask_1_min_01.txt |
AC |
3 ms |
256 KB |
subtask_1_min_02.txt |
AC |
3 ms |
256 KB |
subtask_1_rand_01.txt |
TLE |
2102 ms |
6400 KB |
subtask_1_rand_02.txt |
TLE |
2102 ms |
7680 KB |
subtask_1_rand_03.txt |
AC |
687 ms |
1152 KB |
subtask_1_rand_04.txt |
TLE |
2102 ms |
3200 KB |