矿物运输[辽宁2014年省队互测一]

SOL：

我们发现，如果我们选择开发K层的话，我们肯定是越早开发越好。所以O（N）暴力扫一遍就好了。

#include<bits/stdc++.h>
#define sight(c) ('0'<=c&&c<='9')
#define N 200007
#define int long long
using namespace std;
inline void read(int &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar()) x=x*10+c-48;
}
void write(int x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('
'); }
int n,W,WW,T,c[N],t[N],v[N],ans,V,g;
signed main() {
    //freopen("a.in","r",stdin);
    read(n);read(W);read(T); WW=W;
    for (int i=1;i<=n;i++) read(c[i]),read(t[i]),read(v[i]);
    ans=W;
    for (int i=1;i<=n;i++) {
        W-=c[i];T-=t[i];
        if (W<0) if (V) {g=(-W)/V+((-W)%V?1:0);T-=g;W+=V*g;} else break;
        if (T<0) break; W+=t[i]*V;V+=v[i];
        ans=max(ans,W+T*V);
    }
    writeln(ans-WW); return 0;
}