oj.uz

답안 #15263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15263 2015-07-12T04:52:09 Z ainta 달리는 게임 (kriii3_E) C++
26 / 70
 1000 ms 33172 KB 
#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);
        }
        else break;
        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);
        }
        else break;
        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+1, 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
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 32776 KB Output is correct
2 Correct 0 ms 32776 KB Output is correct
3 Correct 0 ms 32776 KB Output is correct
4 Correct 0 ms 32776 KB Output is correct
5 Correct 0 ms 32776 KB Output is correct
6 Correct 0 ms 32776 KB Output is correct
7 Correct 0 ms 32776 KB Output is correct
8 Correct 0 ms 32776 KB Output is correct
9 Correct 0 ms 32776 KB Output is correct
10 Correct 0 ms 32776 KB Output is correct
11 Correct 0 ms 32776 KB Output is correct
12 Correct 0 ms 32776 KB Output is correct
13 Correct 0 ms 32776 KB Output is correct
14 Correct 0 ms 32776 KB Output is correct
15 Correct 0 ms 32776 KB Output is correct
16 Correct 0 ms 32776 KB Output is correct
17 Correct 0 ms 32776 KB Output is correct
18 Correct 2 ms 32776 KB Output is correct

Subtask #2
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 32776 KB Output is correct
2 Correct 33 ms 32776 KB Output is correct
3 Correct 41 ms 32776 KB Output is correct
4 Correct 77 ms 32776 KB Output is correct
5 Correct 107 ms 33172 KB Output is correct
6 Correct 82 ms 32776 KB Output is correct
7 Correct 456 ms 32776 KB Output is correct
8 Execution timed out 1000 ms 32908 KB Program timed out
9 Halted 0 ms 0 KB -