Submission #3816405
Source Code Expand
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
static void Main(){
int n=int.Parse(Console.ReadLine());
string s=Console.ReadLine();
int sl=s.Length;
long[,,,] dp=new long[sl,sl+1,n+1,2];
for(int i=1;i<=sl;i+=2){
for(int j=0;j+i<=sl;j++){
for(int k=0;k<=n;k++){
dp[j,j+i,k,0]=int.MaxValue;
dp[j,j+i,k,1]=int.MinValue;
if(k>0){
if(i>2){
for(int l=j+1;l<j+i-1;l+=2){
if(s[j+i-1]>47){
for(int m=0;m<=k-1;m++){
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,m,0]+dp[l,j+i-1,k-m-1,0]);
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,m,0]-dp[l,j+i-1,k-m-1,1]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,m,1]+dp[l,j+i-1,k-m-1,1]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,m,1]-dp[l,j+i-1,k-m-1,0]);
}
}
else if(s[j+i-1]==43){
for(int m=0;m<=k-1;m++){
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,m,0]+dp[l,j+i-1,k-m,0]);
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,m,0]-dp[l,j+i-1,k-m-1,1]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,m,1]+dp[l,j+i-1,k-m,1]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,m,1]-dp[l,j+i-1,k-m-1,0]);
}
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,k,0]+dp[l,j+i-1,0,0]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,k,1]+dp[l,j+i-1,0,1]);
}
else{
for(int m=0;m<=k-1;m++){
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,m,0]+dp[l,j+i-1,k-m-1,0]);
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,m,0]-dp[l,j+i-1,k-m,1]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,m,1]+dp[l,j+i-1,k-m-1,1]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,m,1]-dp[l,j+i-1,k-m,0]);
}
dp[j,j+i,k,0]=Math.Min(dp[j,j+i,k,0],dp[j,l,k,0]-dp[l,j+i-1,0,1]);
dp[j,j+i,k,1]=Math.Max(dp[j,j+i,k,1],dp[j,l,k,1]-dp[l,j+i-1,0,0]);
}
}
}
else{
dp[j,j+i,k,0]=0;
dp[j,j+i,k,1]=9;
}
}
else{
if(i>2){
if(s[j+i-1]<47){
for(int l=j+1;l<j+i-1;l+=2){
if(dp[j,l,k,0]!=int.MaxValue&&dp[l,j+i-1,k,0]!=int.MaxValue){
if(s[j+i-1]==43){
dp[j,j+i,k,0]=dp[j,l,k,0]+dp[l,j+i-1,k,0];
dp[j,j+i,k,1]=dp[j,l,k,1]+dp[l,j+i-1,k,1];
}
else{
dp[j,j+i,k,0]=dp[j,l,k,0]-dp[l,j+i-1,k,1];
dp[j,j+i,k,1]=dp[j,l,k,1]-dp[l,j+i-1,k,0];
}
}
}
}
}
else{
if(s[j]>47){
dp[j,j+i,k,0]=s[j]-'0';
dp[j,j+i,k,1]=s[j]-'0';
}
}
}
}
}
}
if(dp[0,sl,n,1]<-10000||sl%2==0){
Console.WriteLine("NG");
}
else{
Console.WriteLine("OK");
Console.WriteLine(dp[0,sl,n,1]);
}
}
}
Submission Info
Submission Time |
|
Task |
A - 計算ドリル |
User |
fgwiebfaoish |
Language |
C# (Mono 4.6.2.0) |
Score |
500 |
Code Size |
2891 Byte |
Status |
AC |
Exec Time |
1104 ms |
Memory |
13268 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 |
22 ms |
9172 KB |
example1 |
AC |
22 ms |
9172 KB |
example2 |
AC |
23 ms |
11220 KB |
example3 |
AC |
22 ms |
9172 KB |
example4 |
AC |
23 ms |
9172 KB |
handmade0 |
AC |
23 ms |
11220 KB |
handmade1 |
AC |
21 ms |
9172 KB |
handmade2 |
AC |
23 ms |
11220 KB |
maxrand0 |
AC |
187 ms |
11744 KB |
maxrand1 |
AC |
307 ms |
9696 KB |
maxrand10 |
AC |
288 ms |
11616 KB |
maxrand11 |
AC |
593 ms |
9824 KB |
maxrand12 |
AC |
27 ms |
9124 KB |
maxrand13 |
AC |
101 ms |
9440 KB |
maxrand14 |
AC |
821 ms |
9952 KB |
maxrand15 |
AC |
352 ms |
11616 KB |
maxrand16 |
AC |
29 ms |
11172 KB |
maxrand17 |
AC |
401 ms |
11744 KB |
maxrand18 |
AC |
62 ms |
9312 KB |
maxrand19 |
AC |
589 ms |
11872 KB |
maxrand2 |
AC |
902 ms |
10080 KB |
maxrand3 |
AC |
619 ms |
9824 KB |
maxrand4 |
AC |
178 ms |
11744 KB |
maxrand5 |
AC |
54 ms |
9312 KB |
maxrand6 |
AC |
204 ms |
9824 KB |
maxrand7 |
AC |
1104 ms |
10208 KB |
maxrand8 |
AC |
345 ms |
9696 KB |
maxrand9 |
AC |
715 ms |
12000 KB |
rand0 |
AC |
22 ms |
11220 KB |
rand1 |
AC |
25 ms |
9100 KB |
rand10 |
AC |
36 ms |
11180 KB |
rand11 |
AC |
55 ms |
11232 KB |
rand12 |
AC |
25 ms |
11128 KB |
rand13 |
AC |
22 ms |
9172 KB |
rand14 |
AC |
29 ms |
9152 KB |
rand15 |
AC |
22 ms |
13268 KB |
rand16 |
AC |
155 ms |
9568 KB |
rand17 |
AC |
22 ms |
11188 KB |
rand18 |
AC |
66 ms |
11360 KB |
rand19 |
AC |
30 ms |
11208 KB |
rand2 |
AC |
236 ms |
11744 KB |
rand3 |
AC |
22 ms |
11220 KB |
rand4 |
AC |
371 ms |
9568 KB |
rand5 |
AC |
25 ms |
13196 KB |
rand6 |
AC |
23 ms |
9128 KB |
rand7 |
AC |
31 ms |
11204 KB |
rand8 |
AC |
22 ms |
11184 KB |
rand9 |
AC |
23 ms |
11184 KB |
smallrand0 |
AC |
22 ms |
9172 KB |
smallrand1 |
AC |
22 ms |
9172 KB |
smallrand2 |
AC |
22 ms |
9172 KB |
smallrand3 |
AC |
23 ms |
11220 KB |
smallrand4 |
AC |
22 ms |
11220 KB |