QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345246 | #3411. Absurdistan Roads | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 1.6kb | 2024-03-06 17:39:56 | 2024-03-06 17:39:56 |
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 double db;
const int N = 1 << 12;
template<typename T>
void updMin(T& a, T b)
{
a = min(a, b);
}
string s;
VI g[N];
int ball[N];
int dp[N][N];
int totBalls;
int sz[N];
void dfs(int v)
{
if (!g[v].empty())
{
sz[v] = 1;
FOR(i, 0, 2)
{
dp[v][i] = max(0, i - ball[v]);
}
return;
}
assert(SZ(g[v]) == 2);
int u1 = g[v][0], u2 = g[v][1];
dfs(u1);
dfs(u2);
sz[v] = sz[u1] + sz[u2];
FOR(k, 0, sz[v] + 1)
{
FOR(k1, k / 2, (k + 1) / 2 + 1)
{
int k2 = k - k1;
updMin(dp[v][k], dp[u1][k1] + dp[u2][k2]);
}
}
}
void solve()
{
FOR(i, 0, N)
{
g[i].clear();
ball[i] = 0;
sz[i] = 0;
}
totBalls = 0;
stack<int> st;
int v = 0;
for (char c : s)
{
if (c == '(')
{
if (!st.empty())
g[st.top()].PB(v);
st.push(v);
v++;
}
else if (c == ')')
{
st.pop();
}
else
{
assert(c == 'B');
ball[st.top()] = 1;
totBalls++;
}
}
FOR(i, 0, N)
FOR(j, 0, N)
dp[i][j] = N;
dfs(0);
cerr << "totBalls " << totBalls << endl;
if (dp[0][totBalls] == N)
cout << "impossible\n";
else
cout << dp[0][totBalls] << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> s)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
40 0 49907 81666 63518 54444 18148 77129 45370 9074 86203 77129 36296 58981 13611 86203 58981 4537 90740 40833 27222 36296 4537 45370 22685 68055 72592 68055 63518 72592 81666 22685 31759 54444 40833 18148 9074 31759 13611 27222 49907 49907 0 49907 68055 77129 31759 27222 4537 40833 36296 54444 1361...