№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
56956758 |
Дорешивание:
lyonlu |
939F
- 31
|
GNU C++11
|
Полное решение
|
46 мс
|
1588 КБ
|
2019-07-13 08:04:10 |
2019-07-13 08:04:10 |
|
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int maxn=200005,INF=0x3f3f3f3f;
int n,k,p,f[2][maxn];
deque<int> q;
int main()
{
scanf("%d%d",&n,&k);
fill(f[0]+1,f[0]+n+1,INF);
while(k--)
{
int l,r;
scanf("%d%d",&l,&r);
p^=1;
q.clear();
memcpy(f[p],f[p^1],sizeof(f[p]));
for(int j=0;j<=min(n,r);j++)
{
while(!q.empty()&&q.front()<j-(r-l)) q.pop_front();
while(!q.empty()&&f[p^1][j]<=f[p^1][q.back()]) q.pop_back();
q.push_back(j);
f[p][j]=min(f[p][j],f[p^1][q.front()]+2);
}
q.clear();
for(int j=r;j>=0;j--)
{
while(!q.empty()&&q.front()<l-j) q.pop_front();
while(!q.empty()&&f[p^1][r-j]<=f[p^1][q.back()]) q.pop_back();
q.push_back(r-j);
f[p][j]=min(f[p][j],f[p^1][q.front()]+1);
}
}
if(f[p][n]!=INF) printf("Full\n%d\n",f[p][n]);
else puts("Hungry");
return 0;
}
Время: ? ms, память: ? КБ