?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
114067718 |
Practice: chengyufeng |
939F - 31 | C++17 (GCC 9-64) | Accepted | 31 ms | 1196 KB | 2021-04-24 05:45:13 | 2021-04-24 05:45:13 |
#include<bits/stdc++.h> #define N 100005 using namespace std; int q[N],f[N],g[N],n,k; int s[105],t[105]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) scanf("%d%d",s+i,t+i); memset(f,0x3f,sizeof(f)); f[0]=0; for(int i=1;i<=k;i++) { for(int j=0;j<=n;j++) g[j]=f[j]; int l=1,r=0,le=t[i]-s[i]; for(int j=0;j<=n&&j<=t[i];j++) { while(l<=r&&j-q[l]>le) l++; while(l<=r&&g[q[r]]>=g[j]) r--; q[++r]=j; f[j]=min(f[j],g[q[l]]+2); if(t[i]-j<=n) f[t[i]-j]=min(f[t[i]-j],g[q[l]]+1); } } if(f[n]<=k*2) printf("Full\n%d",f[n]); else puts("Hungry"); }
?
?
?
?