# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
36428159 |
Practice:
Vingying0 |
939F
- 31
|
GNU C++11
|
Accepted
|
46 ms
|
86440 KB
|
2018-03-20 11:45:17 |
2018-03-20 11:45:17 |
|
#include <bits/stdc++.h>
using namespace std;
const int N=200050;
const int INF=0x3f3f3f3f;
int dp[105][N];
int x,n,K,ans;
int q[N],head,tail;
int main(){
memset(dp,INF,sizeof dp);ans=INF;
cin>>n>>K;
dp[0][0]=0;
while(K--){
x^=1;
int l,r;
cin>>l>>r;
int up=min(n,r);
memcpy(dp[x],dp[x^1],sizeof dp[x]);
head=1,tail=0;
for(int j=0;j<=up;++j){
while(head<=tail&&dp[x^1][q[tail]]>=dp[x^1][j])--tail;
while(head<=tail&&q[head]<j-r+l)++head;
q[++tail]=j;
dp[x][j]=min(dp[x][j],dp[x^1][q[head]]+2);
}
head=1,tail=0;
for(int j=r;j>=0;--j){
while(head<=tail&&dp[x^1][q[tail]]>=dp[x^1][r-j])--tail;
while(head<=tail&&q[head]<l-j)++head;
q[++tail]=r-j;
dp[x][j]=min(dp[x][j],dp[x^1][q[head]]+1);
}
}
if(dp[x][n]==INF)puts("Hungry");
else printf("Full\n%d",dp[x][n]);
return 0;
}
Click to see test details