Batch Scheduling

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, S, t[10001], f[10001];
int w(int i, int x) { return S*(f[N]-f[i]) + t[x]*(f[x]-f[i]); }

int main() {
    cin >> N >> S;

    t[0] = 0; f[0] = 0;
    for (int i=1; i <= N; i++) {
        cin >> t[i] >> f[i];
        t[i] += t[i-1];
        f[i] += f[i-1];
    }

    int dp[N+1]; dp[0] = 0;

    vector<pair<int, int> > v; // start pos, best-k
    v.push_back(make_pair(0, 0));

    for (int x=1; x <= N; x++) {
        // Find the value of dp[x]
        int k = (--lower_bound(v.begin(), v.end(), make_pair(x+1, 0)))->second;
        dp[x] = dp[k] + w(k, x);

        // Update the segments
        for (int i = v.size()-1; i >= 0; i--) {
            int y = v[i].first, oldk = v[i].second;
            // Case 1
            if (y > x && dp[x] + w(x, y) < dp[oldk] + w(oldk, y))
                v.pop_back();
            // Case 2
            else {
                int lo = y+1, hi = N+1;
                while(lo < hi) {
                    int mid = (lo+hi)/2;
                    if (dp[x] + w(x, mid) <= dp[oldk] + w(oldk, mid))
                        hi = mid;
                    else
                        lo = mid+1;
                }
                if (hi != N+1) v.push_back(make_pair(hi, x));
                break;
            }
        }
        if (v.size() == 0)
            v.push_back(make_pair(0, x));
    }
    cout << dp[N] << endl;
    return 0;
}