Codeforces 311B Cats Transport

처음으로 기울기를 사용하여 DP 최적화
양단 대기열로 이전의 dp값을 유지합니다.
코드:

#include
using namespace std;

typedef long long ll;
typedef pair PII;
const int N = 1e5+5;

ll sum[N]{0}, a[N], dp[N], f[N];
int Q[N];

int main() {
    int n, m, p, h;
    cin >> n >> m >> p;
    for(int i = 1; i < n; i++) { scanf("%lld", &f[i]); sum[i+1] = sum[i]+f[i];}
    for(int i = 1; i <= m; i++) { scanf("%d%lld", &h, &a[i]); a[i] -= sum[h]; }
    sort(a+1, a+m+1);
    for(int i = m; i >= 1; i--) a[i] -= a[1];
    for(int i = 1; i <= m; i++) {
        sum[i] = sum[i-1]+a[i];
        dp[i] = a[i]*i-sum[i];
    }

    for(int j = 1; j < p; j++) {
        for(int i = 1; i <= m; i++) f[i] = dp[i]+sum[i];
        int h = 0, t = -1;
        for(int i = 1; i <= m; i++) {
            while(h(f[i]-f[Q[t]])*(Q[t]-Q[t-1])) --t;
            Q[++t] = i;
            dp[i] = f[Q[h]]+a[i]*(i-Q[h])-sum[i];
        }
    }
    printf("%lld
", dp[m]);
    return 0;
}