Submission #1241657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241657		trantrungkein	Watching (JOI13_watching)	C++20	0 / 100	1 ms	324 KiB

watching

#include <bits/stdc++.h>
#define int long long 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;
 
const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 2e5 + 1;
int n,a[N],P,Q;
bool check(int mid)
{   //cout << mid << endl;
    int l = 1,pos1 = 1, pos2 = 1,r = 1, max1 = 1, max2 = 1, numP = P, numQ = Q, ok = 1;
    while(ok)
    {   r++;
        if(a[r] - a[l] + 1<= mid) max1++, pos1 = r;
        if(a[r] - a[l] + 1<= 2*mid) max2++, pos2 = r;
        
        if(a[r] - a[l] + 1 > 2*mid || r == n)
        {   
           // cout << l <<' ' << r <<' ' << max1 <<' ' << max2 << endl;
            if(max1 == max2 && numP != 0)
            {
                r = l = pos1+1;
               // cout << pos1 + 1 <<' ' << endl;
                numP--;
            }
            else if(numQ != 0)
            {
                r = l = pos2+1;
                //cout << pos2 + 1 << endl;
                numQ--;
            }
            if(l > n) {ok = 0;break;}
            if(numQ == 0 && numP == 0) {break;}
            pos1 = pos2 = l;
            max1 = max2 = 1;
        }
        //if(P == 0 && Q == 0)
    }
    return (ok == 0);
}
signed main(){
    cin >> n >> P >> Q;
    For(i,1,n) cin >> a[i];
    a[n+1] = 1e16;
    int l = 1, r = 1e18, kq = -1;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(check(mid)) r = mid - 1, kq = mid;
        else l = mid + 1;
    }
    cout << kq;
}

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50