oj.uz

Submission #15267

# Submission time Handle Problem Language Result Execution time Memory
15267 2015-07-12T05:05:44 Z hodduc 달리는 게임 (kriii3_E) C++
70 / 70
 173 ms 44052 KB 
#include<stdio.h>
int N;
long long s[1000001], v[1000001], ss[1000001];
long long bound[1000001];
long long d[1000001];

int stack[1000001], top;
int main()
{
        scanf("%d", &N);
        for(int i=1; i<=N; i++) scanf("%lld", &v[i]);
        for(int i=1; i<=N; i++) s[i]=s[i-1]+v[i];

        for(int i=1; i<=N; i++){
                ss[i] = ss[i-1] + v[i]*i;
        }

        for(int i=1; i<=N; i++){
                while(top && s[stack[top]] <= s[i]){
                        top--;
                }
                if(top) {
                        bound[i] = stack[top] + 1;
                } else {
                        bound[i] = 0;
                }

                stack[++top] = i;
        }

        for(int i=1; i<=N; i++)
        {
                d[i] = d[i-1];
                if (v[i] < 0) continue;

                int lb = bound[i];
//              printf("%lld %lld", s[i], s[lb-1]);
//              printf(" %d ", lb);
                long long tmp = ss[i] - ss[lb];
                tmp -= (s[i] - s[lb]) * (lb);
                tmp += d[lb];
                //printf("%d %lld %d %lld\n", i, tmp, lb, d[lb]);
                if (tmp > d[i]) d[i] = tmp;
        }

        printf("%lld\n", d[N]);

        return 0;
}

Subtask #1
26.0 / 26.0

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

Subtask #2
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 44052 KB Output is correct
2 Correct 9 ms 44052 KB Output is correct
3 Correct 12 ms 44052 KB Output is correct
4 Correct 19 ms 44052 KB Output is correct
5 Correct 17 ms 44052 KB Output is correct
6 Correct 23 ms 44052 KB Output is correct
7 Correct 98 ms 44052 KB Output is correct
8 Correct 170 ms 44052 KB Output is correct
9 Correct 173 ms 44052 KB Output is correct