POJ 1180

1180.cpp

#include <cstdio>
#include <vector>
#include <deque>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long int LLI;
typedef pair<LLI, LLI> Pair; // (a, b) := ax+b
deque<Pair> lines;

int n;
LLI s;
LLI sumt[10001];
LLI sumf[10001];
LLI dp[10001]; // dp[m] := the minimum cost when disposing of 1 ~ m

int main() {
    scanf("%d", &n);
    scanf("%lld", &s);
    for (int i=1; i<=n; i++) {
        LLI t, f;

        scanf("%lld %lld", &t, &f);
        sumt[i] = sumt[i-1] + t;
        sumf[i] = sumf[i-1] + f;
    }

    lines.push_back(Pair(sumf[n], s*sumf[n]));
    for (int i=1; i<=n; i++) {
        LLI m1, a1;
        LLI m2, a2;
        LLI m3, a3;

        while (lines.size() > 1) {
            m1 = lines[0].first;
            a1 = lines[0].second;
            m2 = lines[1].first;
            a2 = lines[1].second;
            if (m1*sumt[i] + a1 >= m2*sumt[i] + a2) lines.pop_front();
            else break;
        }

        m1 = lines[0].first;
        a1 = lines[0].second;
        dp[i] = m1*sumt[i] + a1;
        m3 = sumf[n]-sumf[i];
        a3 = dp[i] + (s-sumt[i])*(sumf[n]-sumf[i]);

        while (lines.size() > 1) {
            m1 = lines[lines.size()-2].first;
            a1 = lines[lines.size()-2].second;
            m2 = lines[lines.size()-1].first;
            a2 = lines[lines.size()-1].second;
            if ((m2-m1) * (a3-a2) >= (a2-a1) * (m3-m2)) lines.pop_back();
            else break;
        }

        lines.push_back(Pair(m3, a3));
    }

    printf("%lld\n", dp[n]);
}