답안 #963058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963058	2024-04-14T12:36:09 Z	RaresFelix	Chorus (JOI23_chorus)	C++17	61 / 100	1065 ms	1048576 KB

chorus

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

const ll INF = 1e18;

struct CHT {
    int p = 0;
    vector<pair<ll, ll> > V;
    void insert(ll a, ll b) { /// ax + b
        //a va scadea mereu
        while(V.size() > 1) {
            auto [a1, b1] = V.end()[-1];
            auto [a2, b2] = V.end()[-2];
            if((b2 - b) * (a1 - a2) <= (b2 - b1) * (a - a2)) {
                V.pop_back();
                p = min(p, int(V.size()) - 1);
            }
            else break;
        }
        V.push_back({a, b});
    }

    ll query(ll x) {
        if(V.empty()) return INF;
        ll re = INF;
        auto eval = [&](int i) -> ll {
            return V[i].first * x + V[i].second;
        };
        while(p + 1 < V.size() && eval(p + 1) < eval(p)) ++p;
        return min(eval(p), INF);
    }
};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;

    string s0, s;
    cin >> s0;
    ll re0 = 0;
    int nrB = 0, sum = 0;
    for(auto it : s0) {
        if(it == 'A') {
            ++sum;
            s += 'A';
            re0 += nrB;
            if(nrB && sum) {
                s += 'B';
                --nrB;
                --sum;
            }
        } else {
            if(sum) {
                s += 'B';
                --sum;
            } else {
                ++nrB;
            }
        }
    }

    vll A, P(n + 1);
    vll SA;
    P[0] = -1;
    for(auto it : s) {
        if(it == 'A'){
            A.push_back(nrB);
            if(SA.empty())
                SA.push_back(A.back());
            else
                SA.push_back(A.back() + SA.back());
        } 
        else {
            ++nrB;
            P[nrB] = (int)A.size() - 1;
        }
    }
    vll SAP(n);
    for(int i = 0; i < n; ++i) {
        SAP[i] = 0;
        if(P[i] != -1) SAP[i] = SA[P[i]];
    }

    auto cost = [&](ll st, ll dr) {
        return st * P[st] - SAP[st] + SA[dr] - st * dr;
    };

    vector<vll> DP(n, vll(k + 1, INF));

    vector<CHT> Sol(k + 1);
    for(int i = 0; i < n; ++i) {
        DP[i][1] = cost(0, i);
        if(i)
            Sol[1].insert(-i, i * P[i] - SAP[i] + DP[i - 1][1]);
        for(int j = 2; j <= k; ++j) {
            if(i)
                Sol[j].insert(-i, DP[i - 1][j] + i * P[i] - SAP[i]);
            DP[i][j] = Sol[j - 1].query(i) + SA[i];
        }
    }

    ll re = INF;
    for(auto it : DP[n - 1]) re = min(re, it);

    cout << re + re0 << "\n";
    return 0;
}

Compilation message

chorus.cpp: In member function 'll CHT::query(ll)':
chorus.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while(p + 1 < V.size() && eval(p + 1) < eval(p)) ++p;
      |               ~~~~~~^~~~~~~~~~
chorus.cpp:39:12: warning: unused variable 're' [-Wunused-variable]
   39 |         ll re = INF;
      |            ^~

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	512 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	352 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	452 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	512 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	352 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	452 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	2 ms	1116 KB	Output is correct
19	Correct	3 ms	2652 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	352 KB	Output is correct
22	Correct	6 ms	6300 KB	Output is correct
23	Correct	6 ms	6492 KB	Output is correct
24	Correct	1 ms	608 KB	Output is correct
25	Correct	6 ms	6492 KB	Output is correct
26	Correct	5 ms	5468 KB	Output is correct
27	Correct	2 ms	1628 KB	Output is correct
28	Correct	2 ms	1628 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	512 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	352 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	452 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	2 ms	1116 KB	Output is correct
19	Correct	3 ms	2652 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	352 KB	Output is correct
22	Correct	6 ms	6300 KB	Output is correct
23	Correct	6 ms	6492 KB	Output is correct
24	Correct	1 ms	608 KB	Output is correct
25	Correct	6 ms	6492 KB	Output is correct
26	Correct	5 ms	5468 KB	Output is correct
27	Correct	2 ms	1628 KB	Output is correct
28	Correct	2 ms	1628 KB	Output is correct
29	Correct	342 ms	215212 KB	Output is correct
30	Correct	766 ms	360188 KB	Output is correct
31	Correct	127 ms	75860 KB	Output is correct
32	Correct	1 ms	1116 KB	Output is correct
33	Correct	1 ms	1116 KB	Output is correct
34	Correct	1065 ms	570872 KB	Output is correct
35	Correct	1038 ms	570656 KB	Output is correct
36	Correct	2 ms	1880 KB	Output is correct
37	Correct	128 ms	96340 KB	Output is correct
38	Correct	748 ms	449764 KB	Output is correct
39	Correct	361 ms	218464 KB	Output is correct
40	Correct	208 ms	116516 KB	Output is correct
41	Correct	254 ms	116564 KB	Output is correct
42	Correct	205 ms	109136 KB	Output is correct

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	512 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	352 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	452 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	2 ms	1116 KB	Output is correct
19	Correct	3 ms	2652 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	352 KB	Output is correct
22	Correct	6 ms	6300 KB	Output is correct
23	Correct	6 ms	6492 KB	Output is correct
24	Correct	1 ms	608 KB	Output is correct
25	Correct	6 ms	6492 KB	Output is correct
26	Correct	5 ms	5468 KB	Output is correct
27	Correct	2 ms	1628 KB	Output is correct
28	Correct	2 ms	1628 KB	Output is correct
29	Correct	342 ms	215212 KB	Output is correct
30	Correct	766 ms	360188 KB	Output is correct
31	Correct	127 ms	75860 KB	Output is correct
32	Correct	1 ms	1116 KB	Output is correct
33	Correct	1 ms	1116 KB	Output is correct
34	Correct	1065 ms	570872 KB	Output is correct
35	Correct	1038 ms	570656 KB	Output is correct
36	Correct	2 ms	1880 KB	Output is correct
37	Correct	128 ms	96340 KB	Output is correct
38	Correct	748 ms	449764 KB	Output is correct
39	Correct	361 ms	218464 KB	Output is correct
40	Correct	208 ms	116516 KB	Output is correct
41	Correct	254 ms	116564 KB	Output is correct
42	Correct	205 ms	109136 KB	Output is correct
43	Runtime error	582 ms	1048576 KB	Execution killed with signal 9
44	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	512 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	352 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	452 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	2 ms	1116 KB	Output is correct
19	Correct	3 ms	2652 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	352 KB	Output is correct
22	Correct	6 ms	6300 KB	Output is correct
23	Correct	6 ms	6492 KB	Output is correct
24	Correct	1 ms	608 KB	Output is correct
25	Correct	6 ms	6492 KB	Output is correct
26	Correct	5 ms	5468 KB	Output is correct
27	Correct	2 ms	1628 KB	Output is correct
28	Correct	2 ms	1628 KB	Output is correct
29	Correct	342 ms	215212 KB	Output is correct
30	Correct	766 ms	360188 KB	Output is correct
31	Correct	127 ms	75860 KB	Output is correct
32	Correct	1 ms	1116 KB	Output is correct
33	Correct	1 ms	1116 KB	Output is correct
34	Correct	1065 ms	570872 KB	Output is correct
35	Correct	1038 ms	570656 KB	Output is correct
36	Correct	2 ms	1880 KB	Output is correct
37	Correct	128 ms	96340 KB	Output is correct
38	Correct	748 ms	449764 KB	Output is correct
39	Correct	361 ms	218464 KB	Output is correct
40	Correct	208 ms	116516 KB	Output is correct
41	Correct	254 ms	116564 KB	Output is correct
42	Correct	205 ms	109136 KB	Output is correct
43	Runtime error	582 ms	1048576 KB	Execution killed with signal 9
44	Halted	0 ms	0 KB	-

답안 #963058

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0