oj.uz

Submission #963071

# Submission time Handle Problem Language Result Execution time Memory
963071 2024-04-14T12:58:15 Z RaresFelix Chorus (JOI23_chorus) C++17
100 / 100
 1045 ms 99460 KB 
#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<tuple<ll, ll, int> > V;
    void insert(ll a, ll b, int cnt) { /// ax + b
        //a va scadea mereu
        while(V.size() > 1) {
            auto [a1, b1, c1] = V.end()[-1];
            auto [a2, b2, c2] = 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, cnt});
    }

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

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


    auto t = [&](ll lambda) {
        ll re = - lambda * k;
        vll DP(n, INF);
        vi Nr(n, 0);

        CHT Sol;

        for(int i = 0; i < n; ++i) {
            DP[i] = cost(0, i) + lambda;
            Nr[i] = 1;
            if(i)
                Sol.insert(-i, i * P[i] - SAP[i] + DP[i - 1], Nr[i - 1]);
            auto [val, nr] = Sol.query(i);
            val += lambda + SA[i];
            if(val < DP[i]) {
                DP[i] = val;
                Nr[i] = nr + 1;
            }
        }
        return make_pair(DP[n - 1] + re, Nr[n - 1] - k);
    };

    ll st = 0, dr = 1e12, mij;

    ll re = 0;
    for(int i = 0; i <= 200; ++i) {
        mij = (st + dr) / 2;
        auto [val, g] = t(mij);
        re = max(re, val);
        if(st == dr) break;
        if(g > 0) st = mij + 1;
        else dr = mij;
    }

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

Compilation message

chorus.cpp: In member function 'std::pair<long long int, int> CHT::query(ll)':
chorus.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 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 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 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 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 6 ms 1020 KB Output is correct
30 Correct 5 ms 876 KB Output is correct
31 Correct 5 ms 1132 KB Output is correct
32 Correct 5 ms 1032 KB Output is correct
33 Correct 5 ms 1040 KB Output is correct
34 Correct 5 ms 1100 KB Output is correct
35 Correct 5 ms 1024 KB Output is correct
36 Correct 5 ms 900 KB Output is correct
37 Correct 6 ms 900 KB Output is correct
38 Correct 6 ms 1020 KB Output is correct
39 Correct 5 ms 988 KB Output is correct
40 Correct 3 ms 604 KB Output is correct
41 Correct 3 ms 604 KB Output is correct
42 Correct 3 ms 600 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 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 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 6 ms 1020 KB Output is correct
30 Correct 5 ms 876 KB Output is correct
31 Correct 5 ms 1132 KB Output is correct
32 Correct 5 ms 1032 KB Output is correct
33 Correct 5 ms 1040 KB Output is correct
34 Correct 5 ms 1100 KB Output is correct
35 Correct 5 ms 1024 KB Output is correct
36 Correct 5 ms 900 KB Output is correct
37 Correct 6 ms 900 KB Output is correct
38 Correct 6 ms 1020 KB Output is correct
39 Correct 5 ms 988 KB Output is correct
40 Correct 3 ms 604 KB Output is correct
41 Correct 3 ms 604 KB Output is correct
42 Correct 3 ms 600 KB Output is correct
43 Correct 58 ms 6004 KB Output is correct
44 Correct 103 ms 11432 KB Output is correct
45 Correct 99 ms 10068 KB Output is correct
46 Correct 98 ms 10800 KB Output is correct
47 Correct 118 ms 10596 KB Output is correct
48 Correct 118 ms 10940 KB Output is correct
49 Correct 108 ms 10700 KB Output is correct
50 Correct 95 ms 10040 KB Output is correct
51 Correct 106 ms 11244 KB Output is correct
52 Correct 118 ms 10756 KB Output is correct
53 Correct 113 ms 10720 KB Output is correct
54 Correct 96 ms 11064 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 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 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 6 ms 1020 KB Output is correct
30 Correct 5 ms 876 KB Output is correct
31 Correct 5 ms 1132 KB Output is correct
32 Correct 5 ms 1032 KB Output is correct
33 Correct 5 ms 1040 KB Output is correct
34 Correct 5 ms 1100 KB Output is correct
35 Correct 5 ms 1024 KB Output is correct
36 Correct 5 ms 900 KB Output is correct
37 Correct 6 ms 900 KB Output is correct
38 Correct 6 ms 1020 KB Output is correct
39 Correct 5 ms 988 KB Output is correct
40 Correct 3 ms 604 KB Output is correct
41 Correct 3 ms 604 KB Output is correct
42 Correct 3 ms 600 KB Output is correct
43 Correct 58 ms 6004 KB Output is correct
44 Correct 103 ms 11432 KB Output is correct
45 Correct 99 ms 10068 KB Output is correct
46 Correct 98 ms 10800 KB Output is correct
47 Correct 118 ms 10596 KB Output is correct
48 Correct 118 ms 10940 KB Output is correct
49 Correct 108 ms 10700 KB Output is correct
50 Correct 95 ms 10040 KB Output is correct
51 Correct 106 ms 11244 KB Output is correct
52 Correct 118 ms 10756 KB Output is correct
53 Correct 113 ms 10720 KB Output is correct
54 Correct 96 ms 11064 KB Output is correct
55 Correct 728 ms 56584 KB Output is correct
56 Correct 1045 ms 97088 KB Output is correct
57 Correct 951 ms 95208 KB Output is correct
58 Correct 809 ms 97548 KB Output is correct
59 Correct 835 ms 98292 KB Output is correct
60 Correct 859 ms 98848 KB Output is correct
61 Correct 897 ms 99244 KB Output is correct
62 Correct 917 ms 93940 KB Output is correct
63 Correct 945 ms 92844 KB Output is correct
64 Correct 878 ms 99460 KB Output is correct
65 Correct 904 ms 98576 KB Output is correct
66 Correct 986 ms 95468 KB Output is correct
67 Correct 841 ms 98676 KB Output is correct