QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[2024-10-12 14:37:26]
评测

测评结果：AC
用时：98ms
内存：3732kb

查看

[2024-10-12 14:37:25]
提交

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();
}

源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

詳細信息

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:

result:

ok 20003 lines

Extra Test:

score: 0

Extra Test Passed