Submission #3631604
Source Code Expand
#include <iostream> #include <string.h> #include <stdio.h> #include <map> #include <vector> #include <math.h> #include <algorithm> #include <queue> #include <set> #include <tuple> using namespace std; #define FOR(i,init,a) for(int i=init; i<a; i++) #define rep(i,a) FOR(i,0,a) #define rrep(i,a) for(int i=a; i>=0; i--) #define rep1(i,a) for(int i=1; i<=a; i++) #define cout1(a) cout << a << endl; #define cout2(a,b) cout << a << " " << b << endl; #define cout3(a,b,c) cout << a << " " << b << " " << c << endl; #define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl; #define mem(a,n) memset( a, n, sizeof(a)) #define all(a) a.begin(),a.end() typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef vector<int> V; typedef vector<V> VV; typedef vector<VV> VVV; const int INF = 1e9; const int MOD = 1e9+7; const ll LLINF = 1e18; static const double pi = 3.141592653589793; int N, K; string S; bool visit[60][60][60], res[60][60][60]; int dp[60][60][60][2]; bool dfs(int L,int R,int K){ if(visit[L][R][K]) return res[L][R][K]; if((R-L)%2) return false; visit[L][R][K]=true; dp[L][R][K][0]=1<<20; dp[L][R][K][1]=-1<<20; if(L==R){ if(K){ res[L][R][K]=true; dp[L][R][K][0]=0; dp[L][R][K][1]=9; }else{ if(S[L]>='0'&&S[L]<='9'){ res[L][R][K]=true; dp[L][R][K][0]=dp[L][R][K][1]=S[L]-'0'; } } }else{ int left=K-(S[R]!='+'); if(left>=0){ for(int M=L;M<R-1;M++)rep(LL,left+1){ if(dfs(L,M,LL)&&dfs(M+1,R-1,left-LL)){ res[L][R][K]=true; dp[L][R][K][0]=min(dp[L][R][K][0],dp[L][M][LL][0]+dp[M+1][R-1][left-LL][0]); dp[L][R][K][1]=max(dp[L][R][K][1],dp[L][M][LL][1]+dp[M+1][R-1][left-LL][1]); } } } left=K-(S[R]!='-'); if(left>=0){ for(int M=L;M<R-1;M++)rep(LL,left+1){ if(dfs(L,M,LL)&&dfs(M+1,R-1,left-LL)){ res[L][R][K]=true; dp[L][R][K][0]=min(dp[L][R][K][0],dp[L][M][LL][0]-dp[M+1][R-1][left-LL][1]); dp[L][R][K][1]=max(dp[L][R][K][1],dp[L][M][LL][1]-dp[M+1][R-1][left-LL][0]); } } } } return res[L][R][K]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin>>K>>S; N=S.size(); int ma=-10000; rep(i,K+1)if(dfs(0,N-1,i)) ma=max(ma,dp[0][N-1][i][1]); if(ma==-10000){ cout1("NG"); }else{ cout1("OK"); cout1(ma); } }
Submission Info
Submission Time | |
---|---|
Task | A - 計算ドリル |
User | mensan_fukuhara |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2764 Byte |
Status | AC |
Exec Time | 123 ms |
Memory | 1408 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3, example4 |
All | example0, example1, example2, example3, example4, handmade0, handmade1, handmade2, maxrand0, maxrand1, maxrand10, maxrand11, maxrand12, maxrand13, maxrand14, maxrand15, maxrand16, maxrand17, maxrand18, maxrand19, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand10, rand11, rand12, rand13, rand14, rand15, rand16, rand17, rand18, rand19, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
example4 | AC | 1 ms | 384 KB |
handmade0 | AC | 1 ms | 256 KB |
handmade1 | AC | 1 ms | 256 KB |
handmade2 | AC | 1 ms | 256 KB |
maxrand0 | AC | 1 ms | 256 KB |
maxrand1 | AC | 1 ms | 256 KB |
maxrand10 | AC | 38 ms | 1408 KB |
maxrand11 | AC | 1 ms | 256 KB |
maxrand12 | AC | 1 ms | 384 KB |
maxrand13 | AC | 1 ms | 256 KB |
maxrand14 | AC | 123 ms | 1408 KB |
maxrand15 | AC | 41 ms | 1408 KB |
maxrand16 | AC | 1 ms | 384 KB |
maxrand17 | AC | 45 ms | 1408 KB |
maxrand18 | AC | 1 ms | 256 KB |
maxrand19 | AC | 77 ms | 1408 KB |
maxrand2 | AC | 1 ms | 256 KB |
maxrand3 | AC | 79 ms | 1408 KB |
maxrand4 | AC | 18 ms | 1408 KB |
maxrand5 | AC | 1 ms | 256 KB |
maxrand6 | AC | 1 ms | 256 KB |
maxrand7 | AC | 1 ms | 256 KB |
maxrand8 | AC | 1 ms | 256 KB |
maxrand9 | AC | 93 ms | 1408 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 2 ms | 512 KB |
rand10 | AC | 3 ms | 512 KB |
rand11 | AC | 1 ms | 256 KB |
rand12 | AC | 2 ms | 640 KB |
rand13 | AC | 1 ms | 256 KB |
rand14 | AC | 1 ms | 256 KB |
rand15 | AC | 1 ms | 256 KB |
rand16 | AC | 1 ms | 256 KB |
rand17 | AC | 1 ms | 256 KB |
rand18 | AC | 1 ms | 256 KB |
rand19 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |
rand3 | AC | 1 ms | 256 KB |
rand4 | AC | 45 ms | 1152 KB |
rand5 | AC | 1 ms | 256 KB |
rand6 | AC | 1 ms | 512 KB |
rand7 | AC | 1 ms | 256 KB |
rand8 | AC | 1 ms | 256 KB |
rand9 | AC | 1 ms | 256 KB |
smallrand0 | AC | 1 ms | 256 KB |
smallrand1 | AC | 1 ms | 256 KB |
smallrand2 | AC | 1 ms | 256 KB |
smallrand3 | AC | 1 ms | 256 KB |
smallrand4 | AC | 1 ms | 256 KB |