11001번: 김치 - 최적화 필요

https://www.acmicpc.net/problem/11001

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5;
typedef long long ll;
struct line {
    int a, b;
}c[MAX_N];
vector<line> dq[MAX_N * 4];
int n, d, t[MAX_N], ft[MAX_N * 4];
ll ans;
double cross(line i, line j) { return (double)(j.b - i.b) / (i.a - j.a); }
void init(int h, int l, int r) {
    for (int i = l; i <= r; i++) {
        while (dq[h].size()>1 && cross(c[i], dq[h][dq[h].size() - 1])
              >cross(dq[h][dq[h].size() - 1], dq[h][dq[h].size() - 2])) dq[h].pop_back();
        dq[h].push_back(c[i]);
    }
    if (l == r) return;
    init(h * 2 + 1, l, (l + r) / 2);
    init(h * 2 + 2, (l + r) / 2 + 1, r);
}
ll query(int h, int l, int r, int gl, int gr, int x) {
    if (r<gl || gr<l) return -0x7fffffffffffffffLL;
    if (gl <= l && r <= gr) {
        while (dq[h].size() - ft[h]>1 && cross(dq[h][ft[h]], dq[h][ft[h] + 1])>x) ft[h]++;
        return (ll)dq[h][ft[h]].a*x + dq[h][ft[h]].b;
    }
    return max(query(h * 2 + 1, l, (l + r) / 2, gl, gr, x),
        query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x));
}
int main() {
    scanf("%d %d", &n, &d);
    for (int i = 0; i<n; i++) scanf("%d", t + i);
    for (int i = 0, v; i<n; i++) {
        scanf("%d", &v);
        c[i] = { -i,v };
    }
    init(0, 0, n - 1);
    for (int i = 0; i<n; i++)
        ans = max(ans, query(0, 0, n - 1, max(0, i - d), i, t[i]) + (ll)t[i] * i);
    printf("%lld", ans);
    return 0;
}