Submission #15267

#	Time	Username	Problem	Language	Result	Execution time	Memory
15267		hodduc	달리는 게임 (kriii3_E)	C++98	70 / 70	173 ms	44052 KiB

E

#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 / 26
• Subtask 2: 44 / 44