# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
108764066 |
Practice:
caocao11 |
939F
- 31
|
GNU C++11
|
Accepted
|
62 ms
|
82988 KB
|
2021-03-01 05:00:59 |
2021-03-01 05:00:59 |
|
#include<bits/stdc++.h>
#define L long long
#define ld long double
using namespace std;
int l[105],r[105],sta[200005],f[105][200005];
int main(){
int i,j,k,m,n,h,t;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d",&l[i],&r[i]);
memset(f,0x3f3f3f3f,sizeof(f));
f[0][0]=0;
for(i=1;i<=m;i++){
h=1,t=0;
for(j=0;j<=n;j++) f[i][j]=f[i-1][j];
for(j=0;j<=min(n,r[i]);j++){
while(h<=t&&sta[h]<j-(r[i]-l[i])) h++;
while(h<=t&&f[i-1][sta[t]]>=f[i-1][j]) t--;
sta[++t]=j;
f[i][j]=min(f[i][j],f[i-1][sta[h]]+2);
}
h=1,t=0;
for(j=r[i];j>=0;j--){
while(h<=t&&sta[h]<l[i]-j) h++;
while(h<=t&&f[i-1][sta[t]]>=f[i-1][r[i]-j]) t--;
sta[++t]=r[i]-j;
f[i][j]=min(f[i][j],f[i-1][sta[h]]+1);
}
}
if(f[m][n]==0x3f3f3f3f) printf("Hungry");
else
printf("Full\n%d",f[m][n]);
return 0;
}
Click to see test details