|

General

# Author Problem Lang Verdict Time Memory Sent Judged
51453049 Practice:
vjudge3
939F - 31 GNU C++14 Accepted 46 ms 41504 KB 2019-03-18 18:42:56 2019-03-18 18:42:56

→ Source
#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]);
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?