\(i\) elementi bilan tugaydigan eng yaxshi (maksimal yig'indili) bo'lakni saqlab boramiz:

\(cur_i = \max(a_i,\; cur_{i-1} + a_i)\)

Ya'ni oldingi bo'lakka \(a_i\) ni qo'shib davom ettiramiz, yoki agar bu foydasiz bo'lsa, \(i\) dan yangi bo'lak boshlaymiz. Javob — barcha \(cur_i\) ning eng kattasi. Murakkablik \(O(n)\), xotira \(O(1)\). Bu Kadane algoritmi.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long max_sum = LLONG_MIN;
    long long current_sum = 0;

    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        current_sum += a;
        max_sum = max(max_sum, current_sum);
        if (current_sum < 0) current_sum = 0;
    }

    cout << max_sum << endl;
    return 0;
}

Barcha ishlarni tugash vaqti \(r_i\) bo'yicha o'sish tartibida saralab olamiz. \(E\) o'zgaruvchisi orqali hozirgacha tanlangan oxirgi ishning tugash vaqtini saqlab boramiz (dastlab \(E = 0\), chunki hali birorta ham ish tanlanmagan). Shundan so'ng, tartiblangan ishlarni birma-bir ko'rib chiqib, quyidagi ochko'zlik (greedy) qoidasini qo'llaymiz:

Agar joriy ishning boshlanish vaqti \(l_i \ge E\) bo'lsa (ya'ni bu ish oldingi tanlangan ish tugagach yoki u bilan bir vaqtda boshlansa, demak ular bir-biriga xalaqit bermaydi) — bu ishni tanlaymiz va \(E\) qiymatini yangi ishning tugash vaqtiga o'zgartiramiz: \(E \gets r_i\).

Aks holda (agar bu ish oxirgi tanlangan ish tugagunicha boshlanib qolsa va to'qnash kelsa) — bu ishni o'tkazib yuboramiz.

Amalga oshirish: ishlarni \(r_i\) bo'yicha saralash — \(O(n \log n)\), so'ngra bitta chiziqli o'tish — \(O(n)\). Umumiy murakkablik \(O(n \log n)\), xotira \(O(n)\) — bu \(n\) juda katta bo'lganda ham (masalan \(10^6\)) vaqt chegarasiga bemalol sig'adi.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    if(scanf("%d", &n) != 1) return 0;
    vector<pair<long long,long long>> jobs(n);
    for(int i = 0; i < n; i++){
        long long l, r;
        scanf("%lld %lld", &l, &r);
        jobs[i] = {r, l};
    }
    sort(jobs.begin(), jobs.end());

    long long e = LLONG_MIN;
    int count = 0;
    for(int i = 0; i < n; i++){
        long long r = jobs[i].first;
        long long l = jobs[i].second;
        if(l >= e){
            count++;
            e = r;
        }
    }
    printf("%d\n", count);
    return 0;
}

Panelning oxirgi ustunini ikki xil usulda yopish mumkin: bitta vertikal domino (qoladi \(2\times(n-1)\)) yoki ikkita gorizontal domino (qoladi \(2\times(n-2)\)). Demak:

\(ways(n) = ways(n-1) + ways(n-2)\), \(ways(0)=ways(1)=1\)

Bu Fibonachchi ketma-ketligi (siljigan indeks bilan): \(ways(n) = F(n+1)\).

\(n \le 10^{18}\) bo'lgani uchun oddiy iteratsiya ishlamaydi — tez ikkilantirish (fast doubling) ishlatiladi:

\(F(2k) = F(k)\cdot\big(2F(k+1) - F(k)\big)\), \(F(2k+1) = F(k)^2 + F(k+1)^2\)

Har bir so'rov \(O(\log n)\) da hisoblanadi, \(q\) ta so'rovda jami \(O(q\log n)\). Hisoblashlar \(10^9+7\) moduli bo'yicha olib boriladi.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

pair<long long,long long> fibPair(long long n){
    if(n == 0) return {0, 1};
    auto p = fibPair(n >> 1);
    long long a = p.first, b = p.second;
    long long two_b_minus_a = ((2 * b) % MOD - a % MOD + MOD) % MOD;
    long long c = (a * two_b_minus_a) % MOD;
    long long d = (a * a % MOD + b * b % MOD) % MOD;
    if(n & 1LL) return {d, (c + d) % MOD};
    else return {c, d};
}

long long fib(long long n){
    return fibPair(n).first;
}

int main(){
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++){
        long long n;
        scanf("%lld", &n);
        printf("%lld\n", fib(n + 1));
    }
    return 0;
}

Agar \(s\) va \(t\) da uzunligi \(L\) bo'lgan umumiy qism-satr mavjud bo'lsa, u holda uzunligi \(L\) dan kichik bo'lgan umumiy qism-satr ham albatta mavjud (masalan, o'sha topilgan qism-satrning o'zining bir qismini olish orqali). Demak, javob "monoton" xususiyatga ega — buni javobni binary search qilish orqali topish mumkin: mumkin bo'lgan uzunlik \(L\) ni \([0, \min(n,m)]\) oralig'ida binary search qilamiz, har bir \(L\) uchun "uzunligi \(L\) bo'lgan umumiy qism-satr bormi?" degan savolga tez javob beramiz.

Bitta \(L\) uchun tekshirish (heshlash yordamida). \(s\) ning barcha uzunligi \(L\) bo'lgan qism-satrlarining heshini (rolling hash / polinomial hash) hisoblab, hammasini bitta to'plamga (hash-set) joylaymiz — bu \(O(n)\) vaqt oladi (har bir qism-satr heshi prefiks-hesh massivi yordamida \(O(1)\) da hisoblanadi). So'ngra \(t\) ning har bir uzunligi \(L\) bo'lgan qism-satrining heshini hisoblab, u to'plamda bor-yo'qligini tekshiramiz — yana \(O(m)\). Agar mos kelish topilsa, demak uzunligi \(L\) bo'lgan umumiy qism-satr mavjud.

Heshlash kollizhiyasi (turli qism-satrlar bir xil heshga ega bo'lib qolishi) ehtimolini kamaytirish uchun katta tub modul (yoki ikkita mustaqil modul bilan "double hashing") ishlatiladi.

Umumiy murakkablik. Binary search \(O(\log(\min(n,m)))\) qadam qiladi, har bir qadamda tekshirish \(O(n+m)\) vaqt oladi — jami \(O((n+m)\log(\min(n,m)))\). Bu \(n, m\) juda katta bo'lganda ham (masalan \(2\times10^5\)) vaqt chegarasiga bemalol sig'adi.

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long u64;
typedef __int128 u128;

const u64 MOD = (1ULL << 61) - 1;
const u64 BASE = 131542391ULL;

u64 mulmod(u64 a, u64 b){
    return (u64)((u128)a * (u128)b % MOD);
}
u64 addmod(u64 a, u64 b){
    u64 s = a + b;
    if(s >= MOD) s -= MOD;
    return s;
}
u64 submod(u64 a, u64 b){
    return a >= b ? a - b : a + MOD - b;
}

vector<u64> buildPow(int n){
    vector<u64> pw(n + 1);
    pw[0] = 1;
    for(int i = 1; i <= n; i++) pw[i] = mulmod(pw[i-1], BASE);
    return pw;
}

vector<u64> buildPrefix(const string &s, const vector<u64> &pw){
    int n = s.size();
    vector<u64> P(n + 1, 0);
    for(int i = 0; i < n; i++){
        P[i+1] = addmod(mulmod(P[i], BASE), (u64)(s[i]));
    }
    return P;
}

u64 getHash(const vector<u64> &P, const vector<u64> &pw, int l, int r){
    return submod(P[r], mulmod(P[l], pw[r-l]));
}

int n, m;
string s, t;
vector<u64> pw, Ps, Pt;

bool check(int L){
    if(L == 0) return true;
    unordered_set<u64> seen;
    seen.reserve((size_t)(n - L + 1) * 2);
    for(int i = 0; i + L <= n; i++){
        seen.insert(getHash(Ps, pw, i, i + L));
    }
    for(int j = 0; j + L <= m; j++){
        if(seen.count(getHash(Pt, pw, j, j + L))) return true;
    }
    return false;
}

int main(){
    scanf("%d %d", &n, &m);
    {
        char buf[200005];
        scanf("%s", buf);
        s = buf;
    }
    {
        static char buf2[200005];
        scanf("%s", buf2);
        t = buf2;
    }

    int maxlen = max(n, m);
    pw = buildPow(maxlen);
    Ps = buildPrefix(s, pw);
    Pt = buildPrefix(t, pw);

    int lo = 0, hi = min(n, m), ans = 0;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(check(mid)){
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Klassik yukxalta masalasida odatda DP og'irlik o'lchami bo'yicha quriladi: \(dp[j]\) — sig'imi \(j\) bo'lgan yukxaltada erishish mumkin bo'lgan maksimal qiymat. Bu usul \(O(n \cdot W)\) vaqt oladi va \(W\) kichik bo'lganda juda samarali ishlaydi.

Ammo \(W\) juda katta bo'lsa-yu (masalan \(10^9\)), lekin barcha buyumlar qiymatlarining yig'indisi (\(v_1+v_2+\dots+v_n\)) unchalik katta bo'lmasa, DP ni teskari yo'nalishda — qiymat o'lchami bo'yicha qurish mumkin:

\(dp[j]\) = qiymati aynan \(j\) ga teng bo'lgan buyumlar to'plamini tanlash uchun kerak bo'lgan minimal umumiy og'irlik

Boshlang'ich holat: \(dp[0] = 0\), qolgan barcha \(dp[j] = \infty\) (bunday qiymatga hali erishib bo'lmagan).

Har bir buyumni (\(w_i, v_i\)) navbat bilan ko'rib chiqamiz va \(j\) ni yig'indi qiymatining maksimal mumkin bo'lgan chegarasidan pastga qarab (0/1 xossasini saqlash uchun, har bir buyum faqat bir marta hisobga olinishi kerak) yangilaymiz:

\(dp[j] = \min\big(dp[j],\; dp[j - v_i] + w_i\big)\)

Barcha buyumlarni qayta ishlab bo'lgach, javob — \(dp[j] \le W\) shartini qanoatlantiruvchi eng katta \(j\) (ya'ni qiymat yig'indisi \(j\) ga erishish uchun kerak bo'lgan minimal og'irlik yukxaltaga sig'adigan eng katta \(j\)).

Murakkablik: DP massivining o'lchami — qiymatlar yig'indisi (\(V = v_1+\dots+v_n\)) ga teng, har bir buyum uchun \(O(V)\) ishlov beriladi, jami \(O(n \cdot V)\). Bu yondashuv \(W\) va \(w_i\) qanchalik katta bo'lishidan (hattoki \(10^9\) bo'lsa ham) mutlaqo bog'liq emas — faqat qiymatlar yig'indisi kichik bo'lishi muhim.

#include <bits/stdc++.h>
using namespace std;

const long long INF = (long long)4e18;

int main(){
    int n;
    long long W;
    scanf("%d %lld", &n, &W);
    vector<long long> w(n), v(n);
    long long sumV = 0;
    for(int i = 0; i < n; i++){
        scanf("%lld %lld", &w[i], &v[i]);
        sumV += v[i];
    }

    vector<long long> dp(sumV + 1, INF);
    dp[0] = 0;
    for(int i = 0; i < n; i++){
        long long vi = v[i], wi = w[i];
        for(long long j = sumV; j >= vi; j--){
            if(dp[j - vi] != INF && dp[j - vi] + wi < dp[j]){
                dp[j] = dp[j - vi] + wi;
            }
        }
    }

    long long best = 0;
    for(long long j = 0; j <= sumV; j++){
        if(dp[j] <= W) best = j;
    }
    printf("%lld\n", best);
    return 0;
}

Bekatlarni tugunlar, yo'llarni esa og'irlikli qirralar sifatida tasavvur qilsak, masala klassik eng qisqa yo' masalasiga aylanadi: \(1\)-tugundan \(n\)-tugungacha bo'lgan minimal og'irlikli yo'lni topish kerak.

Umumiy holat (og'irliklar ixtiyoriy musbat son). Bu — Dijkstra algoritmi uchun klassik holat. Har bir tugun uchun undan hozirgacha ma'lum bo'lgan eng qisqa masofani saqlaymiz. Navbat (priority queue / min-heap) yordamida har doim "hozircha eng yaqin" tugunni tanlab, undan chiqadigan qirralar orqali qo'shni tugunlarning masofasini yangilaymiz (agar yangi yo'l qisqaroq bo'lsa). Bir tugun navbatdan bir necha marta chiqishi mumkin (eskirgan yozuvlar), lekin har birini faqat birinchi (eng yaxshi) marta qayta ishlaymiz. Murakkabligi — \(O((n+m)\log n)\).

Maxsus holat (og'irliklar faqat 0 yoki 1). Bunda navbatni oddiy ikki tomonlama navbat (deque) bilan almashtirish mumkin — bu 0-1 BFS deb ataladi: agar qirraning og'irligi 0 bo'lsa, qo'shni tugunni navbatning boshiga qo'shamiz (chunki masofa o'zgarmaydi — darhol qayta ishlash kerak); agar og'irlik \(1\) bo'lsa, navbatning oxiriga qo'shamiz. Bu holda navbat har doim "kengayish darajasi" bo'yicha tartiblangan bo'lib qoladi (heap kerak emas), va murakkablik navbatning \(O(\log n)\) operatsiyalari o'rniga oddiy \(O(1)\) operatsiyalar bilan \(O(n+m)\) ga tushadi — bu heap bilan Dijkstraga qaraganda tezroq va katta hajmdagi tarmoqlarda muhim ustunlik beradi.

Amaliy maslahat: yagona yechim yozib, avval barcha qirralarning og'irligi \(0\) yoki \(1\) ekanligini tekshirib olish, so'ng mos usulni (0-1 BFS yoki heap bilan Dijkstra) tanlash — bu yechimni barcha holatlar uchun ishonchli va tez qiladi.

Agar \(n\)-tugunga hech qanday yo'l bilan yetib bo'lmasa (tarmoq bo'laklarga bo'lingan bo'lsa), uning masofasi "cheksiz" holatda qoladi — bunda \(-1\) chiqariladi.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<pair<int,long long>>> adj(n + 1);
    bool allZeroOne = true;
    vector<array<long long,3>> edges(m);
    for(int i = 0; i < m; i++){
        int u, v; long long w;
        scanf("%d %d %lld", &u, &v, &w);
        edges[i] = {u, v, w};
        if(w != 0 && w != 1) allZeroOne = false;
    }
    for(int i = 0; i < m; i++){
        int u = edges[i][0], v = edges[i][1];
        long long w = edges[i][2];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    const long long INF = LLONG_MAX / 2;
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;

    if(allZeroOne){
        deque<int> dq;
        vector<char> visited(n + 1, 0);
        dq.push_back(1);
        while(!dq.empty()){
            int u = dq.front(); dq.pop_front();
            if(visited[u]) continue;
            visited[u] = 1;
            for(auto &e : adj[u]){
                int v = e.first; long long w = e.second;
                if(dist[u] + w < dist[v]){
                    dist[v] = dist[u] + w;
                    if(w == 0) dq.push_front(v);
                    else dq.push_back(v);
                }
            }
        }
    } else {
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        pq.push({0, 1});
        while(!pq.empty()){
            auto [d, u] = pq.top(); pq.pop();
            if(d > dist[u]) continue;
            for(auto &e : adj[u]){
                int v = e.first; long long w = e.second;
                if(d + w < dist[v]){
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    if(dist[n] >= INF) printf("-1\n");
    else printf("%lld\n", dist[n]);
    return 0;
}

Avval oddiy DP tuzamiz: \(dp[k][i]\) — massivning dastlabki \(i\) ta elementini aynan \(k\) ta bo'lakka bo'lishning eng kichik narxi. O'tish:

\(dp[k][i]\) = \(\min_{k-1 \le j < i}\Big( dp[k-1][j] + (pref_i - pref_j)^2 \Big)\)

bu yerda \(pref\) — massivning prefiks yig'indilari. Javob — \(dp[K][n]\). Bu DP \(O(n^2 K)\) ishlaydi, bu kichik \(n\) uchun yetarli, lekin katta \(n\) da juda sekin.

Tezlashtirish g'oyasi. Narx funksiyasi \(w(j, i) = (pref_i - pref_j)^2\) to'rtburchak tengsizligi (quadrangle inequality) xususiyatiga ega: \(l_1 \le l_2 \le r_1 \le r_2\) bo'lganda \(w(l_1,r_1)+w(l_2,r_2) \le w(l_1,r_2)+w(l_2,r_1)\). Bu xususiyat tufayli, har bir \(k\)-qatlam uchun \(i\) ortib borishi bilan optimal o'tish nuqtasi \(opt(i)\) ham monoton ortib boradi (kamaymaydi). Ya'ni \(opt(1) \le opt(2) \le \dots \le opt(n)\).

Shu monotonlikdan foydalanib, har bir \(k\)-qatlam uchun \(dp[k][\cdot]\) massivini Divide & Conquer usulida hisoblaymiz: \(solve(lo, hi, optlo, opthi)\) funksiyasi \([lo, hi]\) oralig'idagi barcha \(i\) larning optimal o'tish nuqtasi \([optlo, opthi]\) oralig'ida yotishini bilib, o'rtadagi \(mid = (lo+hi)/2\) uchun optimal \(j\) ni to'g'ridan-to'g'ri (chiziqli qidiruv bilan) \([optlo, opthi]\) orasidan topadi, so'ng chap yarimni \([optlo, bestJ]\) bilan, o'ng yarimni \([bestJ, opthi]\) bilan rekursiv chaqiradi. Monotonlik tufayli har bir qatlam uchun umumiy ish hajmi \(O(n \log n)\) ga tushadi (odatiy \(O(n^2)\) o'rniga).

Natijada barcha \(K\) qatlam uchun umumiy murakkablik \(O(nK \log n)\) bo'ladi — bu \(O(n^2 K)\) ga qaraganda ancha tezroq.

Amalga oshirish bo'yicha eslatma: rekursiyani stek (yoki oddiy rekursiv funksiya) yordamida amalga oshirish mumkin. Har bir \((lo, hi, optlo, opthi)\) chaqiruvida faqat \([optlo, \min(opthi, mid-1)]\) oralig'i bo'ylab chiziqli qidiruv qilinadi — bu intervallarning yig'indisi butun qatlam uchun \(O(n \log n)\) ni tashkil qiladi.

Massiv elementlari va \(n\) qiymatlari shunday tanlanganki, oraliq yig'indilar kvadrati \(\mathrm{long\ long}\) (64-bitli butun son) chegarasidan chiqib ketmaydi.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 2;

int n, K;
vector<ll> pref;
vector<ll> dpPrev, dpCur;

inline ll cost(int j, int i) {
    ll s = pref[i] - pref[j];
    return s * s;
}

void solve(int lo, int hi, int optlo, int opthi) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    ll best = INF;
    int bestJ = optlo;
    int upper = min(opthi, mid - 1);
    for (int j = optlo; j <= upper; j++) {
        if (dpPrev[j] >= INF) continue;
        ll val = dpPrev[j] + cost(j, mid);
        if (val < best) {
            best = val;
            bestJ = j;
        }
    }
    dpCur[mid] = best;
    solve(lo, mid - 1, optlo, bestJ);
    solve(mid + 1, hi, bestJ, opthi);
}

int main() {
    scanf("%d %d", &n, &K);
    pref.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        pref[i] = pref[i - 1] + x;
    }

    dpPrev.assign(n + 1, INF);
    dpPrev[0] = 0;
    for (int k = 1; k <= K; k++) {
        dpCur.assign(n + 1, INF);
        solve(k, n, k - 1, n - 1);
        dpPrev = dpCur;
    }

    printf("%lld\n", dpPrev[n]);
    return 0;
}