oj.uz

Submission #902723

# Submission time Handle Problem Language Result Execution time Memory
902723 2024-01-11T01:39:39 Z Tuanlinh123 Chorus (JOI23_chorus) C++17
16 / 100
 3 ms 6612 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
 
const long long inf=1e6, maxn=1e6+5;
long long cnt[maxn], to[maxn];
long long n, k, dp[maxn], pre[maxn];
 
struct Lichao
{
    ll div(ll x){return (x -!!(x % 2))/2;}

    struct node
    {
        pair<pair<long long, long long>, ll> line;
        ll l=-1, r=-1;
        node(long long a, long long b, int idx): line({a, b}, idx){}
        pair<long long, ll> eval(ll x){return {line.fi.fi*x+line.fi.se, line.se};}
    };
    vector<node> tree;

    const ll MAXV = 1'000'000;
    void insert(long long a, long long b, ll idx)
    {
        node c(a, b, idx);
        if (tree.empty())
        {
            tree.push_back(c);
            return;
        }
        ll tidx=0, Start=-MAXV, End=MAXV;
        while (Start<=End)
        {
            ll mid=div(Start+End);
            bool l=c.eval(Start).fi<tree[tidx].eval(Start).fi;
            bool m=c.eval(mid).fi<tree[tidx].eval(mid).fi;
            if (mid) swap(c.line, tree[tidx].line);
            if (Start==End) return;
            if (l!=m)
            {
                End=mid-1;
                if (tree[tidx].l==-1)
                {
                    tree[tidx].l=tree.size();
                    tree.push_back(c);
                    return;
                }
                tidx=tree[tidx].l;
            }
            else
            {
                Start=mid+1;
                if (tree[tidx].r==-1)
                {
                    tree[tidx].r=tree.size();
                    tree.push_back(c);
                    return;
                }
                tidx=tree[tidx].r;
            }
        }
    }

    pair<long long, ll> query(ll x)
    {
        pair<long long, ll> ans={LLONG_MAX, 0};
        ll tidx = 0, Start = -MAXV, End = MAXV;
        while (Start<=End && tidx!=-1)
        {
            ans=min(ans, tree[tidx].eval(x));
            ll mid = div(Start+End);
            if (x==mid) return ans;
            if (x<mid) End=mid-1, tidx=tree[tidx].l;
            else Start=mid+1, tidx = tree[tidx].r;
        }
        return ans;
    }
};
 
pair<long long, ll> solve(long long C)
{
    ll crr=1;
    Lichao A; A.insert(0, -pre[to[0]-1], 0);
    for (ll i=1; i<=n; i++)
        dp[i]=inf*inf, cnt[i]=0;
    for (ll i=1; i<=n; i++)
    {
        while (crr<i && to[crr]<=i)
            A.insert(-crr, -(pre[to[crr]-1]-(to[crr]-1)*crr)+dp[crr], cnt[crr]), crr++;
        tie(dp[i], cnt[i])=A.query(i); 
        dp[i]+=C+pre[i], cnt[i]++;
        if (crr<i && dp[crr]+C<dp[i])
            dp[i]=dp[crr]+C, cnt[i]=cnt[crr]+1;
    }
    return {dp[n], cnt[n]};
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    string s; cin >> s;
    long long x=0, y=0, crr=1;
    for (ll i=0; i<n*2; i++)
    {
        if (s[i]=='A')
            x++, pre[x]=pre[x-1]+y;
        else y++;
    }
    for (ll i=1; i<=n; i++)
        while (crr<=pre[i]-pre[i-1])
            to[crr]=i, crr++;
    while (crr<=n) to[crr]=n+1, crr++;
    for (ll i=0; i<=n; i++)
        if (to[i]<=i)
            to[i]=i+1;
    long long lo=0, hi=1LL*n*n;
    while (hi>lo)
    {
        long long mid=(lo+hi)/2;
        if (solve(mid).se<=k)
            hi=mid;
        else lo=mid+1;
    }
    cout << 0LL+solve(lo).fi-lo*k;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6612 KB Output is correct
8 Correct 1 ms 6504 KB Output is correct
9 Correct 1 ms 6504 KB Output is correct
10 Correct 1 ms 6504 KB Output is correct
11 Correct 1 ms 6504 KB Output is correct
12 Correct 1 ms 6500 KB Output is correct
13 Correct 1 ms 6504 KB Output is correct
14 Correct 2 ms 6504 KB Output is correct
15 Correct 1 ms 6504 KB Output is correct
16 Correct 1 ms 6556 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6612 KB Output is correct
8 Correct 1 ms 6504 KB Output is correct
9 Correct 1 ms 6504 KB Output is correct
10 Correct 1 ms 6504 KB Output is correct
11 Correct 1 ms 6504 KB Output is correct
12 Correct 1 ms 6500 KB Output is correct
13 Correct 1 ms 6504 KB Output is correct
14 Correct 2 ms 6504 KB Output is correct
15 Correct 1 ms 6504 KB Output is correct
16 Correct 1 ms 6556 KB Output is correct
17 Correct 2 ms 6504 KB Output is correct
18 Correct 3 ms 6504 KB Output is correct
19 Correct 3 ms 6504 KB Output is correct
20 Correct 2 ms 6504 KB Output is correct
21 Incorrect 2 ms 6504 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6612 KB Output is correct
8 Correct 1 ms 6504 KB Output is correct
9 Correct 1 ms 6504 KB Output is correct
10 Correct 1 ms 6504 KB Output is correct
11 Correct 1 ms 6504 KB Output is correct
12 Correct 1 ms 6500 KB Output is correct
13 Correct 1 ms 6504 KB Output is correct
14 Correct 2 ms 6504 KB Output is correct
15 Correct 1 ms 6504 KB Output is correct
16 Correct 1 ms 6556 KB Output is correct
17 Correct 2 ms 6504 KB Output is correct
18 Correct 3 ms 6504 KB Output is correct
19 Correct 3 ms 6504 KB Output is correct
20 Correct 2 ms 6504 KB Output is correct
21 Incorrect 2 ms 6504 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6612 KB Output is correct
8 Correct 1 ms 6504 KB Output is correct
9 Correct 1 ms 6504 KB Output is correct
10 Correct 1 ms 6504 KB Output is correct
11 Correct 1 ms 6504 KB Output is correct
12 Correct 1 ms 6500 KB Output is correct
13 Correct 1 ms 6504 KB Output is correct
14 Correct 2 ms 6504 KB Output is correct
15 Correct 1 ms 6504 KB Output is correct
16 Correct 1 ms 6556 KB Output is correct
17 Correct 2 ms 6504 KB Output is correct
18 Correct 3 ms 6504 KB Output is correct
19 Correct 3 ms 6504 KB Output is correct
20 Correct 2 ms 6504 KB Output is correct
21 Incorrect 2 ms 6504 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6612 KB Output is correct
8 Correct 1 ms 6504 KB Output is correct
9 Correct 1 ms 6504 KB Output is correct
10 Correct 1 ms 6504 KB Output is correct
11 Correct 1 ms 6504 KB Output is correct
12 Correct 1 ms 6500 KB Output is correct
13 Correct 1 ms 6504 KB Output is correct
14 Correct 2 ms 6504 KB Output is correct
15 Correct 1 ms 6504 KB Output is correct
16 Correct 1 ms 6556 KB Output is correct
17 Correct 2 ms 6504 KB Output is correct
18 Correct 3 ms 6504 KB Output is correct
19 Correct 3 ms 6504 KB Output is correct
20 Correct 2 ms 6504 KB Output is correct
21 Incorrect 2 ms 6504 KB Output isn't correct
22 Halted 0 ms 0 KB -