?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
107263301 |
Practice: chenyifanlx |
939F - 31 | C++17 (GCC 7-32) | Accepted | 46 ms | 10580 KB | 2021-02-13 10:49:21 | 2021-02-13 10:49:21 |
#include<bits/stdc++.h> using namespace std; int n,k,l[105],r[105],f[2][900005],q[900005],h,t,m,i,j; int main(){ scanf("%d%d",&n,&k); for(i=1;i<=k;++i)scanf("%d%d",&l[i],&r[i]); for(i=1;i<=n;++i)f[0][i]=1e9; for(i=1;i<=k;++i){ h=1;t=0; for(j=0;j<=n;++j)f[m^1][j]=f[m][j]; for(j=0;j<=min(n,r[i]);++j){ while(h<=t&&j-r[i]+l[i]>q[h])++h; while(h<=t&&f[m][j]<=f[m][q[t]])--t; q[++t]=j;f[m^1][j]=min(f[m^1][j],f[m][q[h]]+2); } h=1;t=0; for(j=r[i];j>=0;--j){ while(h<=t&&l[i]-j>q[h])++h; while(h<=t&&f[m][r[i]-j]<=f[m][q[t]])--t; q[++t]=r[i]-j;f[m^1][j]=min(f[m^1][j],f[m][q[h]]+1); } m^=1; } if(f[m][n]>=1e9)puts("Hungry"); else printf("Full\n%d",f[m][n]); return 0; }
?
?
?
?