oj.uz

답안 #769974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
769974 2023-06-30T15:31:12 Z LittleCube Chorus (JOI23_chorus) C++17
61 / 100
 872 ms 196412 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, K;
ll dp[5005][5005], in[1000006], suf[1000006], tot;
char c[2000006];

ll f(pll p, ll x)
{
    return p.F * x + p.S;
}

ll check(pll p1, pll p2, pll p3)
{
    return (p1.S - p2.S) * (p3.F - p2.F) >= (p2.S - p3.S) * (p2.F - p1.F);
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> K;
    for (int i = 1; i <= 2 * N; i++)
        cin >> c[i];
    for (int i = 1, j = 0, k = 1; i <= N; i++, k++)
    {
        while (c[k] != 'B')
            j++, k++;
        in[i - 1] = j;
    }
    for (int i = 0; i < N; i++)
        in[i] = max((ll)i, in[i]);
    for (int i = 1, j = N, k = 1; i <= N; i++, k++)
    {
        while (c[k] != 'A')
            j--, k++;
        suf[i] = j;
    }
    for (int i = N; i >= 0; i--)
        suf[i] += suf[i + 1];

    for (int k = 0; k <= K; k++)
        for (int i = 0; i <= N; i++)
            dp[i][k] = 1e18;
    dp[0][0] = 0;
    for (int k = 1; k <= K; k++)
    {
        deque<pll> hull, free;
        auto update = [&](pll p)
        {
            while (hull.size() >= 2 && check(hull[(int)hull.size() - 2], hull.back(), p))
                hull.pop_back();
            hull.emplace_back(p);
        };
        free.emplace_back(pll(dp[k - 1][k - 1], k - 1));
        for (int i = k; i <= N; i++)
        {
            // dp[j][k - 1] + (i - in[j]) * (N - j) - (suf[in[j] + 1] - suf[i + 1])
            // dp[j][k - 1] + i * N - i * j - in[j] * N + in[j] * j - suf[in[j] + 1] + suf[i + 1]
            // dp[j][k - 1] - in[j] * N + in[j] * j - suf[in[j] + 1]
            //                                                       - i * j
            //                                                               + i * N + suf[i + 1]
            while (!free.empty() && in[free.front().S] < i)
            {
                int j = free.front().S;
                update(pll(-j, dp[j][k - 1] - in[j] * N + in[j] * j - suf[in[j] + 1]));
                free.pop_front();
            }
            while (hull.size() >= 2 && f(hull[0], i) > f(hull[1], i))
                hull.pop_front();

            if (!hull.empty())
                dp[i][k] = min(dp[i][k], f(hull[0], i) + i * N + suf[i + 1]);
            if (!free.empty())
                dp[i][k] = min(dp[i][k], free[0].F);
            free.emplace_back(pll(dp[i][k - 1], i));
            // cout << dp[i][k] << " \n"[i == N];
        }
    }
    cout << dp[N][K] << '\n';
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 1096 KB Output is correct
18 Correct 3 ms 2764 KB Output is correct
19 Correct 4 ms 3412 KB Output is correct
20 Correct 1 ms 2388 KB Output is correct
21 Correct 1 ms 2388 KB Output is correct
22 Correct 5 ms 4300 KB Output is correct
23 Correct 5 ms 4308 KB Output is correct
24 Correct 2 ms 2388 KB Output is correct
25 Correct 6 ms 4296 KB Output is correct
26 Correct 6 ms 3924 KB Output is correct
27 Correct 4 ms 3028 KB Output is correct
28 Correct 4 ms 3016 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 1096 KB Output is correct
18 Correct 3 ms 2764 KB Output is correct
19 Correct 4 ms 3412 KB Output is correct
20 Correct 1 ms 2388 KB Output is correct
21 Correct 1 ms 2388 KB Output is correct
22 Correct 5 ms 4300 KB Output is correct
23 Correct 5 ms 4308 KB Output is correct
24 Correct 2 ms 2388 KB Output is correct
25 Correct 6 ms 4296 KB Output is correct
26 Correct 6 ms 3924 KB Output is correct
27 Correct 4 ms 3028 KB Output is correct
28 Correct 4 ms 3016 KB Output is correct
29 Correct 482 ms 99160 KB Output is correct
30 Correct 737 ms 190120 KB Output is correct
31 Correct 274 ms 61056 KB Output is correct
32 Correct 8 ms 20820 KB Output is correct
33 Correct 9 ms 20948 KB Output is correct
34 Correct 867 ms 196408 KB Output is correct
35 Correct 872 ms 196412 KB Output is correct
36 Correct 12 ms 21204 KB Output is correct
37 Correct 294 ms 59888 KB Output is correct
38 Correct 791 ms 182540 KB Output is correct
39 Correct 567 ms 113712 KB Output is correct
40 Correct 380 ms 85940 KB Output is correct
41 Correct 417 ms 85860 KB Output is correct
42 Correct 304 ms 85880 KB Output is correct

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 1096 KB Output is correct
18 Correct 3 ms 2764 KB Output is correct
19 Correct 4 ms 3412 KB Output is correct
20 Correct 1 ms 2388 KB Output is correct
21 Correct 1 ms 2388 KB Output is correct
22 Correct 5 ms 4300 KB Output is correct
23 Correct 5 ms 4308 KB Output is correct
24 Correct 2 ms 2388 KB Output is correct
25 Correct 6 ms 4296 KB Output is correct
26 Correct 6 ms 3924 KB Output is correct
27 Correct 4 ms 3028 KB Output is correct
28 Correct 4 ms 3016 KB Output is correct
29 Correct 482 ms 99160 KB Output is correct
30 Correct 737 ms 190120 KB Output is correct
31 Correct 274 ms 61056 KB Output is correct
32 Correct 8 ms 20820 KB Output is correct
33 Correct 9 ms 20948 KB Output is correct
34 Correct 867 ms 196408 KB Output is correct
35 Correct 872 ms 196412 KB Output is correct
36 Correct 12 ms 21204 KB Output is correct
37 Correct 294 ms 59888 KB Output is correct
38 Correct 791 ms 182540 KB Output is correct
39 Correct 567 ms 113712 KB Output is correct
40 Correct 380 ms 85940 KB Output is correct
41 Correct 417 ms 85860 KB Output is correct
42 Correct 304 ms 85880 KB Output is correct
43 Runtime error 65 ms 44096 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 1096 KB Output is correct
18 Correct 3 ms 2764 KB Output is correct
19 Correct 4 ms 3412 KB Output is correct
20 Correct 1 ms 2388 KB Output is correct
21 Correct 1 ms 2388 KB Output is correct
22 Correct 5 ms 4300 KB Output is correct
23 Correct 5 ms 4308 KB Output is correct
24 Correct 2 ms 2388 KB Output is correct
25 Correct 6 ms 4296 KB Output is correct
26 Correct 6 ms 3924 KB Output is correct
27 Correct 4 ms 3028 KB Output is correct
28 Correct 4 ms 3016 KB Output is correct
29 Correct 482 ms 99160 KB Output is correct
30 Correct 737 ms 190120 KB Output is correct
31 Correct 274 ms 61056 KB Output is correct
32 Correct 8 ms 20820 KB Output is correct
33 Correct 9 ms 20948 KB Output is correct
34 Correct 867 ms 196408 KB Output is correct
35 Correct 872 ms 196412 KB Output is correct
36 Correct 12 ms 21204 KB Output is correct
37 Correct 294 ms 59888 KB Output is correct
38 Correct 791 ms 182540 KB Output is correct
39 Correct 567 ms 113712 KB Output is correct
40 Correct 380 ms 85940 KB Output is correct
41 Correct 417 ms 85860 KB Output is correct
42 Correct 304 ms 85880 KB Output is correct
43 Runtime error 65 ms 44096 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -