?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
54967737 |
Practice: huangpeilun |
939F - 31 | GNU C++11 | Accepted | 31 ms | 2376 KB | 2019-06-02 10:11:56 | 2019-06-02 10:11:56 |
#include<bits/stdc++.h> 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; }
?
?
?
?