Submission #92773

#	Time	Username	Problem	Language	Result	Execution time	Memory
92773		SamAnd	Divide and conquer (IZhO14_divide)	C++17	100 / 100	136 ms	9592 KiB

divide

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct ban
{
    long long x,g,d;
};
struct ban1
{
    long long y,i;
};
bool operator<(const ban1 a,const ban1 b)
{
    if(a.y<b.y)
        return true;
    if(a.y>b.y)
        return false;
    return a.i<b.i;
}
const int N=100005;

int n;
ban a[N];
long long pg[N],pd[N];
ban1 t[N];
long long minu[N];
int byn(long long y)
{
    int l=1,r=n-1;
    while((r-l)>3)
    {
        int m=(l+r)/2;
        if(t[m].y>y)
            r=m;
        else
            l=m;
    }
    for(int i=r;i>=l;--i)
        if(t[i].y<=y)
            return i;
}
int main()
{
    //freopen("divide.in","r",stdin);
    //freopen("divide.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i].x>>a[i].g>>a[i].d;
    a[0].x=-1;
    a[0].g=0;
    a[0].d=0;
    ++n;

    for(int i=1;i<n;++i)
        pg[i]=pg[i-1]+a[i].g;
    for(int i=1;i<n;++i)
        pd[i]=pd[i-1]+a[i].d;

    for(int i=1;i<n;++i)
    {
        t[i].i=i;
        t[i].y=pd[i-1]-a[i].x;
    }
    sort(t+1,t+n);
    minu[1]=t[1].i;
    for(int i=2;i<n;++i)
        minu[i]=min(minu[i-1],t[i].i);

    long long ans=0;
    for(int i=1;i<n;++i)
    {
        long long y=pd[i]-a[i].x;
        int j=byn(y);
        ans=max(ans,pg[i]-pg[minu[j]-1]);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int byn(long long int)':
divide.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52