?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
108876106 |
Practice: wish2lucky |
939F - 31 | C++17 (GCC 9-64) | Accepted | 31 ms | 2284 KB | 2021-03-02 15:38:32 | 2021-03-02 15:38:32 |
#include<cstring> #include<cstdio> #define N 100010 #define INF 0x3f3f3f3f #define Min(a,b) (a<b?a:b) int h,t,q[N<<1]; int n,K,l,r,f[2][N<<1]; int main(){ memset(f[0],0x3f,sizeof(f[0])); f[0][0]=0; scanf("%d%d",&n,&K); for(int i=1;i<=K;++i){ scanf("%d%d",&l,&r); for(int j=0;j<=n;++j) f[i&1][j]=f[!(i&1)][j]; h=1; t=0; //下面枚举的对应题解中 r-(j+k) 中 j+k 的值 for(int j=r;j>=0;--j){ while(h<=t&&q[h]<l-j) ++h; while(h<=t&&f[!(i&1)][q[t]]>f[!(i&1)][r-j]) --t; q[++t]=r-j; f[i&1][j]=Min(f[i&1][j],f[!(i&1)][q[h]]+1); } h=1; t=0; //下面枚举的对应题解中 j-k 的值 for(int j=0,mj=Min(n,r);j<=mj;++j){ while(h<=t&&q[h]<j-r+l) ++h; while(h<=t&&f[!(i&1)][q[t]]>f[!(i&1)][j]) --t; q[++t]=j; f[i&1][j]=Min(f[i&1][j],f[!(i&1)][q[h]]+2); } } if(f[K&1][n]==INF)printf("Hungry\n"); else printf("Full\n%d\n",f[K&1][n]); }
?
?
?
?