# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
54967782 |
Practice:
vjudge2 |
939F
- 31
|
MS C++
|
Accepted
|
31 ms
|
2356 KB
|
2019-06-02 10:13:26 |
2019-06-02 10:13:26 |
|
#include <cstring>
#include <iostream>
using namespace std;
int n, k, x, y, l, r, f[200001], g[200001], a[200001];
int main() {
scanf("%d%d", &n, &k);
memset(f, 0x3f, sizeof(f)), memset(g, 0x3f, sizeof(g));
f[0] = 0, g[0] = 0;
for (; k; k--) {
scanf("%d%d", &x, &y);
l = 1, r = 0;
for (int i = 0; i <= min(n, y); i++) {
while ((l <= r) && (f[a[r]] >= f[i])) r--;
r++;
a[r] = i;
while ((l <= r) && (a[l] <= i - (y - x + 1))) l++;
g[i] = min(g[i], f[a[l]] + 2);
}
l = 1, r = 0;
for (int i = y; i >= 0; i--) {
while ((l <= r) && (f[a[r]] >= f[y - i])) r--;
while ((l <= r) && (a[l] <= x - i - 1)) l++;
r++;
a[r] = y - i;
g[i] = min(g[i], f[a[l]] + 1);
}
memcpy(f, g, sizeof(f));
}
if (f[n] >= 0x3f3f3f3f) printf("Hungry\n");
else printf("Full\n%d\n", f[n]);
return 0;
}
Click to see test details