// Autor: Ríša Hladík #include #include #include #include struct interval { int l, r; } *a; struct record { int pos, val; } *dp; // dp bude setříděné vzestupně jak podle pos, tak podle val. // Každá položka p bude říkat "do času p.pos (včetně) se dá optimálně naspat // p.val hodin". // Když budeme pro nějaký konkrétní čas chtít zjistit, kolik se do něj dá // naspat, stačí binárně vyhledat nejbližší nižší čas v dp. // komparátor pro qsort, řadí intervaly vzestupně podle pravého konce static int cmp(const void *p, const void *q) { return ((struct interval *)p)->r - ((struct interval *)q)->r; } int bs(int x, int l, int r) { int best = 0; while (l <= r) { int c = (l + r) / 2; if (dp[c].pos <= x) best = c, l = c + 1; else r = c - 1; } return best; } static inline int max(int a, int b) { return (a > b) ? a : b; } int main(void) { int N; scanf("%d", &N); a = malloc(N * sizeof(*a)); // pro stručnost vynecháváme kontrolu, že se malloc povedl, načítání vstupu funguje atd. for (int i = 0; i < N; i++) scanf("%d %d", &a[i].l, &a[i].r); qsort(a, N, sizeof(*a), cmp); dp = calloc(N + 1, sizeof(*dp)); // calloc funguje jako malloc, ale paměť nuluje int pos = 0; // pos ukazuje na poslední spočítanou hodnotu dp for (int i = 0; i < N; i++) { // projdeme intervaly podle pravých konců zleva doprava if (dp[pos].pos < a[i].r) { // pokud aktuální interval končí víc vpravo, než všechny předchozí pos++; // vytvoříme pro něj nový záznam dp[pos].pos = a[i].r; dp[pos].val = dp[pos - 1].val; // umíme určitě naspat tolik, jako s menším časem } int best = bs(a[i].l, 0, pos); // najdeme, kolik toho můžeme naspat před začátkem aktuálního intervalu dp[pos].val = max(dp[pos].val, dp[best].val + a[i].r - a[i].l); } printf("%d\n", dp[pos].val); }