№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
132524583 |
Дорешивание:
GJHTLAb |
939F
- 31
|
C++14 (GCC 6-32)
|
Полное решение
|
46 мс
|
44496 КБ
|
2021-10-20 15:03:09 |
2021-10-20 15:03:09 |
|
#include<bits/stdc++.h>
using namespace std;
int n,k,h,t,dp[110][100010],q[100010];
int main(){
memset(dp,0x3f,sizeof(dp));
scanf("%d%d",&n,&k);
dp[0][0]=0;
for(int i=1;i<=k;i++){
int l,r;
scanf("%d%d",&l,&r);
for(int j=0;j<=n;j++)
dp[i][j]=dp[i-1][j];
h=1,t=0;
for(int j=r;~j;j--){
while(h<=t&&q[h]<l-j) h++;
while(h<=t&&dp[i][q[t]]>dp[i][r-j]) t--;
q[++t]=r-j;
dp[i][j]=min(dp[i][j],dp[i-1][q[h]]+1);
}
h=1,t=0;
for(int j=0;j<=min(r,n);j++){
while(h<=t&&q[h]<j-r+l) h++;
while(h<=t&&dp[i][q[t]]>dp[i][j]) t--;
q[++t]=j;
dp[i][j]=min(dp[i][j],dp[i-1][q[h]]+2);
}
}
if(dp[k][n]==0x3f3f3f3f) printf("Hungry\n");
else printf("Full\n%d\n",dp[k][n]);
return 0;
}
Время: ? ms, память: ? КБ