QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345283 | #3419. Infix to Prefix | PetroTarnavskyi# | AC ✓ | 119ms | 15460kb | C++20 | 3.1kb | 2024-03-06 18:59:14 | 2024-03-06 18:59:14 |
Judging History
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;
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, 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;
}
bool ok =true;
FOR (i, l, r)
if (s[i] == '+' || s[i] == '-')
ok = false;
if (!ok)
{
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: 100
Accepted
time: 119ms
memory: 15460kb
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 74 74 -73191756 -73191756 -745651 -744936 24327 59902 -554440547 -554440481 -949838387 950884545 -999355092 979728736 -1018367442 1018367332 -740921427 727654475 61240554 75587461 -1793606917 1793797611 -1957879068 1957879015 -299734325 299734252 -814950751...
result:
ok 41 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
--34 +1234 --09 +111111111111 --0071
output:
-7 34 46 235 -9 9 222222 111111222 -71 -71
result:
ok 5 lines