Submission #894776

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
894776	2023-12-29 01:15:29	ksujay2	Chorus (JOI23_chorus)	C++17	100 / 100	1452 ms	75336 KiB

chorus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line {
    ll m, b, s;
    ll eval(ll x) { return m * x + b; }
};
int main() {
    int N, K; cin >> N >> K;
    string s; cin >> s;
    vector<int> h(N);
    int x = 0, y = 0;
    for(int i = 0; i < 2 * N; i++) {
        if(s[i] == 'A') h[x] = y, x++;
        else y++;
    }
    auto f = [&] (ll k) {
        vector<pair<int, Line>> cht;
        int best = 0;
        vector<pair<ll, ll>> dp(N + 1);
        ll g = 0;
        int j = 0;
        for(int i = 0; i < N; i++) {
            while(j <= h[i] && j <= i) {
                Line l;
                l.m = -j;
                l.b = dp[j].first - g + (ll) i * j;
                while(cht.size() > 0) {
                    if(cht.back().second.eval(cht.back().second.s) > l.eval(cht.back().second.s)) cht.pop_back();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

chorus.cpp: In lambda function:
chorus.cpp:32:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, Line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                     if(best == cht.size()) best--;
      |                        ~~~~~^~~~~~~~~~~~~
chorus.cpp:45:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, Line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             while(best + 1 < cht.size() && cht[best + 1].second.s <= i + 1) best++;
      |                   ~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 26 / 26
• Subtask 5: 13 / 13