开long long
by rhn7 @ 2024-01-30 15:36:17
@[zhanghui2021](/user/699348) 不开longlong见祖宗
by Hoks @ 2024-01-30 16:04:59
@[rhn7](/user/760998) @[Hoks](/user/551100) 开long long全WA
by zhanghui2021 @ 2024-01-30 16:48:01
@[zhanghui2021](/user/699348) 啊,你对比下我的看看?
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f3f3f3f3f;
int n,m;
int h[N],a[N],x[N],dp[N];
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void){
int x(0),t(1);char fc(getchar());
while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
return x*t;
}
inline void print(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) h[i]=read(),a[i]=read(),dp[i]=INF;dp[0]=0;
for(int i=1,s=0,dt=0,l=1,r=1;i<=n;i++)
{
s+=a[i];while(s>m) s-=a[dt],dt++;
while(l<=r&&x[l]<dt) l++;
while(l<=r&&h[x[r]]<=h[i]) r--;x[++r]=i;
for(int j=l;j<=r-1;j++) dp[i]=min(dp[i],dp[x[j]]+h[x[j+1]]);
dp[i]=min(dp[i],dp[dt-1]+h[x[l]]);
}
print(dp[n]);
return 0;
}
```
by Hoks @ 2024-01-30 16:53:17
反正WA的那个点答案是超int的/cf
by Hoks @ 2024-01-30 16:53:37
@[Hoks](/user/551100) 谢谢
by zhanghui2021 @ 2024-01-30 16:59:54