# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
35615446 |
Practice:
skruch |
939F
- 31
|
C++14 (GCC 6-32)
|
Accepted
|
31 ms
|
86392 KB
|
2018-02-24 08:23:18 |
2018-02-24 08:23:18 |
|
#include<bits/stdc++.h>
using namespace std;
const int N=200005,inf=2e8;
struct node{int l,r;}e[N];
int n,m,f[105][N],q[N],l,r;
inline void solve(int t){
for(int i=0;i<=n;i++)f[t][i]=f[t-1][i];
l=1;r=0;
for(int i=0;i<=e[t].r;i++){
while(l<=r && q[l]<i-(e[t].r-e[t].l))l++;
if(l<=r)f[t][i]=min(f[t][i],f[t-1][q[l]]+2);
if(i<=n){
while(l<=r && f[t-1][i]<=f[t-1][q[r]])r--;
q[++r]=i;
}
}
l=1;r=0;q[++r]=0;
for(int i=e[t].r;i>=0;i--){
if(e[t].r-i<=n){
while(l<=r && f[t-1][e[t].r-i]<=f[t-1][q[r]])r--;
q[++r]=e[t].r-i;
}
while(l<=r && q[l]<e[t].l-i)l++;
if(l<=r)f[t][i]=min(f[t][i],f[t-1][q[l]]+1);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&e[i].l,&e[i].r);
for(int i=1;i<=n;i++)f[0][i]=N;f[0][0]=0;
for(int i=1;i<=m;i++)solve(i);
if(f[m][n]<N)printf("Full\n%d\n",f[m][n]);
else puts("Hungry");
return 0;
}
Click to see test details