Submission #19181

#	Time	Username	Problem	Language	Result	Execution time	Memory
19181		tncks0121	달리는 게임 (kriii3_E)	C++14	70 / 70	286 ms	32608 KiB

E

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

#define debug(format, ...) printf(format, __VA_ARGS__);

const int N_ = 1000500;

int N;

ll A[N_];
ll S1[N_], S2[N_];

ll cost (int l, int r) {
    return (S2[r] - S2[l-1]) - (S1[r] - S1[l-1]) * (l-1);
}

struct line {
    ll a, b;
    line (ll a = 0, ll b = 0): a(a), b(b) { }
    ll y (ll x) { return a * x + b; }
};

lf intersection (line p, line q) {
    return (lf)(q.b - p.b) / (p.a - q.a);
}

struct CHT {
    vector<line> stk;

    void add (line p) { // 기울기 증가
        while(stk.size() >= 2 && intersection(stk.back(), p) <= intersection(stk[stk.size()-2], p))
            stk.pop_back();
        stk.push_back(p);
    }

    ll get (ll x) { // 들쭉날쭉
        int low = 0, high = (int)stk.size() - 2;
        int pos = (int)stk.size() - 1;
        ll ret = (ll)-1e18;
        while(low <= high) {
            int mid = (low + high) >> 1;
            lf p = intersection(stk[mid], stk[mid + 1]);
            ret = max(ret, stk[mid].y(x));
            if(p > x) {
                high = mid - 1;
                pos = mid;
            }else {
                low = mid + 1;
            }
        }

        for(int i = pos-5; i <= pos+5; i++) {
            if(0 <= i && i < stk.size())
                ret = max(ret, stk[i].y(x));
        }

        return ret;
    }
} cht;

ll tb[N_];

int main() {
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        scanf("%lld", A+i);
        S1[i] = S1[i-1] + A[i];
        S2[i] = S2[i-1] + i * A[i];
    }

    cht.add(line(0, 0));
    for(int i = 1; i <= N; i++) {
        tb[i] = max(tb[i-1], cht.get(-S1[i]) + S2[i]);
        cht.add(line(i, (-S2[i] + S1[i] * i + tb[i])));


        /*for(int j = 0; j < i; j++) {
            ll val = 
                - (S1[i]) * j
                + (-S2[j] + S1[j] * j + tb[j])
                + S2[i];
            tb[i] = max(tb[i], val);
        }*/
    }

    printf("%lld\n", tb[N]);
    return 0;
}

• Subtask 1: 26 / 26
• Subtask 2: 44 / 44