oj.uz

Submission #852120

# Submission time Handle Problem Language Result Execution time Memory
852120 2023-09-21T09:18:36 Z danikoynov Chorus (JOI23_chorus) C++14
0 / 100
 1 ms 8668 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll maxn = 1e6 + 10;
const ll inf = 1e18;

ll n, k;
string s;

ll pos[2][maxn], pref[maxn];
/// ll dp[maxn][maxn];
/**

*/

void chmin(ll &var, ll val) /// careful for long long
{
    var = min(var, val);
}

int pre_cost[maxn];

void precompute()
{
    for (int i = 1; i <= n; i ++)
    {
        int above = (i - 1) * 2;
        int lf = i, rf = n;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (pos[0][mf] > above + (mf - i + 1))
                rf = mf - 1;
            else
                lf = mf + 1;
        }
        pre_cost[i] = lf;
    }
}
ll cost(ll left, ll right)
{
    if (pre_cost[left] > right)
        return 0;

        ll lf = pre_cost[left];
    ll above = (left - 1) * 2;

    ll sum = pref[right] - pref[lf - 1];
    sum = sum - (right - lf + 1) * above;
    ll len = right - left + 1;
    ll sm = lf - left;
    sum = sum - (len) * (len + 1) / 2;
    sum = sum + (sm) * (sm + 1) / 2;

    return sum;

}

/**void divide(ll row, ll left, ll right, ll optl, ll optr)
{
    if (left > right)
        return;

    ll mid = (left + right) / 2;
    ll opt = -1;
    for (ll j = optl; j <= min(optr, mid); j ++)
    {
        ll cur = dp[j - 1][row - 1] + costd[j][mid];
        if (cur < dp[mid][row])
        {
            dp[mid][row] = cur;
            opt = j;
        }
    }

    divide(row, left, mid - 1, optl, opt);
    divide(row, mid + 1, right, opt, optr);
}*/



ll dp[maxn], f[maxn];

ll get_better(int i, int j)
{
    int lf = 1, rf = n;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (dp[i - 1] + cost(i, mf) > dp[j - 1] + cost(j, mf))
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    return lf;
}
pair < ll, ll > calc_dp(ll group_cost)
{
    for (int i = 1; i <= n; i ++)
    {
        dp[i] = inf;
        f[i] = 0;
    }
    deque < pair < int, int > > dq;
    for (int i = 1; i <= n; i ++)
    {
        while(dq.size() > 1)
        {
            int last = dq.back().first;
            int bef = dq[dq.size() - 2].first;
            if (dq[dq.size() - 2].second < get_better(bef, last))
            {
                dq.pop_back();
            }
            else
            {
                break;
            }
        }
        if (!dq.empty())
            dq.back().second = get_better(dq.back().first, i);
        dq.push_back({i, 0});

        while(dq.size() > 1)
        {
            int fs = dq[0].first;
            int sc = dq[1].first;
            if (get_better(fs, sc) <= i)
                dq.pop_front();
            else
                break;
        }

        dp[i] = dp[dq[0].first - 1] + cost(dq[0].first, i) + group_cost;
        f[i] = f[dq[0].first - 1] + 1;

        /**for (int j = 1; j <= i; j ++)
        {
            ll cur = dp[j - 1] + cost(j, i) + group_cost;
            if (cur < dp[i])
            {
                dp[i] = cur;
                f[i] = f[j - 1] + 1;
            }
        }*/
    }


    return {dp[n], f[n]};
}
void solve()
{
    cin >> n >> k >> s;

    s = "#" + s;
    ll cntA = 0, cntB = 0;
    for (ll i = 1; i <= 2 * n; i ++)
    {
        if (s[i] == 'A')
        {
            cntA ++;
            pos[0][cntA] = i;
            pref[cntA] = pref[cntA - 1] + i;
        }
        else
        {
            cntB ++;
            pos[1][cntB] = i;
        }
    }

    ///for (ll i = 0; i <= n; i ++)
       // for (ll j = 0; j <= n; j ++)
         //   dp[i][j] = 4 * n * n; /// careful for overflow

    /**ll cr = 0;
    for (ll j = 1; j <= n; j ++)
    {
        cr = cr + pos[0][j] - j;

        dp[j][1] = cr;
    }

    for (ll j = 2; j <= k; j ++)

    {
        divide(j, j, n, j, n);
    }*/

    precompute();
    ll lf = 0, rf = n * n / 2;
    while(lf <= rf)
    {
        ll mf = (lf + rf) / 2;
        pair < ll, ll > cur = calc_dp(mf);
        if (cur.second <= k)
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    if (rf < 0)
    {
        pair < ll, ll > cur = calc_dp(0);
        cout << cur.first << endl;
        return;
    }
    pair < ll, ll > fs = calc_dp(rf);
    pair < ll, ll > ds = calc_dp(rf + 1);

    ll fs_val = fs.first - fs.second * rf;
    ll ds_val = ds.first - ds.second * (rf + 1);

    double part = (double)(fs.second - k) / (double)(fs.second - ds.second); /// remember to cast
    double ans = (double)(fs_val) + part * (double)(ds_val - fs_val);
    ///cout << ds.first << "  " << ds.second << endl;
    ///cout << fs.first << "  " << fs.second << endl;
    cout << (ll)(round(ans)) << endl;
}

int main()
{
    speed();
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}

Compilation message

chorus.cpp: In function 'll cost(ll, ll)':
chorus.cpp:60:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   60 |     if (pre_cost[left] > right)
      |     ^~
chorus.cpp:63:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |         ll lf = pre_cost[left];
      |         ^~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8656 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Incorrect 1 ms 8668 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8656 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Incorrect 1 ms 8668 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8656 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Incorrect 1 ms 8668 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8656 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Incorrect 1 ms 8668 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8656 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Incorrect 1 ms 8668 KB Output isn't correct
16 Halted 0 ms 0 KB -