AcWing 300. 任务安排1（ 前缀和 dp优化）

思路：

代码：

#include
#include
#include
#define int long long
using namespace std;
const int N=5010;
int n,f[N],sumt[N],sumc[N],s;
//f[i][j]=f[k][j-1]+(t[1]+...+t[i]+j*s)*(c[k+1]+...+c[i])
signed main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        int t,c;
        cin>>t>>c;
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j