Submission #3816336

---

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){
			Console.WriteLine("NG");
		}
		else{
			Console.WriteLine("OK");
			Console.WriteLine(dp[0,sl,n,1]);
		}
	}
}

Submission Info

Judge Result