# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
51453049 |
Practice:
vjudge3 |
939F
- 31
|
C++14 (GCC 6-32)
|
Accepted
|
46 ms
|
41504 KB
|
2019-03-18 18:42:56 |
2019-03-18 18:42:56 |
|
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n,m,dp[105][100005];
int q[100005],h,t,l,r;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) dp[0][i] = inf;
dp[0][0]=0;
for (int i=1; i<=m; i++)
{
scanf("%d%d",&l,&r);
h=1, t=0;
for (int j=0; j<=n; j++) dp[i][j] = dp[i-1][j];
for (int j=0; j<=r; j++)
{
if (j<=n)
{
while (h<=t&&dp[i-1][j]<=dp[i-1][q[t]]) t--;
q[++t]=j;
}
while (h<=t&&q[h]<j-r+l) h++;
if (h<=t) dp[i][j] = min(dp[i][j], dp[i-1][q[h]]+2);
}
h=1,t=0;
for (int j=r; j>=0; j--)
{
if (r-j<=n)
{
while (h<=t&&dp[i-1][r-j]<=dp[i-1][q[t]]) t--;
q[++t]=r-j;
}
while (h<=t&&q[h]<l-j) h++;
if (h<=t) dp[i][j]=min(dp[i][j],dp[i-1][q[h]]+1);
}
}
if (dp[m][n]>=inf) puts("Hungry");
else printf("Full\n%d\n",dp[m][n]);
}
Click to see test details