|

General

# Author Problem Lang Verdict Time Memory Sent Judged
35615446 Practice:
skruch
939F - 31 GNU C++14 Accepted 31 ms 86392 KB 2018-02-24 08:23:18 2018-02-24 08:23:18

→ Source
#include<bits/stdc++.h>
using namespace std;
const int N=200005,inf=2e8;
struct node{int l,r;}e[N];
int n,m,f[105][N],q[N],l,r;
inline void solve(int t){
for(int i=0;i<=n;i++)f[t][i]=f[t-1][i];
l=1;r=0;
for(int i=0;i<=e[t].r;i++){
while(l<=r && q[l]<i-(e[t].r-e[t].l))l++;
if(l<=r)f[t][i]=min(f[t][i],f[t-1][q[l]]+2);
if(i<=n){
while(l<=r && f[t-1][i]<=f[t-1][q[r]])r--;
q[++r]=i;
}
}
l=1;r=0;q[++r]=0;
for(int i=e[t].r;i>=0;i--){
if(e[t].r-i<=n){
while(l<=r && f[t-1][e[t].r-i]<=f[t-1][q[r]])r--;
q[++r]=e[t].r-i;
}
while(l<=r && q[l]<e[t].l-i)l++;
if(l<=r)f[t][i]=min(f[t][i],f[t-1][q[l]]+1);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&e[i].l,&e[i].r);
for(int i=1;i<=n;i++)f[0][i]=N;f[0][0]=0;
for(int i=1;i<=m;i++)solve(i);
if(f[m][n]<N)printf("Full\n%d\n",f[m][n]);
else puts("Hungry");
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
Checker comment
?
Diagnostics
?
Click to see test details