QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345273#3419. Infix to PrefixPetroTarnavskyi#WA 113ms21036kbC++202.9kb2024-03-06 18:51:482024-03-06 18:51:48

Judging History

你现在查看的是最新测评结果

  • [2024-03-06 18:51:48]
  • 评测
  • 测评结果:WA
  • 用时:113ms
  • 内存:21036kb
  • [2024-03-06 18:51:48]
  • 提交

answer

#include <bits/stdc++.h> 

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const LL LINF = 1e18 + 44447;
const int N = 1047;
bool was[N][N];
PLL dp[N][N];
string s;
VI idx;
	
void clear(int n)
{
	idx.clear();
	n++;
	FOR (i, 0, n)
	{
		FOR (j, i, n)
		{
			dp[i][j] = {LINF, -LINF};
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	while (cin >> s)
	{
		clear(SZ(s));
		FOR (i, 0, SZ(s))
		{
			if (s[i] == '+' || s[i] == '-')
				idx.PB(i);
		}
		int n = SZ(s);
		RFOR (l, n, 0)
		{
			FOR (r, l + 1, n + 1)
			{
				if (l >= r || s[r - 1] == '+' || s[r - 1] == '-')
				{
					dp[l][r] = {-LINF, -LINF};
					continue;
				}
				if (s[l] == '+')
				{
					int j = lower_bound(ALL(idx), l) - idx.begin() + 1;
					while (j < SZ(idx) && idx[j] < r)
					{
						PLL& p1 = dp[l + 1][idx[j]];
						PLL& p2 = dp[idx[j]][r];
						j++;
						if (p1.F == -LINF || p2.F == -LINF)
							continue;
						dp[l][r].F = min(dp[l][r].F, p1.F + p2.F);
						dp[l][r].S = max(dp[l][r].S, p1.S + p2.S);
					}
					FOR (i, max(r - 10, l + 1), r + 1)
					{
						PLL& p1 = dp[l + 1][i];
						PLL& p2 = dp[i][r];
						if (p1.F == -LINF || p2.F == -LINF)
							continue;
						dp[l][r].F = min(dp[l][r].F, p1.F + p2.F);
						dp[l][r].S = max(dp[l][r].S, p1.S + p2.S);
					}
				}
				else if (s[l] == '-')
				{
					int j = lower_bound(ALL(idx), l) - idx.begin() + 1;
					while (j < SZ(idx) && idx[j] < r)
					{
						PLL& p1 = dp[l + 1][idx[j]];
						PLL& p2 = dp[idx[j]][r];
						j++;
						if (p1.F == -LINF || p2.F == -LINF)
							continue;
						dp[l][r].F = min(dp[l][r].F, p1.F - p2.S);
						dp[l][r].S = max(dp[l][r].S, p1.S - p2.F);
					}		
					FOR (i, max(r - 10, l + 1), r + 1)
					{
						PLL& p1 = dp[l + 1][i];
						PLL& p2 = dp[i][r];
						if (p1.F == -LINF || p2.F == -LINF)
							continue;
						dp[l][r].F = min(dp[l][r].F, p1.F - p2.S);
						dp[l][r].S = max(dp[l][r].S, p1.S - p2.F);
					}
					PLL& p = dp[l + 1][r];
					if (p.F != -LINF)
					{
						dp[l][r].F = min(dp[l][r].F, -p.S);
						dp[l][r].S = max(dp[l][r].S, -p.F);
					}
				}
				else
				{
					if (l + 1 == r)
					{
						dp[l][r] = {s[l] - '0', s[l] - '0'};
						continue;
					}
					if (s[l] == '0' || r - l > 9)
					{
						dp[l][r] = {-LINF, -LINF};
						continue;
					}
					int x = stoi(s.substr(l, r - l));
					dp[l][r] = {x, x};
				}
			}
		}
		
		auto p = dp[0][SZ(s)];
		cout << p.F << ' ' << p.S << '\n';
	}
	cerr << db(clock()) / CLOCKS_PER_SEC << '\n';
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 113ms
memory: 21036kb

input:

+123456789012
+102
+012
+210
0
2
-9-065
-0+60-73191753+057
-79+93+-0516+1-745503--638-+83
++9+25107+33611++20-14+3+1041+3-+6+97+-086
-8836+553609318-246-9-19+7+5400+48+-8+19-845139-049-65
+432863-90216+-973-0-+2486319++-37926-7582+++719478285231+9-2+6332
-47-94752-714+5033-61-91+67+9714119-++99284-4...

output:

912468 456789135
12 12
12 12
12 21
0 0
2 2
-56 74
-73191756 90962
-746167 1243
-1198 59980
-554451381 -552750066
-949838895 950885116
-999355097 999260439
-1018367443 1018367339
-740921427 727654485
-75596372 75600345
-1793796709 1793797612
-1957879992 1957880091
-299735305 299735251
-814951320 8143...

result:

wrong answer 7th lines differ - expected: '74 74', found: '-56 74'