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

Submission Time
Task E - Addition and Subtraction Hard
User vjudge1
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1233 Byte
Status WA
Exec Time 2103 ms
Memory 10368 KB

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
AC × 2
WA × 1
AC × 4
TLE × 22
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