oj.uz

Submission #767425

# Submission time Handle Problem Language Result Execution time Memory
767425 2023-06-26T18:26:11 Z PurpleCrayon Chorus (JOI23_chorus) C++17
40 / 100
 7000 ms 125040 KB 
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 5e3+10, MOD = 1e9+7;

int n, K, small[N], cost[N][N];
int ps[N], l_use[N];
vector<int> one, two;
int dp[N][N];

void solve() {
    cin >> n >> K;
    for (int i = 0; i < 2 * n; i++) {
        char c; cin >> c;
        if (c == 'A') one.push_back(i);
        else two.push_back(i);
    }

    // for (int x : one) cerr << x << ' '; cerr << endl;
    // for (int x : two) cerr << x << ' '; cerr << endl;

    for (int i = 0; i < n; i++) {
        small[i] = lower_bound(two.begin(), two.end(), one[i]) - two.begin();
    }

    for (int i = 0; i < n; i++) {
        ps[i] = small[i] + (i ? ps[i-1] : 0);
        l_use[i] = -(i ? ps[i-1] : 0);
        for (int j = i; j < n; j++) {
            if (small[j] < i) {
                l_use[i] -= small[j] - i;
            }
        }
    }

    // -l * (r - l + 1) + ps_small[r] - other_ps_small[l-1]
    // other_ps_small[l-1] = (small[r] < l ?
    // for (int i = 0; i < n; i++) cerr << small[i] << ' ';
    // cerr << endl;

    for (int l = 0; l < n; l++) {
        int cur = 0;
        for (int r = l; r < n; r++) {
            cur += max(small[r] - l, 0);
            cost[l][r] = cur;
        }
    }
    
    auto COST = [&](int l, int r) {
        return ps[r] + l_use[l] - l * (r - l + 1);
    };

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int one = cost[i][j];
            int two = COST(i, j);
            assert(one == 0 && two > 0 || one == two);
        }
    }

    for (int i = 0; i < n; i++) for (int j = 0; j <= K; j++) dp[i][j] = MOD;

    for (int i = 0; i < n; i++) {
        for (int k = 1; k <= K; k++) {
            for (int l = i; l >= 0; l--) {
                dp[i][k] = min(dp[i][k], COST(l, i) + (l == 0 ? 0 : dp[l-1][k-1]));
            }

            int l = small[i];
            if (l <= i) {
                dp[i][k] = min(dp[i][k], (l == 0 ? 0 : dp[l-1][k-1]));
            }
        }
    }

    cout << dp[n-1][K] << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from chorus.cpp:1:
chorus.cpp: In function 'void solve()':
chorus.cpp:60:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |             assert(one == 0 && two > 0 || one == two);
      |                    ~~~~~~~~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2 ms 1876 KB Output is correct
18 Correct 16 ms 4948 KB Output is correct
19 Correct 45 ms 5400 KB Output is correct
20 Correct 3 ms 4820 KB Output is correct
21 Correct 3 ms 4820 KB Output is correct
22 Correct 79 ms 5844 KB Output is correct
23 Correct 78 ms 5844 KB Output is correct
24 Correct 4 ms 4820 KB Output is correct
25 Correct 80 ms 5836 KB Output is correct
26 Correct 69 ms 5588 KB Output is correct
27 Correct 29 ms 5204 KB Output is correct
28 Correct 29 ms 5200 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2 ms 1876 KB Output is correct
18 Correct 16 ms 4948 KB Output is correct
19 Correct 45 ms 5400 KB Output is correct
20 Correct 3 ms 4820 KB Output is correct
21 Correct 3 ms 4820 KB Output is correct
22 Correct 79 ms 5844 KB Output is correct
23 Correct 78 ms 5844 KB Output is correct
24 Correct 4 ms 4820 KB Output is correct
25 Correct 80 ms 5836 KB Output is correct
26 Correct 69 ms 5588 KB Output is correct
27 Correct 29 ms 5204 KB Output is correct
28 Correct 29 ms 5200 KB Output is correct
29 Execution timed out 7079 ms 125040 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2 ms 1876 KB Output is correct
18 Correct 16 ms 4948 KB Output is correct
19 Correct 45 ms 5400 KB Output is correct
20 Correct 3 ms 4820 KB Output is correct
21 Correct 3 ms 4820 KB Output is correct
22 Correct 79 ms 5844 KB Output is correct
23 Correct 78 ms 5844 KB Output is correct
24 Correct 4 ms 4820 KB Output is correct
25 Correct 80 ms 5836 KB Output is correct
26 Correct 69 ms 5588 KB Output is correct
27 Correct 29 ms 5204 KB Output is correct
28 Correct 29 ms 5200 KB Output is correct
29 Execution timed out 7079 ms 125040 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 2 ms 1876 KB Output is correct
18 Correct 16 ms 4948 KB Output is correct
19 Correct 45 ms 5400 KB Output is correct
20 Correct 3 ms 4820 KB Output is correct
21 Correct 3 ms 4820 KB Output is correct
22 Correct 79 ms 5844 KB Output is correct
23 Correct 78 ms 5844 KB Output is correct
24 Correct 4 ms 4820 KB Output is correct
25 Correct 80 ms 5836 KB Output is correct
26 Correct 69 ms 5588 KB Output is correct
27 Correct 29 ms 5204 KB Output is correct
28 Correct 29 ms 5200 KB Output is correct
29 Execution timed out 7079 ms 125040 KB Time limit exceeded
30 Halted 0 ms 0 KB -