Submission #15256

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15256	2015-07-12T04:43:41 Z	ainta	달리는 게임 (kriii3_E)	C++	0 / 70	5 ms	32776 KB

E

#include<stdio.h>
#include<algorithm>
#include<set>
#define SIT set<Seg>::iterator
using namespace std;
int n;
long long w[1010000], S[1010000], Sum[1010000], D[1010000];
struct Seg{
    long long a, b;
    bool operator<(const Seg &p)const{
        return a<p.a;
    }
};
set<Seg>Set;
double Inter(Seg p, Seg q){
    return ((double)p.b-q.b)/(q.a-p.a);
}
void Ins(Seg tp){
    SIT it1,it,it2, itt;
    Set.insert(tp);
    it = Set.find(tp);
    it2 = it;it2++;
    if(it != Set.begin() && it2 != Set.end()){
        it1 = it;it1--;
        if(Inter(*it,*it2) < Inter(*it1,*it2)){
            Set.erase(it);
            return;
        }
    }
    it2 = it;it2++;
    while(it2 != Set.end()){
        itt = it2;itt++;
        if(itt==Set.end())break;
        if(Inter(*it2, *itt) < Inter(*it, *itt)){
            Set.erase(it2);
        }
        it2=itt;
    }
    if(it==Set.begin())return;
    it1 = it;it1--;
    while(it1 != Set.begin()){
        itt = it1;itt--;
        if(Inter(*itt, *it1) > Inter(*itt, *it)){
            Set.erase(it1);
        }
        it1=itt;
    }
}
void Add(int a){
    Seg tp;
    tp.a = -a-1;
    tp.b = D[a] - Sum[a+1] + S[a+1]*(a+1);
    Ins(tp);
}
long long Res;
long long Gap(long long x, int p){
    if(Set.begin()->a == 0){
        return Set.begin()->a * x + Set.begin()->b;
    }
    int b = -p+2, e = -1, mid;
    SIT it, it2, r;
    Seg tp;
    it=Set.end();it--;r=it;
    while(b<=e){
        mid=(b+e)>>1;
        tp.a = mid+1, tp.b = 0;
        it = Set.lower_bound(tp);
        if(it == Set.begin()){
            b = mid+1;
            continue;
        }
        if(it == Set.end()){
            e = mid-1;
            continue;
        }
        it2 = it;it--;
        if(it->a * x + it->b >= it2->a * x + it2->b){
            r = it;
            e = mid-1;
        }
        else b = mid+1;
    }
    return r->a * x + r->b;
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&w[i]);
        S[i]=S[i-1]+w[i];
        Sum[i]=Sum[i-1]+w[i]*i;
    }
    Seg tp;
    tp.a=0,tp.b=0;
    Set.insert(tp);
    Add(0);
    for(i=1;i<=n;i++){
        D[i] = max(Gap(S[i], i) + Sum[i], D[i-1]);
        Res=max(Res,D[i]);
        if(i!=1)Add(i-1);
    }
    printf("%lld\n",Res);
}

Subtask #1

0.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	32776 KB	Output is correct
2	Incorrect	0 ms	32776 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-