# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
129048940 |
Practice:
QQH |
939F
- 31
|
C++14 (GCC 6-32)
|
Accepted
|
46 ms
|
86636 KB
|
2021-09-17 11:30:28 |
2021-09-17 11:30:28 |
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,m,i,q[N],f[105][N];
int main(){
memset(f[0],0x3f,sizeof(f[0]));
f[0][0]=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int l,r,he=1,ta=0;
scanf("%d%d",&l,&r);
memcpy(f[i],f[i-1],sizeof(f[i]));
for(int j=r;j>=0;j--){
while(he<=ta&&q[he]<l-j)he++;
while(he<=ta&&f[i-1][q[ta]]>f[i-1][r-j])ta--;
q[++ta]=r-j;
f[i][j]=min(f[i][j],f[i-1][q[he]]+1);
}
he=1,ta=0;
for(int j=0;j<=min(r,n);j++){
while(he<=ta&&q[he]<j+l-r)he++;
while(he<=ta&&f[i-1][q[ta]]>f[i-1][j])ta--;
q[++ta]=j;
f[i][j]=min(f[i][j],f[i-1][q[he]]+2);
}
}
if(f[m][n]==0x3f3f3f3f)puts("Hungry");
else printf("Full\n%d",f[m][n]);
return 0;
}
Click to see test details