Submission #1063854


Source Code Expand

Copy
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

#define OK "OK"
#define NG "NG"

int k;
string s;
int n;

#define INF (1000000)

int dp[2][100][100][100];

int main(int argc, char **argv) {
	cin >> k >> s;
	n = s.length();
	if (n % 2 == 0) {
		cout << NG << endl;
		return 0;
	}
	REP(i, n) REP(j, n - i + 1) REP(l, k + 1) {
		dp[0][i][j][l] = INF;
		dp[1][i][j][l] = -INF;
	}
	REP(i, n) {
		if (s[i] >= '0' && s[i] <= '9') {
			dp[0][i][1][0] = dp[1][i][1][0] = s[i] - '0';
		}
		dp[0][i][1][1] = 0;
		dp[1][i][1][1] = 9;
	}
	REP(temp, n / 2) {
		int j = temp * 2 + 3;
		REP(i, n - j + 1) {
			REP(temp2, j / 2) {
				int j2 = temp2 * 2 + 1;
				REP(l1, k + 1) REP(l2, k - l1 + 1) {
					int mi1 = dp[0][i][j2][l1];
					int ma1 = dp[1][i][j2][l1];
					int mi2 = dp[0][i + j2][j - j2 - 1][l2];
					int ma2 = dp[1][i + j2][j - j2 - 1][l2];
					if (s[i + j - 1] == '+') {
						dp[0][i][j][l1 + l2] = min(dp[0][i][j][l1 + l2], mi1 + mi2);
						dp[0][i][j][l1 + l2 + 1] = min(dp[0][i][j][l1 + l2 + 1], mi1 - ma2);
						dp[1][i][j][l1 + l2] = max(dp[1][i][j][l1 + l2], ma1 + ma2);
						dp[1][i][j][l1 + l2 + 1] = max(dp[1][i][j][l1 + l2 + 1], ma1 - mi2);
					}
					else if (s[i + j - 1] == '-') {
						dp[0][i][j][l1 + l2 + 1] = min(dp[0][i][j][l1 + l2 + 1], mi1 + mi2);
						dp[0][i][j][l1 + l2] = min(dp[0][i][j][l1 + l2], mi1 - ma2);
						dp[1][i][j][l1 + l2 + 1] = max(dp[1][i][j][l1 + l2 + 1], ma1 + ma2);
						dp[1][i][j][l1 + l2] = max(dp[1][i][j][l1 + l2], ma1 - mi2);
					}
					else {
						dp[0][i][j][l1 + l2 + 1] = min(dp[0][i][j][l1 + l2 + 1], mi1 + mi2);
						dp[0][i][j][l1 + l2 + 1] = min(dp[0][i][j][l1 + l2 + 1], mi1 - ma2);
						dp[1][i][j][l1 + l2 + 1] = max(dp[1][i][j][l1 + l2 + 1], ma1 + ma2);
						dp[1][i][j][l1 + l2 + 1] = max(dp[1][i][j][l1 + l2 + 1], ma1 - mi2);
					}
				}
			}
		}
	}
	int res = -INF;
	REP(l, k + 1) res = max(res, dp[1][0][n][l]);
	if (abs(res) < 1000) {
		cout << OK << endl;
		cout << res << endl;
	}
	else {
		cout << NG << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task A - 計算ドリル
User yupotown
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2903 Byte
Status AC
Exec Time 33 ms
Memory 1664 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 5
AC × 53
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 3 ms 256 KB
example1 AC 3 ms 256 KB
example2 AC 3 ms 256 KB
example3 AC 3 ms 256 KB
example4 AC 3 ms 256 KB
handmade0 AC 3 ms 256 KB
handmade1 AC 3 ms 256 KB
handmade2 AC 3 ms 256 KB
maxrand0 AC 3 ms 256 KB
maxrand1 AC 3 ms 256 KB
maxrand10 AC 15 ms 1664 KB
maxrand11 AC 3 ms 256 KB
maxrand12 AC 4 ms 1664 KB
maxrand13 AC 2 ms 256 KB
maxrand14 AC 33 ms 1664 KB
maxrand15 AC 17 ms 1664 KB
maxrand16 AC 4 ms 1664 KB
maxrand17 AC 18 ms 1664 KB
maxrand18 AC 3 ms 256 KB
maxrand19 AC 25 ms 1664 KB
maxrand2 AC 2 ms 256 KB
maxrand3 AC 26 ms 1664 KB
maxrand4 AC 10 ms 1664 KB
maxrand5 AC 3 ms 256 KB
maxrand6 AC 3 ms 256 KB
maxrand7 AC 2 ms 256 KB
maxrand8 AC 2 ms 256 KB
maxrand9 AC 30 ms 1664 KB
rand0 AC 2 ms 256 KB
rand1 AC 3 ms 512 KB
rand10 AC 3 ms 640 KB
rand11 AC 2 ms 256 KB
rand12 AC 3 ms 768 KB
rand13 AC 3 ms 384 KB
rand14 AC 3 ms 256 KB
rand15 AC 2 ms 256 KB
rand16 AC 3 ms 256 KB
rand17 AC 3 ms 256 KB
rand18 AC 2 ms 256 KB
rand19 AC 2 ms 256 KB
rand2 AC 3 ms 256 KB
rand3 AC 3 ms 512 KB
rand4 AC 17 ms 1408 KB
rand5 AC 3 ms 256 KB
rand6 AC 3 ms 512 KB
rand7 AC 2 ms 256 KB
rand8 AC 3 ms 256 KB
rand9 AC 3 ms 256 KB
smallrand0 AC 3 ms 256 KB
smallrand1 AC 2 ms 256 KB
smallrand2 AC 2 ms 256 KB
smallrand3 AC 2 ms 256 KB
smallrand4 AC 3 ms 256 KB