# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
57870298 |
Practice:
lopare |
939F
- 31
|
GNU C++11
|
Accepted
|
46 ms
|
7440 KB
|
2019-07-28 04:11:48 |
2019-07-28 04:11:48 |
|
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[3][300005],n,k,q[1000005];
int main()
{
scanf("%d%d",&n,&k);
memset(f,127,sizeof(f));
f[0][0]=0;
int opt=0;
for(int i=1;i<=k;i++)
{
opt=!opt;
int l,r,h=1,t=0;
scanf("%d%d",&l,&r);
for(int j=0;j<=r;j++)
{
if(j<=n)
{
while(h<=t&&f[!opt][j]<=f[!opt][q[t]])t--;
q[++t]=j;
}
while(h<=t&&q[h]<j-(r-l))h++;
f[opt][j]=min(f[!opt][j],f[!opt][q[h]]+2);
}
h=1,t=0;
for(int j=r;j>=0;j--)
{
if(r-j<=n)
{
while(h<=t&&f[!opt][r-j]<=f[!opt][q[t]])t--;
q[++t]=r-j;
}
while(h<=t&&q[h]<l-j)h++;
f[opt][j]=min(f[opt][j],f[!opt][q[h]]+1);
}
}
if(f[opt][n]>1000000)printf("Hungry");
else
printf("Full\n%d",f[opt][n]);
return 0;
}
Click to see test details