oj.uz

Submission #994674

# Submission time Handle Problem Language Result Execution time Memory
994674 2024-06-08T03:31:39 Z 12345678 Chorus (JOI23_chorus) C++17
0 / 100
 1 ms 4444 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;

#define ll long long

ll n, k, h[nx], p[nx], qs[nx], r=0, c=1, idx=1;
pair<ll, ll> dp[nx];
string s;

ll cost(ll l, ll r)
{
    if (p[r]<=l) return 0;
    return r*(p[r]-l)-(qs[p[r]-1]-qs[l-1]);
}

struct line
{
    ll m, c, cnt;
    line(ll m=0, ll c=0, ll cnt=0): m(m), c(c), cnt(cnt){}
    ll val(ll x) {return m*x+c;}
};

struct convexhulltrick
{
    deque<line> dq;
    ll bad(line a, line b, line c)
    {
        return (a.c-c.c)*(b.m-a.m)<(a.c-b.c)*(c.m-a.m);
    }
    void add(line x)
    {
        while (dq.size()>=2&&bad(dq[dq.size()-2], dq.back(), x)) dq.pop_back();
        dq.push_back(x);
    }
    line query(ll x)
    {
        while (dq.size()>=2&&dq[0].val(x)>dq[2].val(x)) dq.pop_front();
        return dq[0];
    }
} d;

pair<ll, ll> solve(ll lambda)
{
    idx=1;
    d.dq.clear();
    for (int i=1; i<=n; i++)
    {
        while (idx<=p[i]&&idx<=i) d.add(line(-i, qs[i-1]+dp[i-1].first, dp[i-1].second)), idx++;
        dp[i]={d.query(i).val(i)+i*p[i]-qs[p[i]-1]+lambda, d.query(i).cnt+1};
    }
    return dp[n];
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k>>s;
    for (int i=0; i<2*n; i++)
    {
        if (s[i]=='A') r++, h[c]=r;
        if (s[i]=='B') c++, h[c]=r;
    }
    for (int i=1; i<=n; i++)
    {
        qs[i]=qs[i-1]+h[i];
        while (idx<=i&&h[idx]<i) idx++;
        p[i]=idx;
    }
    ll l=0, r=1e12;
    while (l<r)
    {
        ll md=(l+r)/2;
        //cout<<md<<' '<<solve(md).first<<' '<<solve(md).second<<'\n';
        if (solve(md).second<=k) r=md;
        else l=md+1;
    }
    cout<<solve(l).first-k*l;
}

/*
(a.c-c.c)/(c.m-a.m)<(a.c-b.c)/(b.m-a.m)
*/

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -