oj.uz

Submission #15440

# Submission time Handle Problem Language Result Execution time Memory
15440 2015-07-12T07:41:20 Z gs13068 달리는 게임 (kriii3_E) C++
70 / 70
 270 ms 35936 KB 
#include<cstdio>
#include<set>

long long a[1111111];
long long s[1111111];
long long ss[1111111];
long long d[1111111];

std::set<std::pair<long long,long long> > S;
std::set<std::pair<long long,long long> >::iterator it1,it2;
std::pair<long long,long long> P;

int main()
{
    double tx,ty;
    int i,j,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    S.insert(std::make_pair(0,0));
    for(i=n;i>=0;i--)
    {
        s[i]=s[i+1]+a[i];
        ss[i]=ss[i+1]+s[i+1];
        while(S.size()>=2)
        {
            it1=S.end();
            it1--;
            it2=it1;
            it2--;
            if(i*it1->first+it1->second>i*it2->first+it2->second)break;
            S.erase(it1);
        }
        it1=S.end();
        it1--;
        d[i]=i*it1->first+it1->second+ss[i];

        P=std::make_pair(s[i],d[i]-ss[i]-i*s[i]);

        it1=it2=S.lower_bound(std::make_pair(P.first,-9e18));
        if(it1!=S.end())
        {
            if(it1->first==P.first&&it1->second>=P.second)continue;
            if(it1!=S.begin())
            {
                it2--;
                tx=-1.*(it1->second-it2->second)/(it1->first-it2->first);
                ty=it1->first*tx+it1->second;
                if(ty>=P.first*tx+P.second)continue;
            }
        }
        while(1)
        {
            it1=it2=S.lower_bound(std::make_pair(P.first,-9e18));
            if(it1==S.end())break;
            if(it1->first==P.first&&it1->second<=P.second)
            {
                S.erase(it1);
                continue;
            }
            it2++;
            if(it2==S.end())break;
            tx=-1.*(it1->second-it2->second)/(it1->first-it2->first);
            ty=it1->first*tx+it1->second;
            if(ty<=P.first*tx+P.second)S.erase(it1);
            else break;
        }
        while(1)
        {
            it1=it2=S.lower_bound(std::make_pair(P.first,-1e18));
            if(it1==S.begin())break;
            it1--;
            if(it1==S.begin())break;
            it2=it1;
            it2--;
            tx=-1.*(it1->second-it2->second)/(it1->first-it2->first);
            ty=it1->first*tx+it1->second;
            if(ty<=P.first*tx+P.second)S.erase(it1);
            else break;
        }
        S.insert(std::make_pair(P.first,P.second));
    }
    printf("%lld\n",d[0]);
}

Subtask #1
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 35936 KB Output is correct
2 Correct 0 ms 35936 KB Output is correct
3 Correct 0 ms 35936 KB Output is correct
4 Correct 0 ms 35936 KB Output is correct
5 Correct 0 ms 35936 KB Output is correct
6 Correct 0 ms 35936 KB Output is correct
7 Correct 0 ms 35936 KB Output is correct
8 Correct 0 ms 35936 KB Output is correct
9 Correct 0 ms 35936 KB Output is correct
10 Correct 0 ms 35936 KB Output is correct
11 Correct 0 ms 35936 KB Output is correct
12 Correct 0 ms 35936 KB Output is correct
13 Correct 0 ms 35936 KB Output is correct
14 Correct 0 ms 35936 KB Output is correct
15 Correct 0 ms 35936 KB Output is correct
16 Correct 0 ms 35936 KB Output is correct
17 Correct 0 ms 35936 KB Output is correct
18 Correct 0 ms 35936 KB Output is correct

Subtask #2
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35936 KB Output is correct
2 Correct 15 ms 35936 KB Output is correct
3 Correct 7 ms 35936 KB Output is correct
4 Correct 30 ms 35936 KB Output is correct
5 Correct 24 ms 35936 KB Output is correct
6 Correct 14 ms 35936 KB Output is correct
7 Correct 114 ms 35936 KB Output is correct
8 Correct 234 ms 35936 KB Output is correct
9 Correct 270 ms 35936 KB Output is correct