大佬求调,0pts
查看原帖
大佬求调,0pts
1259871
jkZJM110211楼主2025/7/31 09:40
#include <bits/stdc++.h>
using namespace std;
const int M = 3e5+4;
long long t[M], f[M];
long long sum_t[M], sum_f[M];    
long long dp[M];
int main() {
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
        cin >> t[i] >> f[i];
    }
    for (int i = 1; i <= n; ++i) {
        sum_t[i] = sum_t[i - 1] + t[i];
        sum_f[i] = sum_f[i - 1] + f[i];
    }
    int q[M], h = 0, e = 0;
    q[e++] = 0;
    for (int i = 1; i <= n; ++i) {
        while (e - h >= 2) {
            int j1 = q[h];
            int j2 = q[h + 1];
            if (dp[j1] - dp[j2] >= (sum_f[j1] - sum_f[j2]) * (s + sum_t[i])) {
                h++;
            } else {
                break;
            }
        }
        int j = q[h];
        dp[i] = dp[j] + (s + sum_t[i] - sum_t[j]) * (sum_f[i] - sum_f[j]);
        while (e - h >= 2) {
            int j1 = q[e - 2];
            int j2 = q[e - 1];
            if ((dp[j2] - dp[j1]) * (sum_f[i] - sum_f[j2]) >= (dp[i] - dp[j2]) * (sum_f[j2] - sum_f[j1])) {
                e--;
            } else {
                break;
            }
        }
        q[e++] = i;
    }
    cout << dp[n];
    return 0;
}
2025/7/31 09:40
加载中...