QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #633133 | #9454. String of CCPC | ucup-team5226# | AC ✓ | 98ms | 3732kb | C++20 | 2.2kb | 2024-10-12 14:37:25 | 2024-10-12 14:37:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using str = string;
using vl = vector<ll>;
#define reps(i, a, n) for (ll i = (a), i##_loop_size = (n); i < i##_loop_size; i++)
#define rep(i, n) reps(i, 0, n)
#define all(a) a.begin(), a.end()
bool chmin(ll& a, ll b) {
if (a > b) {
a = b;
return true;
}
return false;
}
bool chmax(ll& a, ll b) {
if (a < b) {
a = b;
return true;
}
return false;
}
void solve() {
constexpr ll INF = 100;
ll n;
str s;
cin >> n >> s;
array<array<ll, 4>, 5> dp;
rep(i, 5) rep(j, 4) dp[i][j] = -INF;
dp[0][0] = 0;
rep(_, 6) {
array<array<ll, 4>, 5> nextdp = dp;
rep(x, 4) {
chmax(nextdp[x + 1][1], dp[x][0] - x);
chmax(nextdp[x + 1][2], dp[x][1] - x);
chmax(nextdp[x + 1][3], dp[x][2] - x);
chmax(nextdp[x + 1][1], dp[x][3] - x + 1);
}
dp.swap(nextdp);
}
rep(i, n) {
{
array<array<ll, 4>, 5> nextdp;
rep(x, 5) rep(y, 4) nextdp[x][y] = -INF;
rep(x, 5) {
if (s[i] == 'C') {
chmax(nextdp[x][1], dp[x][0]);
chmax(nextdp[x][2], dp[x][1]);
chmax(nextdp[x][2], dp[x][2]);
chmax(nextdp[x][1], dp[x][3] + 1);
} else {
chmax(nextdp[x][0], dp[x][0]);
chmax(nextdp[x][0], dp[x][1]);
chmax(nextdp[x][3], dp[x][2]);
chmax(nextdp[x][0], dp[x][3]);
}
}
dp.swap(nextdp);
}
rep(_, 6) {
array<array<ll, 4>, 5> nextdp = dp;
rep(x, 4) {
chmax(nextdp[x + 1][1], dp[x][0] - x);
chmax(nextdp[x + 1][2], dp[x][1] - x);
chmax(nextdp[x + 1][3], dp[x][2] - x);
chmax(nextdp[x + 1][1], dp[x][3] - x + 1);
}
dp.swap(nextdp);
}
}
ll ans = 0;
rep(x, 5) rep(y, 4) chmax(ans, dp[x][y]);
cout << ans << endl;
}
int main() {
ll t;
cin >> t;
rep(i, t) solve();
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
3 3 CCC 5 CCCCP 4 CPCP
output:
1 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 98ms
memory: 3732kb
input:
20003 5 PCCPC 10 CPPPPCPCPC 4 CPPC 11 CCPPCPPPCCP 17 PPPPCPCCCCCPCCCCC 10 PPCCPCPPCP 9 CPCCCCPPC 11 PCPPPPCCPPP 15 CPCPPPPCCPCPCCC 11 PCCPPCCPCPP 9 PCPCCPPCP 10 CCPCPPPCPP 14 CCCCPPPCPCPCPP 2 CC 12 CCPCPPPPPCPP 6 CPPPPP 12 PCCPCCCCCPCC 16 CPCCPCCPPCCCCPPC 7 CPPPCPC 16 PPPPPCCPCPCPCPPC 13 PPPCPCCCCPP...
output:
1 1 0 1 2 1 1 1 2 2 1 1 1 0 1 0 3 2 1 2 1 2 2 0 1 2 3 1 1 3 1 2 2 1 0 0 0 3 1 0 0 1 1 2 0 1 1 0 1 2 0 1 0 1 0 3 1 1 0 2 1 3 2 2 0 2 2 0 0 2 1 1 3 3 1 3 1 2 0 1 1 0 1 2 2 1 1 2 1 3 1 1 3 1 2 2 0 1 0 3 0 1 1 2 2 0 2 1 1 2 2 0 3 1 1 1 1 2 1 2 0 1 1 0 3 0 3 1 1 0 0 1 0 3 0 1 1 1 1 2 2 1 1 0 0 1 2 0 1 2 ...
result:
ok 20003 lines
Extra Test:
score: 0
Extra Test Passed