Submission #157010

#	Time	Username	Problem	Language	Result	Execution time	Memory
157010		combi1k1	Cake 3 (JOI19_cake3)	C++14	0 / 100	2 ms	504 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define int long long

const int   N   = 2e5 + 1;
const int   inf = 1e9 + 7;

typedef pair<int,int>   ii;

ii  f[N];
ii  T[N];
int n, m;

ii  work(int M) {
    ii  cur = ii(0,0);
    ii  res = ii(0,0);

    for(int i = 1 ; i <= n ; ++i)   {
        int B = cur.X + T[i].Y - 2 * T[i].X - M;
        int C = cur.Y + 1;
        if (C == 1)
            B += 2 * T[i].X;

        f[i] = ii(B,C);

        cur = max(cur,ii(B + 2 * T[i].X,C));
        res = max(res,ii(B,C));
    }

    return  res;
}

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for(int i = 1 ; i <= n ; ++i)
        cin >> T[i].Y >> T[i].X;

    sort(T + 1,T + 1 + n);

    int L = 0;
    int R = inf;

    while (L < R)   {
        int M = (L + R) / 2;
        ii  cur = work(M);
        if (cur.Y <= m)
            R = M;
        else
            L = M + 1;
    }

    ii  res = work(L);

    cout << res.X + L * m << endl;
}
/*
8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76