# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
96446918 |
Practice:
UltiMadow |
939F
- 31
|
GNU C++11
|
Accepted
|
46 ms
|
3920 KB
|
2020-10-23 15:58:47 |
2020-10-23 15:58:47 |
|
#include<bits/stdc++.h>
#define MAXN 200010
using namespace std;
int n,K,L[MAXN],R[MAXN];
int f[MAXN],g[MAXN];
int q[MAXN],l,r;
int main(){
scanf("%d%d",&n,&K);
for(int i=1;i<=K;i++)scanf("%d%d",&L[i],&R[i]);
memset(f,0x3f,sizeof(f));f[0]=0;
for(int i=1;i<=K;i++){
memcpy(g,f,sizeof(g));l=1,r=0;
for(int j=R[i];j>=0;j--){
while(l<=r&&g[q[r]]>=g[R[i]-j])r--;
q[++r]=R[i]-j;
while(l<=r&&q[l]<L[i]-j)l++;
f[j]=min(f[j],g[q[l]]+1);
}l=1,r=0;
for(int j=0;j<=R[i];j++){
while(l<=r&&g[q[r]]>=g[j])r--;
q[++r]=j;
while(l<=r&&q[l]<j+L[i]-R[i])l++;
f[j]=min(f[j],g[q[l]]+2);
}
}
if(f[n]==0x3f3f3f3f)printf("Hungry\n");
else printf("Full\n%d\n",f[n]);
return 0;
}
Click to see test details