# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
121396555 |
Practice:
LHN200861 |
939F
- 31
|
GNU C++11
|
Accepted
|
31 ms
|
83312 KB
|
2021-07-05 15:54:32 |
2021-07-05 15:54:32 |
|
#include<bits/stdc++.h>
using namespace std;
deque<int>q;
int f[105][200005];
int main()
{
int i,j,n,k,l,r;
memset(f[0],0x3f,sizeof(f[0]));
f[0][0]=0;
cin>>n>>k;
for(i=1;i<=k;i++)
{
cin>>l>>r;
for(j=0;j<=n;j++)
f[i][j]=f[i-1][j];
while(!q.empty())q.pop_back();
for(j=r;j>=0;j--)
{
while(!q.empty()&&q.front()<l-j)q.pop_front();
while(!q.empty()&&f[i-1][q.back()]>f[i-1][r-j])q.pop_back();
q.push_back(r-j);
f[i][j]=min(f[i][j],f[i-1][q.front()]+1);
}
while(!q.empty())q.pop_back();
for(j=0;j<=min(n,r);j++)
{
while(!q.empty()&&q.front()<j-r+l)q.pop_front();
while(!q.empty()&&f[i-1][q.back()]>f[i-1][j])q.pop_back();
q.push_back(j);
f[i][j]=min(f[i][j],f[i-1][q.front()]+2);
}
}
if(f[k][n]==0x3f3f3f3f)
puts("Hungry");
else
{
puts("Full");
cout<<f[k][n]<<endl;
}
return 0;
}
Click to see test details