int n;
bool a[LIM][LIM];
int b[LIM][LIM];
 
bool check(int x, int y, int u, int v) /// Check if this square is valid
{
    int sum = b[u][v] - b[u][y - 1] - b[x - 1][v] + b[x - 1][y - 1];
    return (sum == 0) || (sum == (u - x + 1) * (v - y + 1));
}
 
bool check(int scale) /// Check if the scaling is valid
{
    for (int lx = 1, rx = scale; lx <= n; lx += scale, rx += scale)
        for (int ly = 1, ry = scale; ly <= n; ly += scale, ry += scale)
            if (!check(lx, ly, rx, ry)) return false;
 
    return true;
}
 
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
 
    /// Input
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; j += 4)
        {
            char c;
            cin >> c;
 
            /// Decode a[i][j]
            int v = (c <= '9') ? c - '0' : c + 10 - 'A';
            a[i][j + 0] = v >> 3 & 1;
            a[i][j + 1] = v >> 2 & 1;
            a[i][j + 2] = v >> 1 & 1;
            a[i][j + 3] = v >> 0 & 1;
        }
    }
 
    /// Constructing partialsum table
    for (int i = 0; i <= n; ++i) b[i][0] = b[0][i] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
 
    /// Find answer
    for (int x = n; x >= 1; --x)
        if (n % x == 0 && check(x))
            return cout << x, 0;
 
    return 0;
}

int n;
bool a[LIM][LIM];
bool check(int scale) /// Check if this scaling is valid
{
    for (int lx = 1, rx = scale; lx <= n; lx += scale, rx += scale)
        for (int ly = 1, ry = scale; ly <= n; ly += scale, ry += scale)
            for (int x = lx; x <= rx; ++x)
                for (int y = ly; y <= ry; ++y)
                    if (a[x][y] != a[lx][ly])
                        return false;
 
    return true;
}
 
int main()
{
//    file("Test");
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
 
    /// Input
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; j += 4)
        {
            char c;
            cin >> c;
 
            /// Decode a[i][j]
            int v = (c <= '9') ? c - '0' : c + 10 - 'A';
            a[i][j + 0] = v >> 3 & 1;
            a[i][j + 1] = v >> 2 & 1;
            a[i][j + 2] = v >> 1 & 1;
            a[i][j + 3] = v >> 0 & 1;
        }
    }
 
    /// Find result
    for (int x = n; x >= 1; --x)
        if (n % x == 0 && check(x))
            return cout << x, 0;
 
    return 0;
}

Input:
0 0

Output:
1

Explain:
(0, 0, 0)

Input:
1 1

Output:
4

Explain:
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(1, 0, 0)

Input:
10 10

Output:
213

Input:
100 100

Output:
16616

Input:
1000 1000

Output:
1530920

Input:
10000 10000

Output:
150511618

Input:
100000 100000

Full Output:
15007668845

Output Modulo 1e9 + 7:
7668740

Input:
1000000 1000000

Full Output:
1500107530589

Output Modulo 1e9 + 7:
107520089

Input:
10000000 10000000

Full Output:
150001436760246

Output Modulo 1e9 + 7:
435710239

Input:
100000000 100000000

Full Output:
15000018512473629

Output Modulo 1e9 + 7:
407473503

Input:
1000000000 1000000000

Full Output:
1500000231875375222

Output Modulo 1e9 + 7:
375373675

Input:
10000000000 10000000000

Full Output:
?????????????????????

Output Modulo 1e9 + 7:
786369931

Input:
100000000000 100000000000

Full Output:
??????????????????????

Output Modulo 1e9 + 7:
72345276

Input:
1000000000000 1000000000000

Full Output:
???????????????????????

Output Modulo 1e9 + 7:
173128245

Input:
10000000000000 10000000000000

Full Output:
???????????????????????

Output Modulo 1e9 + 7:
144115209

Input:
100000000000000 100000000000000

Full Output:
???????????????????????

Output Modulo 1e9 + 7:
607035370

Query for $$$(0 \leq S \leq 10^{18}, 0 \leq T \leq 10^{12})$$$ in under $$$830ms$$$

Update: Fixed the bug when calculate C++std::cbrt($$$n$$$) for $$$n$$$ = int($$$x$$$)$$$^3$$$

/// @title: Count non negative integer tuple (a, b, c) satisfied (sum <= S) and (product <= T)
/// @testing: for large S <= 1e18, T <= 1e12
/// > in O(T^(5/9)) time complexity = 830ms codeforces = 310ms ideone
/// > in O(const) memory complexity
/// > in O(3700Mb) code memory in 200 lines, 4444 characters
///
/// @date:    23/08/2021
/// @link:    https://ideone.com/yMi8tu
/// @author:  SPyofgame
/// @lisence: free lisence

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <iostream>
#include <cmath>

typedef long long ll;
const int MOD = 1e9 + 7;

///====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

/// Utility function
ll min(ll a, ll b) { return a < b ? a : b; }
ll max(ll a, ll b) { return a > b ? a : b; }
ll square(ll x) { return x * x; }

/// Sum of (1 + 2 + ... + x)
ll natural_sum(ll x)
{
    return (x <= 0) ? 0 : x * (x + 1) / 2;
}

/// Sum of (l + (l + 1) + ... + r)
ll natural_sum(ll l, ll r)
{
    return (l > r) ? 0 : natural_sum(r) - natural_sum(l - 1);
}

/// Sigma(p = y -> x) floor(n / p) in O(cbrt(n))
/// @link: https://arxiv.org/pdf/1206.3369.pdf
/// @author: Richard Sladkey
ll fastsumdiv(ll y, ll x, ll n)
{
    if (y > x) return 0;

    ll S = 0;
    ll B = n / (x + 1);
    ll E = n % (x + 1);
    ll D = n / x - B;
    ll G = B - x * D;
    ll d = 0;

    for (; x >= y; --x)
    {
        E += G;
        if (E >= x)
        {
            D += 1, G -= x, E -= x;
            if (E >= x)
            {
                D += 1, G -= x, E -= x;
                if (E >= x) break; /// not likely to happen more
            }
        }
        else if (E < 0)
        {
            D -= 1, G += x, E += x;
        }

        G += 2 * D, B += D, S += B;
    }

    E = n % (x + 1);
    D = n / x - B;
    G = B - x * D;
    for (; x >= y; --x)
    {
        E += G;
        d = E / x;
        D += d;
        E -= x * d;
        G += 2 * D - x * d, B += D, S += B;
    }

    for (; x >= y; --x)
    {
        S += n / x;
    }

    return S;
}

/// you can modify to -> Bignum / Modulo / Overflow
void add(ll &res, ll val)
{
    val %= MOD;
    res += val;
    if (res >= MOD) res -= MOD;
}

/// you can modify to -> Bignum / Modulo / Overflow
void sub(ll &res, ll val)
{
    val %= MOD;
    res -= val;
    if (res < 0) res += MOD;
}

/// Count (a, b, c) satisfied
/// { min(a, b, c) >= 0
/// { a + b + c <= S
/// { a * b * c <= T
/// O(cbrt(T)^2) complexity
///
/// @proof: https://math.stackexchange.com/questions/4230187/faster-algorithm-for-counting-non-negative-tripplea-b-c-satisfied-a-b-c
/// @author: SPyofgame
ll solve_ABC(ll S, ll T)
{
    ll cbT = cbrt(T); /// Not very accuracy
    while (cbT * cbT * cbT < T) ++cbT;
    while (cbT * cbT * cbT > T) --cbT;



/// [1] 0 <= a < b < c && a <= cbrt(T) -> cnt1 * 6
    ll cnt1 = 0;
    add(cnt1, (S / 2) * S - 2 * natural_sum(S / 2)); /// a = 0

    ll k = 1;
    for (ll a = 1, upa = min(S, cbT); a <= upa; ++a) /// a > 0 -> count(b < c)
    {
        ll SSS = S - a;
        ll TTT = T / a;
        ll KKK = min(SSS / 2, min((ll)sqrt(TTT), TTT / 2 + 1));

        /// Binary search for max k satisfy (S - a - k) <= (T / a / k)
        ll k = a;
        for (ll l = a + 1, r = KKK; l <= r; )
        {
            ll m = (l + r) >> 1;
            ll v = TTT / m;
            if (SSS - m <= v)
            {
                k = m;
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }

        sub(cnt1, natural_sum(a + 1, KKK));
        add(cnt1, SSS * (k - a) - natural_sum(a + 1, k));
        add(cnt1, fastsumdiv(k + 1, KKK, TTT));
    }



/// [2] 0 <= a < b = c && a <= cbrt(T) -> cnt2 * 3
    ll cnt2 = 0;
    add(cnt2, S / 2); /// a = 0
    for (ll a = 1, upa = min(S, cbT); a <= upa; ++a) /// a > 0 -> count(b = c)
    {
        add(cnt2, max(0LL, min((S - a) / 2, ll(floor(sqrt(T / a)))) - a));
    }



/// [3] 0 <= a = b < c && a <= cbrt(T) -> cnt3 * 3
    ll cnt3 = 0;
    add(cnt3, S); /// a = 0
    for (ll a = 1, upa = min(S / 2, cbT); a <= upa; ++a) /// a > 0 -> count(a < c)
    {
        add(cnt3, max(0LL, min(S - a - a, T / a / a) - a));
    }



/// [4] 0 <= a = b = c && a <= cbrt(T) -> cnt4 * 1
    ll cnt4 = 0;
    add(cnt4, min(S / 3, cbT) + 1); /// a = b = c >= 0



/// Final result: total counting
    ll res = 0;
    add(res, cnt1 * 6 + cnt2 * 3 + cnt3 * 3 + cnt4 * 1);
    return res;
}

/// Main function
int main()
{
	/// Input any number 0 <= S, T <= 1e18
    std::cout << solve_ABC(1000000000000000000LL, 1000000000000LL);
    return 0;
}

Input:  a
Output: 0
String: a

Input:  ba
Output: 1
String: ab

Input:  aaaaaa
Output: 0
String: aaaaaa

Input:  aaaaab
Output: 0
String: aaaaab

Input:  aaaaba
Output: 5
String: aaaaab

Input:  aaabaa
Output: 4
String: aaaaab

Input:  aabaaa
Output: 3
String: aaaaab

Input:  abaaaa
Output: 2
String: aaaaab

Input:  baaaaa
Output: 1
String: aaaaab

Input:  baaaab
Output: 1
String: aaaabb

Input:  abbbba
Output: 5
String: aabbbb

Input:  baabaa
Output: 1
String: aabaab

Input:  abaabaaabaababaaabaaababaab
Output: 14
String: aaabaaababaababaabaaabaabab

Input:  a ba aaaaaa aaaaab aaaaba aaabaa aabaaa abaaaa baaaaa baaaab abbbba baabaa abaabaaabaababaaabaaababaab
Output: 0  1 0      0           5     4     3     2     1      1          5  1                   14 
Output: 0 1 0 0 5 4 3 2 1 1 5 1 14 
String: a ab aaaaaa aaaaab aaaaab aaaaab aaaaab aaaaab aaaaab aaaabb aabbbb aabaab aaabaaababaababaabaaabaabab 

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
    
int min_cyc(string s)
{
    vector<pair<string, int> > V; 
    for (int i = 0; i < s.size(); ++i)
    {
        V.push_back(make_pair(s, i));
        rotate(s.begin(), s.begin() + 1, s.end());
    }

    sort(V.begin(), V.end());
    return V.front().second;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;
    
int min_cyc(string s)
{
    map<string, int> M;
    for (int i = 0; i < s.size(); ++i)
    {
        if (!M.count(s)) M[s] = i;
        rotate(s.begin(), s.begin() + 1, s.end());
    }
    return (M.begin() -> second);
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    s += s;
    
    int t = 0;
    for (int i = 1; i < n; ++i)
        if (s.substr(i, n) < s.substr(t, n))
            t = i;

    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>

using namespace std;

int min_cyc(const string &s)
{
    int n = s.size();

    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        int cmp = 0; /// EQUAL
        for (int p = n, l = t, r = i; p > 0; --p, ++l, ++r)
        {
            if (l == n) l = 0;
            if (r == n) r = 0;
            if (s[l] < s[r]) { cmp = -1; break; } ///  LESS 
            if (s[l] > s[r]) { cmp = +1; break; } /// GREATER
        }

        if (cmp == +1) t = i;
    }
    
    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

Candidate: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    abaabaaabaababaaabaaababaab
Candidate Substring:
0 - a 
1 - b
2 - a
3 - a
4 - b
5 - a
6 - a
7 - a
8 - b
9 - a
10 - a
11 - b
12 - a
13 - b 
14 - a
15 - a
16 - a
17 - b
18 - a
19 - a
20 - a
21 - b
22 - a
24 - a
25 - a
26 - b
Winner: a*

Candidate: 0 2 3 5 6 7 9 10 12 14 15 16 18 19 20 22 24 25 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    a_aa_aaa_aa_a_aaa_aaa_a_aa_
Candidate Substring:
0 - ab
2 - aa
3 - ab
5 - aa
6 - aa
7 - ab
9 - aa
10 - ab
12 - ab 
14 - aa
15 - aa
16 - ab
18 - aa
19 - aa
20 - ab
22 - ab
24 - aa
25 - ab
Winner: aa*

Candidate: 2 5 6 9 14 15 18 19 24 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    __aa_aa__a____aa__aa____a__
Candidate Substring:
2 - aab
5 - aaa
6 - aab
9 - aab
14 - aaa
15 - aab
18 - aaa
19 - aab
24 - aab
Winner: aaa*

Candidate: 5 14 18 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Candidate Substring:
5 - aaab
14 - aaab
18 - aaab
Winner: aaab*

Candidate: 5 14 18 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Candidate Substring:
5 - aaaba
14 - aaaba
18 - aaaba
Winner: aaaba*

Candidate: 5 14 18 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Candidate Substring:
5 - aaabaa
14 - aaabaa
18 - aaabab
Winner: aaabaa*

Candidate: 5 14
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a____________
Candidate Substring:
5 - aaabaab
14 - aaabaaa
Winner: aaabaaa*

Winner:   14 - VI
Number:   012345678901234567890123456
String:   abaabaaabaababaaabaaababaab
Remain:   ______________a____________
Champion: aaabaaa*

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size(); /// For convention: n = |s|
    s += s;

    /// For convention
    char mx = *max_element(s.begin(), s.end());
    char mn = *min_element(s.begin(), s.end());

    /// Candidate list
    vector<int> a;

    /// Pre-elimination
    for (int i = 0; i < n; ++i)
        if (s[i] == mn)
            a.push_back(i);

    /// Doing dth elimination
    for (int d = 1; d < n; ++d)
    {
        /// Minimal character among substrings
        char c = mx;
        for (int x : a) c = min(c, s[x + d]);

        /// New candidate list
        vector<int> b;

        /// Elimination
        for (int x : a)
            if (s[x + d] == c)
                b.push_back(x);

        swap(a, b);
        if (a.size() == 1) break; /// Found final candidate
    }

    return a.front(); /// The one with smallest index
}

int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    char mx = *max_element(s.begin(), s.end());
    char mn = *min_element(s.begin(), s.end());
    vector<int> a;
    for (int i = 0; i < n; ++i)
        if (s[i] == mn)
            a.push_back(i);

    for (int d = 1; d < n; ++d)
    {
        char c = mx;
        for (int x : a) c = min(c, s[x + d]);

        vector<int> b;
        for (int x : a)
            if (s[x + d] == c)
                b.push_back(x);

        swap(a, b);
        if (a.size() == 1) break;
    }

    return a.front();
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        int lcp = 0;
        for (int l = 0, r = n - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            if (s.substr(t, m) == s.substr(i, m))
            {
                lcp = m;
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }

        if (lcp == n) continue; /// Equal
        if (s[t + lcp] > s[i + lcp]) t = i;
    }

    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int MOD = 1e9 + 7;
int BASE = 123;
int powMOD(int x, int n)
{
    if (n == 0) return 1;
    if (n & 1) return (1LL * powMOD(x, n - 1) * x) % MOD;
    return (1LL * powMOD(x, n / 2) * powMOD(x, n / 2)) % MOD;
}

vector<int> P;
vector<int> H;
void init(const string &s)
{
    int n = s.size();
    int b = 1;
    
    P.assign(n, 0);
    H.assign(n + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
        P[i] = powMOD(b, MOD - 2);
        b = (1LL * b * BASE) % MOD;
    }
}

int query(int l, int r)
{
    return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
}

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    init(s);
    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        int lcp = 0;
        for (int l = 0, r = n - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            if (query(t, t + m) == query(i, i + m))
            {
                lcp = m;
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }

        if (lcp == n - 1) continue; /// Equal
        if (s[t + lcp] > s[i + lcp]) t = i;
    }

    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

template <const int MOD, const int BASE>
struct Hash 
{
    int powMOD(int x, int n)
    {
        if (n == 0) return 1;
        if (n & 1) return (1LL * powMOD(x, n - 1) * x) % MOD;
        return (1LL * powMOD(x, n / 2) * powMOD(x, n / 2)) % MOD;
    }

    vector<int> P;
    vector<int> H;
    void init(const string &s)
    {
        int n = s.size();
        int b = 1;
     
        P.assign(n, 0);
        H.assign(n + 1, 0);
        for (int i = 0; i < n; ++i)
        {
            H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
            P[i] = powMOD(b, MOD - 2);
            b = (1LL * b * BASE) % MOD;
        }
    }

    int query(int l, int r)
    {
        return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
    }
};

struct Pack
{
    int a, b, c, d, e, f;
    Pack (int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0)
    : a(a), b(b), c(c), d(d), e(e), f(f) {}

    bool operator == (const Pack &o)
    {
        return (a == o.a)
            && (b == o.b)
            && (c == o.c)
            && (d == o.d)
            && (e == o.e)
            && (f == o.f);
    }
};

struct Multihash
{
    Hash <1000000007, 123> A;
    Hash <1000000009, 1234> B;
    Hash <1000000021, 12345> C;
    Hash <1000000033, 123456> D;
    Hash <1000000087, 1234567> E;
    Hash <1000000093, 12345678> F;
    void init(const string &s)
    {
        A.init(s);
        B.init(s);
        C.init(s);
        D.init(s);
        E.init(s);
        F.init(s);
    }

    Pack query(int l, int r)
    {
        return Pack(
            A.query(l, r),
            B.query(l, r),
            C.query(l, r),
            D.query(l, r),
            E.query(l, r),
            F.query(l, r)
        );
    }
};

Multihash H;
int min_cyc(string s)
{
    int n = s.size();
    s += s;

    H.init(s);
    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        int lcp = 0;
        for (int l = 0, r = n - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            if (H.query(t, t + m) == H.query(i, i + m))
            {
                lcp = m;
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }

        if (lcp == n - 1) continue; /// Equal
        if (s[t + lcp] > s[i + lcp]) t = i;
    }

    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>

using namespace std;

int min_cyc(const string &s)
{
    int t = 0;
    int n = s.size();
    for (int i = 1; i < n; ++i)
    {
        int lcp = 0;
        for (int l = t, r = i; lcp < n; ++lcp, ++l, ++r)
        {
            if (l == n) l = 0;
            if (r == n) r = 0;
            if (s[l] != s[r]) break;
        }

        if (lcp == n) continue; /// Equal
        if (s[t + lcp] > s[i + lcp]) t = i;
    }

    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 2e5 + 25;
const int MOD = 1e9 + 7;
const int BASE = 123;
int powMOD(int x, int n)
{
    int res = 1;
    for (; n > 0; n >>= 1)
    {
        if (n & 1) res = (1LL * res * x) % MOD;
        x = (1LL * x * x) % MOD;
    }

    return res;
}

int H[LIM];
int P[LIM];
void init(const string &s)
{
    int n = s.size();
    int b = 1;
    
    H[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
        b = (1LL * b * BASE) % MOD;
    }

    P[n] = powMOD(b, MOD - 2);
    for (int i = n - 1; i >= 0; --i)
        P[i] = (1LL * P[i + 1] * BASE) % MOD;
}

int query(int l, int r)
{
    return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
}

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    init(s);
    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        int lcp = 0;
        for (int l = 0, r = n - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            if (query(t, t + m) == query(i, i + m))
            {
                lcp = m;
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }

        if (lcp == n - 1) continue; /// Equal
        if (s[t + lcp] > s[i + lcp]) t = i;
    }

    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>

using namespace std;

template <const int LIM, const int MOD, const int BASE>
struct Hash 
{
    int powMOD(int x, int n)
    {
        int res = 1;
        for (; n > 0; n >>= 1)
        {
            if (n & 1) res = (1LL * res * x) % MOD;
            x = (1LL * x * x) % MOD;
        }

        return res;
    }

    int H[LIM];
    int P[LIM];
    void init(const string &s)
    {
        int n = s.size();
        int b = 1;
     
        H[0] = 0;
        for (int i = 0; i < n; ++i)
        {
            H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
            b = (1LL * b * BASE) % MOD;
        }

        P[n] = powMOD(b, MOD - 2);
        for (int i = n - 1; i >= 0; --i)
            P[i] = (1LL * P[i + 1] * BASE) % MOD;
    }

    int query(int l, int r)
    {
        return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
    }
};

struct Pack
{
    int a, b, c, d, e, f;
    Pack (int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0)
    : a(a), b(b), c(c), d(d), e(e), f(f) {}

    bool operator == (const Pack &o)
    {
        return (a == o.a)
            && (b == o.b)
            && (c == o.c)
            && (d == o.d)
            && (e == o.e)
            && (f == o.f);
    }
};

struct Multihash
{
    Hash <200200, 1000000007, 123> A;
    Hash <200200, 1000000009, 1234> B;
    Hash <200200, 1000000021, 12345> C;
    Hash <200200, 1000000033, 123456> D;
    Hash <200200, 1000000087, 1234567> E;
    Hash <200200, 1000000093, 12345678> F;
    void init(const string &s)
    {
        A.init(s);
        B.init(s);
        C.init(s);
        D.init(s);
        E.init(s);
        F.init(s);
    }

    Pack query(int l, int r)
    {
        return Pack(
            A.query(l, r),
            B.query(l, r),
            C.query(l, r),
            D.query(l, r),
            E.query(l, r),
            F.query(l, r)
        );
    }
};

Multihash H;
int min_cyc(string s)
{
    int n = s.size();
    s += s;

    H.init(s);
    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        int lcp = 0;
        for (int l = 0, r = n - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            if (H.query(t, t + m) == H.query(i, i + m))
            {
                lcp = m;
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }

        if (lcp == n - 1) continue; /// Equal
        if (s[t + lcp] > s[i + lcp]) t = i;
    }

    return t;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

const int LIM = 1e6 + 16;
const int MOD = 1e9 + 7;
const int BASE = 123;
const int LESS    = -1;
const int EQUAL   =  0;
const int GREATER = +1;

/// Calculate (x ^ n) % MOD
int powMOD(int x, int n)
{
    int res = 1;
    for (; n > 0; n >>= 1)
    {
        if (n & 1) res = (1LL * res * x) % MOD;
        x = (1LL * x * x) % MOD;
    }
    
    return res;
}

int H[LIM];
int P[LIM];
/// Calculate hash of (S)
void init(const string &s)
{
    int n = s.size();

    H[0] = 0;
    int b = 1;
    for (int i = 0; i < n; ++i)
    {
        H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
        b = (1LL * b * BASE) % MOD;
    }

    P[n] = powMOD(b, MOD - 2);
    for (int i = n; i >= 1; --i)
        P[i - 1] = (1LL * P[i] * BASE) % MOD;
}

/// Hash value of s[l..r]
int query(int l, int r)
{
    return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
}

/// Compare s[l..l+d-1] vs s[r..r+d-1]
int cmp(const string &s, int i, int j, int d)
{
    int lcp = 0;
    for (int l = 0, r = d - 1; l <= r; )
    {
        int m = (l + r) >> 1;
        if (query(i, i + m) == query(j, j + m))
        {
            lcp = m;
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }

    if (lcp == d - 1 || s[i + lcp] == s[j + lcp]) return EQUAL;
    return (s[i + lcp] < s[j + lcp]) ? LESS : GREATER;
}

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size();
    int k = log(n) + 1;
    s += s;
    init(s);

    int big = 0;
    int upper = n / k + 1;
    for (int part = 0; part < upper; ++part)
    {
        int small = k * part;
        int upper = min(n, k * (part + 1));
        for (int i = k * part; i < upper; ++i)
            if (cmp(s, small, i, k) == GREATER)
                small = i;

        if (cmp(s, big, small, n) == GREATER) 
            big = small;
    }

    return big;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

const int LIM = 1e6 + 16;
const int LESS    = -1;
const int EQUAL   =  0;
const int GREATER = +1;

template<const int MOD, const int BASE>
struct Hash
{
    /// Calculate (x ^ n) % MOD
    int powMOD(int x, int n)
    {
        int res = 1;
        for (; n > 0; n >>= 1)
        {
            if (n & 1) res = (1LL * res * x) % MOD;
            x = (1LL * x * x) % MOD;
        }
        
        return res;
    }

    int H[LIM];
    int P[LIM];
    /// Calculate hash of (S)
    void init(const string &s)
    {
        int n = s.size();

        H[0] = 0;
        int b = 1;
        for (int i = 0; i < n; ++i)
        {
            H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
            b = (1LL * b * BASE) % MOD;
        }

        P[n] = powMOD(b, MOD - 2);
        for (int i = n; i >= 1; --i)
            P[i - 1] = (1LL * P[i] * BASE) % MOD;
    }

    /// Hash value of s[l..r]
    int query(int l, int r)
    {
        return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
    }
};

struct Pack 
{
    int a, b, c, d, e, f;
    Pack (int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0)
    : a(a), b(b), c(c), d(d), e(e), f(f) {}

    bool operator == (const Pack &o)
    {
        return (a == o.a)
            && (b == o.b)
            && (c == o.c)
            && (d == o.d)
            && (e == o.e)
            && (f == o.f);
    }
};

struct Multihash 
{
    Hash<1000000007, 123> A;
    Hash<1000000009, 1234> B;
    Hash<1000000021, 12345> C;
    Hash<1000000033, 123456> D;
    Hash<1000000087, 1234567> E;
    Hash<1000000093, 12345678> F;

    void init(const string &s)
    {
        A.init(s);
        B.init(s);
        C.init(s);
        D.init(s);
        E.init(s);
        F.init(s);
    }

    Pack query(int l, int r)
    {
        return Pack(
            A.query(l, r), 
            B.query(l, r),
            C.query(l, r),
            D.query(l, r),
            E.query(l, r),
            F.query(l, r)
        );
    }
};

Multihash H;

/// Compare s[l..l+d-1] vs s[r..r+d-1]
int cmp(const string &s, int i, int j, int d)
{
    int lcp = 0;
    for (int l = 0, r = d - 1; l <= r; )
    {
        int m = (l + r) >> 1;
        if (H.query(i, i + m) == H.query(j, j + m))
        {
            lcp = m;
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }

    if (lcp == d - 1 || s[i + lcp] == s[j + lcp]) return EQUAL;
    return (s[i + lcp] < s[j + lcp]) ? LESS : GREATER;
}

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size();
    int k = log(n) + 1;
    s += s;
    H.init(s);

    int big = 0;
    int upper = n / k + 1;
    for (int part = 0; part < upper; ++part)
    {
        int small = k * part;
        int upper = min(n, k * (part + 1));
        for (int i = k * part; i < upper; ++i)
            if (cmp(s, small, i, k) == GREATER)
                small = i;

        if (cmp(s, big, small, n) == GREATER) 
            big = small;
    }

    return big;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

int min_cyc(string s)
{
    int n = s.size(); /// real size of string
    int k = sqrt(n); /// optimal choice
    s += s; /// for convention

    int big = 0; /// One random candidate
    /// Big iteration: Compare string of size K
    for (int part = 0; part < n / k + 1; ++part) 
    {
        int small = part * k; /// One random candidate
        /// Small iteration: Compare string of size K
        for (int i = part * k; i < min(n, (part + 1) * k); ++i) 
        {
            /// Local comparision: Circular Prefixstring starts from here
            if (s.substr(small, k) > s.substr(i, k)) 
            {
                /// Assign new minimal point
                small = i; 
            }
        }

        /// Global comparision: Circular String starts from here
        if (s.substr(big, n) > s.substr(small, n)) 
        {
            /// Assign new minimal point
            big = small;
        }
    }

    /// The final winner
    return big;
}

int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

int min_cyc(string s)
{
    int n = s.size(); 
    int k = sqrt(n);
    s += s; 

    int big = 0; 
    for (int part = 0; part < n / k + 1; ++part) 
    {
        int small = part * k; 
        for (int i = part * k; i < min(n, (part + 1) * k); ++i) 
            if (s.substr(small, k) > s.substr(i, k)) 
                small = i; 

        if (s.substr(big, n) > s.substr(small, n)) 
            big = small;
    }

    return big;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

int min_cyc(const string &s)
{
    int n = s.size(); 
    int k = sqrt(n);

    int big = 0; 
    int upper = n / k + 1;
    for (int part = 0; part < upper; ++part) 
    {
        int small = part * k; 
        int upper = min(n, (part + 1) * k);
        for (int i = part * k; i < upper; ++i) 
        {
            for (int p = 0, l = small, r = i; p < k; ++p, ++l, ++r)
            {
                if (l == n) l = 0;
                if (r == n) r = 0;
                if (s[l]  > s[r]) small = i;
                if (s[l] != s[r]) break;
            }
        }

        for (int p = 0, l = big, r = small; p < n; ++p, ++l, ++r)
        {
            if (l == n) l = 0;
            if (r == n) r = 0;
            if (s[l]  > s[r]) big = small;
            if (s[l] != s[r]) break;
        }
    }

    return big;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

const int LIM = 2e5 + 25;
const int MOD = 1e9 + 7;
const int BASE = 123;
const int LESS    = -1;
const int EQUAL   =  0;
const int GREATER = +1;

/// Calculate (x ^ n) % MOD
int powMOD(int x, int n)
{
    int res = 1;
    for (; n > 0; n >>= 1)
    {
        if (n & 1) res = (1LL * res * x) % MOD;
        x = (1LL * x * x) % MOD;
    }
    
    return res;
}

int H[LIM];
int P[LIM];
/// Calculate hash of (S)
void init(const string &s)
{
    int n = s.size();

    H[0] = 0;
    int b = 1;
    for (int i = 0; i < n; ++i)
    {
        H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
        b = (1LL * b * BASE) % MOD;
    }

    P[n] = powMOD(b, MOD - 2);
    for (int i = n; i >= 1; --i)
        P[i - 1] = (1LL * P[i] * BASE) % MOD;
}

/// Hash value of s[l..r]
int query(int l, int r)
{
    return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
}

/// Compare s[l..l+d-1] vs s[r..r+d-1]
int cmp(const string &s, int i, int j, int d)
{
    int lcp = 0;
    for (int l = 0, r = d - 1; l <= r; )
    {
        int m = (l + r) >> 1;
        if (query(i, i + m) == query(j, j + m))
        {
            lcp = m;
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }

    if (lcp == d - 1 || s[i + lcp] == s[j + lcp]) return EQUAL;
    return (s[i + lcp] < s[j + lcp]) ? LESS : GREATER;
}

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size();
    int k = sqrt(n);
    s += s;
    init(s);

    int big = 0;
    int upper = n / k + 1;
    for (int part = 0; part < upper; ++part)
    {
        int small = k * part;
        int upper = min(n, k * (part + 1));
        for (int i = k * part; i < upper; ++i)
            if (cmp(s, small, i, k) == GREATER)
                small = i;

        if (cmp(s, big, small, n) == GREATER) 
            big = small;
    }

    return big;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

const int LIM = 2e5 + 25;
const int LESS    = -1;
const int EQUAL   =  0;
const int GREATER = +1;

template<const int MOD, const int BASE>
struct Hash
{
    /// Calculate (x ^ n) % MOD
    int powMOD(int x, int n)
    {
        int res = 1;
        for (; n > 0; n >>= 1)
        {
            if (n & 1) res = (1LL * res * x) % MOD;
            x = (1LL * x * x) % MOD;
        }
        
        return res;
    }

    int H[LIM];
    int P[LIM];
    /// Calculate hash of (S)
    void init(const string &s)
    {
        int n = s.size();

        H[0] = 0;
        int b = 1;
        for (int i = 0; i < n; ++i)
        {
            H[i + 1] = (H[i] + 1LL * b * (s[i] - 'a' + 1)) % MOD;
            b = (1LL * b * BASE) % MOD;
        }

        P[n] = powMOD(b, MOD - 2);
        for (int i = n; i >= 1; --i)
            P[i - 1] = (1LL * P[i] * BASE) % MOD;
    }

    /// Hash value of s[l..r]
    int query(int l, int r)
    {
        return (1LL * (H[r] - H[l] + MOD) * P[l]) % MOD;
    }
};

struct Pack 
{
    int a, b, c, d, e, f;
    Pack (int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0)
    : a(a), b(b), c(c), d(d), e(e), f(f) {}

    bool operator == (const Pack &o)
    {
        return (a == o.a)
            && (b == o.b)
            && (c == o.c)
            && (d == o.d)
            && (e == o.e)
            && (f == o.f);
    }
};

struct Multihash 
{
    Hash<1000000007, 123> A;
    Hash<1000000009, 1234> B;
    Hash<1000000021, 12345> C;
    Hash<1000000033, 123456> D;
    Hash<1000000087, 1234567> E;
    Hash<1000000093, 12345678> F;

    void init(const string &s)
    {
        A.init(s);
        B.init(s);
        C.init(s);
        D.init(s);
        E.init(s);
        F.init(s);
    }

    Pack query(int l, int r)
    {
        return Pack(
            A.query(l, r), 
            B.query(l, r),
            C.query(l, r),
            D.query(l, r),
            E.query(l, r),
            F.query(l, r)
        );
    }
};

Multihash H;

/// Compare s[l..l+d-1] vs s[r..r+d-1]
int cmp(const string &s, int i, int j, int d)
{
    int lcp = 0;
    for (int l = 0, r = d - 1; l <= r; )
    {
        int m = (l + r) >> 1;
        if (H.query(i, i + m) == H.query(j, j + m))
        {
            lcp = m;
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }

    if (lcp == d - 1 || s[i + lcp] == s[j + lcp]) return EQUAL;
    return (s[i + lcp] < s[j + lcp]) ? LESS : GREATER;
}

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size();
    int k = sqrt(n);
    s += s;
    H.init(s);

    int big = 0;
    int upper = n / k + 1;
    for (int part = 0; part < upper; ++part)
    {
        int small = k * part;
        int upper = min(n, k * (part + 1));
        for (int i = k * part; i < upper; ++i)
            if (cmp(s, small, i, k) == GREATER)
                small = i;

        if (cmp(s, big, small, n) == GREATER) 
            big = small;
    }

    return big;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

void KMP(const string &s, vector<int> &K)
{
    K.assign(s.size(), 0);
    for (int l = 1, r = 1; r < s.size(); ++r)
    {
        for (l = K[r - 1]; l && s[l] != s[r]; l = K[l - 1]);
        K[r] = l + (s[l] == s[r]);
    }
}

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> KMP(const string &s)
{
    vector<int> K(s.size());
    for (int l = 1, r = 1; r < s.size(); ++r)
    {
        for (l = K[r - 1]; l && s[l] != s[r]; l = K[l - 1]);
        K[r] = l + (s[l] == s[r]);
    }
    return K;
}

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    int p = 0;
    for (int i = 1; i < n; ++i)
    {
        vector<int> K = KMP(s.substr(p, n) + "#" + s.substr(i, n));
        int k = 0; /// First difference character
        while (k < n && K[k + n] + 1 == K[k + n + 1]) ++k;
        if (k < n && s[p + k] > s[i + k]) p = i;
    }

    return p;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    /// Prefix Function, not for the inital but the current one
    vector<int> f(s.size(), -1); /// -1 means KMP function stop right there
    s += s; /// Duplicating for convention

    int p = 0; /// The current rotation we are compare with
    for (int l = 1, r = 1; r < s.size(); ++r) 
    {
        /// KMP function
        ///
        /// l = f[r - p - 1]      <=       l = K[K[r] - 1]
        /// Latest KMP value              Latest KMP value
        ///
        ///           l != 0 && s[l] != s[r]
        ///    non-ended KMP and non-equal character 
        ///            V    V    V    V    V
        ///       l != -1 && s[p + l + 1] != s[r]          
        /// non-ended KMP and non-equal character at pth rotation            
        ///
        ///  l = f[l]              <=        l = K[l - 1]
        /// Previous KMP                     Previous KMP 
        /// For convention we just made (l) difference a little bit
        ///

        for (l = f[r - p - 1]; l != -1 && s[p + l + 1] != s[r]; l = f[l])
        {
            if (s[l + p + 1] > s[r]) /// pth rotation is bigger than current rotation
            {  
                p = r - l - 1;
            }
        }

        /// KMP not ended here and this is the first different character between pth rotation and current rotation
        if (l == -1 && s[l + p + 1] != s[r])
        {
            if (s[p + l + 1] > s[r]) /// pth rotation is bigger than current rotation
            {
                p = r;
            }
                           /// f[r - p] <=> K[K[r]]
            f[r - p] = -1; /// KMP must ended here since we compared the rotation
        }
        else
        {
            f[r - p] = l + 1; /// Normal KMP where "(s[l] = s[r]) = (1)"
        }
    }
    
    /// Return the rotation
    return p;
}
    
int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int min_cyc(string s)
{
    int p = 0;
    s += s;

    vector<int> f(s.size(), -1);
    for (int l = 1, r = 1; r < s.size(); ++r) 
    {
        for (l = f[r - p - 1]; l != -1 && s[p + l + 1] != s[r]; l = f[l])
            if (s[l + p + 1] > s[r])
                p = r - l - 1;

        if (l == -1 && s[p + l + 1] != s[r])
        {
            if (s[p + l + 1] > s[r])
                p = r;

            f[r - p] = -1;
        }
        else
        {
            f[r - p] = l + 1;
        }
    }
    
    return p;
}
    
int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

[0] $$$ab$$$

[2] $$$aab$$$

[5] $$$aaabaabab$$$

[14] $$$aaabaaababaab$$$

• The idea is that when we factorize duplicated string $$$t = s + s$$$

• Then the answer will be a substring of maximum starting position $$$p$$$ not exceed $$$|s|$$$

• The proves is already inside the code

#include <algorithm>
#include <iostream>

using namespace std;

/// Find starting position of minimum acyclic string in (s)
int min_cyc(string s)
{
    int n = s.size(); /// the real size of the string
    s += s; /// for convention since we are deadling with acyclic

    ///
    /// s = s1 + s2 + s3
    /// s1 = s[1..l-1] is handled
    /// s2 = s[l..r]   is handling
    /// s3 = s[p..n]   is going to be handled
    /// 

    int res = 0; /// minimum acyclic string
    /// while (s2) is a lyndon word, try to add s2 with s[p]
    for (int l = 0; l < n; )
    {
        ///
        /// - Case 1: 
        ///     If (s) is fully ordered, then return 0
        ///     Surely will this loop make [l..r] = [0..n-1]
        ///     Ans it is currently that (l = 0) 
        ///     => res = l is a correct answer
        ///
        /// - Case 2:
        ///     Minimum acyclic string s' = s[l..r] that 0 <= l < n <= r < 2n
        ///     Also if s2 is s', then the loop will extend its (r >= n)
        ///     Since l < n, the latest (l) will create s'    
        ///     => res = l is a correct answer
        /// 
        /// Hence in both cases, res = last(l) will return a correct answer
        ///
        res = l;

        /// Extend as much as possible lyndon word s2 = s[l..r]
        int r = l, p = l + 1;
        while (p < s.size())
        {
            /// (s2 + s[p]) is not a lyndon word
            if (s[r] > s[p]) 
            {
                break;
            }

            /// (s2 + s[p]) is stil a lyndon word, hence extend s2
            if (s[r] == s[p]) 
            {
                ++r;
                ++p;
                continue;
            }
            
            /// (s2 + s[p]) is a lyndon word, but it may be a repeated string
            if (s[r] < s[p]) 
            {
                r = l;
                ++p;
                continue;
            }
        }

        /// The lyndon word may have the form of s2 = sx + sx + .. + sx like "12312123"
        while (l <= r) 
        {
            /// s[l..l + p - r] is sx
            l += p - r;
        }
    }

    /// Dont forget to return the value ;)
    return res;
}

/// If you wanna know about that minimum acyclic string
string cyc(string s, int k)
{
    rotate(s.begin(), s.begin() + k, s.end());
    return s;
}

int main()
{
    /// Input 
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s) << '\n';
//  cout << cyc(s, min_cyc(s));
    return 0;
}

#include <iostream>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    int res = 0;
    for (int l = 0; l < n; )
    {
        res = l;
        int r = l, p = l + 1;
        for (; p < s.size() && s[r] <= s[p]; ++r, ++p)
            if (s[r] < s[p]) r = l - 1;

        while (l <= r) l += p - r;
    }

    return res;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s) << '\n';
    return 0;
}

#include <iostream>
    
using namespace std;
    
int min_cyc(const string &s) 
{
    int n = s.size();
    int res = 0;
    for (int l = 0; l < n; )
    {
        res = l;
        int r = l, p = l + 1;
        for (; r < n; ++r, ++p) /// If there is such string found, then its length wont exceed |s|
        {
            char c = (p < n) ? s[p] : s[p - n]; /// to avoid modulo
            if (s[r] > c) break;
            if (s[r] < c) r = l - 1;
        }        
        l = max(r, l + p - r); /// just skip those (s2 = sx + sx + ... + sx + sy) cases
    }
    return res;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

At (0): SA[i] = 8 | LCP[i] = 0 | Suffix we care: <p>Unable to parse markup [type=CF_MATHJAX]</p>$$$ | Real suffix = $$$\$$
At (1): SA[i] = 7 | LCP[i] = 0 | Suffix we care: a$   | Real suffix = a$
At (2): SA[i] = 3 | LCP[i] = 1 | Suffix we care: aaab | Real suffix = aaaba$
At (3): SA[i] = 4 | LCP[i] = 2 | Suffix we care: aaba | Real suffix = aaba$
At (4): SA[i] = 0 | LCP[i] = 0 | Suffix we care: aaba | Real suffix = aabaaaba$
At (5): SA[i] = 5 | LCP[i] = 1 | Suffix we care: aba$ | Real suffix = aba$
At (6): SA[i] = 1 | LCP[i] = 3 | Suffix we care: abaa | Real suffix = abaaaba$
At (7): SA[i] = 6 | LCP[i] = 0 | Suffix we care: ba$  | Real suffix = ba$
At (8): SA[i] = 2 | LCP[i] = 2 | Suffix we care: baaa | Real suffix = baaaba$

t = 2
answer = 3

$$$O(n^2 log n)$$$ by storing and sorting by the whole suffix

$$$O(n^2)$$$ by improving the sorting

$$$O(n log^2(n))$$$ by only provide positions and sort by the $$$2^0, 2^1, \dots, 2^k \approx n$$$ character

$$$O(n log(n))$$$ by using radix sort instead

$$$O(n log(log(n)))$$$ by improving how you sort further deep

$$$O(n)$$$ by using DC3 algorithm

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
using namespace std;

#define all(x) (x).begin(), (x).end()
vector<int> cal_SA(const string &s)
{
    vector<int> p(s.size());
    iota(all(p), 0);
    sort(all(p), [&](int x, int y) { return s.substr(x, s.size() - x) < s.substr(y, s.size() - y); });
    return p;
}

int main()
{
    string s;
    cin >> s;
    s += '$';

    vector<int> SA = cal_SA(s);
    for (int x : SA) 
    {
        string suffix = s.substr(x);
        cout << x << ' ' << suffix << endl;
    }

    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
vector<int> cal_SA(const string &s)
{
    const ll n = s.size();
    vector<int> p(n);
    vector<ll> c(n), d(n);
    for (int i = 0; i < n; ++i) p[i] = i, c[i] = s[i];

    for (int k = 0; k < n; k = !k ? 1 : k <<= 1)
    {
        for (int i = 0; i < n; ++i) d[i] = n * c[i] + c[(i + k) % n];
        sort(all(p), [&](int i, int j) { return d[i] < d[j]; });
 
        c[p[0]] = 0;
        for (int i = 1; i < n; ++i)
            c[p[i]] = c[p[i - 1]] + (d[p[i]] != d[p[i - 1]]);
    }
 
    return p;
}
int main()
{
    string s;
    cin >> s;
    s += '$';
    
    vector<int> SA = cal_SA(s);
    for (int x : SA) 
    {
        string suffix = s.substr(x);
        cout << x << ' ' << suffix << endl;
    }

    return 0;
}

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
vector<int> cal_SA(const string &s)
{
    int n = s.size();
    vector<int> f(2 * n), p(n), c(n);
    for (int i = 0; i < n; ++i)
        f[i] = f[i + n] = i;
        
    { /// k = 0
        /// sort one character
        iota(all(p), 0);
        stable_sort(all(p), [&](int i, int j) { return s[i] < s[j]; });

        /// assign initial order
        c[p[0]] = 0;
        for (int i = 1; i < n; ++i)
            c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
    }
 
    vector<int> cn(n), pn(n), cnt(n + 1);
    for (int k = 1; k < n; k <<= 1)
    {
        /// radix sort
        for (int &x : p) x = f[x - k + n];
        fill(all(cnt), 0);
        for(int x : c) cnt[x + 1]++;
        partial_sum(all(cnt), cnt.begin());
        for(int x : p) pn[cnt[c[x]]++] = x;
        swap(p, pn);
 
        /// assign new order
        cn[p[0]] = 0;
        for (int i = 1; i < n; ++i)
        {
            int l = p[i - 1], r = p[i];
            cn[r] = cn[l] + (c[l] != c[r] || c[f[l + k]] != c[f[r + k]]);
        }
        swap(c, cn);
    }
    
    return p;
}

int main()
{
    string s;
    cin >> s;
    s += '$';
    
    vector<int> SA = cal_SA(s);
    for (int x : SA) 
    {
        string suffix = s.substr(x);
        cout << x << ' ' << suffix << endl;
    }

    return 0;
}

$$$O(n^2)$$$ by comparing consecutives suffix

$$$O(n log n)$$$ by using hashing and binary search

$$$O(n log(log(n)))$$$ by using binary search but with clever more way

$$$O(n)$$$ by using Kasai Algorithm

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
using namespace std;
 
#define all(x) (x).begin(), (x).end()
vector<int> cal_SA(const string &s)
{
    int n = s.size();
    vector<int> f(2 * n), p(n), c(n);
    for (int i = 0; i < n; ++i)
        f[i] = f[i + n] = i;
        
    { /// k = 0
        iota(all(p), 0);
        stable_sort(all(p), [&](int i, int j) { return s[i] < s[j]; });

        c[p[0]] = 0;
        for (int i = 1; i < n; ++i)
            c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
    }
 
    vector<int> cn(n), pn(n), cnt(n + 1);
    for (int k = 1; k < n; k <<= 1)
    {
        for (int &x : p) x = f[x - k + n];
        fill(all(cnt), 0);
        for(int x : c) cnt[x + 1]++;
        partial_sum(all(cnt), cnt.begin());
        for(int x : p) pn[cnt[c[x]]++] = x;
        swap(p, pn);
 
        cn[p[0]] = 0;
        for (int i = 1; i < n; ++i)
        {
            int l = p[i - 1], r = p[i];
            cn[r] = cn[l] + (c[l] != c[r] || c[f[l + k]] != c[f[r + k]]);
        }
        swap(c, cn);
    }
    
    return p;
}
 
vector<int> cal_LCP(const string &s, const vector<int> &p)
{
    int n = s.size();
    vector<int> LCP(n), c(n);
    for (int i = 0; i < n; i++) c[p[i]] = i;
    for (int i = 0, k = 0; i < n; ++i) if (p[i] != n - 1)
    {
        for (int j = p[c[i] - 1]; s[i + k] == s[j + k]; ++k);
        LCP[c[i]] = k;
        if (k) --k;
    }
 
    return LCP;
}
 
int min_cyc(const string &s)
{
    if (count(all(s), s[0]) == s.size()) return 0;
    int n = s.size();
    vector<int> SA = cal_SA(s + s + '$');
    vector<int> LCP = cal_LCP(s + s + '$', SA);

    for (int i = 0; i < 2 * n + 1; ++i) if (SA[i] < n)
    {
        while (i <= 2 * n && SA[i] > SA[i + 1] && LCP[i + 1] >= n) ++i;
        return SA[i];
    }
}
 
int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
}

#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct state 
{
    // leng : longest lengh of all strings in the pth class
    // minp : minimum position of occurence
    // link : provide you the parent of sa_size
    // edge : labeled edge from node sa_size

    int leng;
    int minp;
    int link;
    map<char, int> edge;
};

const int LIM = 2e6 + 26;
state sa[LIM * 2];
int sa_size;
int last;

void construct(const string &s) 
{
    /// Initialization
    last = 0;
    sa[0].leng = 0;
    sa[0].minp = -1;
    sa[0].link = -1;
    sa_size = 1;

    /// Extend suffix automaton
    for (char c : s)
    {
        /// Make new state
        int cur = sa_size++;
        sa[cur].leng = sa[last].leng + 1;
        sa[cur].minp = sa[cur].leng - 1;

        int u = last;
        /// Find such state (u) linked to (last)
        for (; u != -1 && !sa[u].edge.count(c); u = sa[u].link)
            sa[u].edge[c] = cur;

        last = cur;
        if (u == -1) continue; /// (last) is linked with inital state only
        
        int v = sa[u].edge[c];
        if (sa[u].leng + 1 == sa[v].leng) /// we dont split state (v) here
        {
            sa[cur].link = v;
            continue;
        } 
         
        /// Split state (v) by making its clone (v')
        int nxt = sa_size++;
        sa[nxt].leng = sa[u].leng + 1;
        sa[nxt].minp = sa[v].minp;
        sa[nxt].link = sa[v].link;
        sa[nxt].edge = sa[v].edge;

        /// Find such state linked with it
        sa[v].link = sa[cur].link = nxt;
        for (; u != -1 && sa[u].edge[c] == v; u = sa[u].link)
            sa[u].edge[c] = nxt;
    }
}

int min_cyc(const string &s)
{
    /// Construct Suffix Automata of all string rotations
    construct(s + s);

    /// Find lexicographically minimal string rotation
    int root = 0;
    for (int i = 0; i < s.size(); ++i)
    {
   /// cout << sa[root].edge.begin() -> first; /// if you want to output such string
        root = sa[root].edge.begin() -> second;
    }

    /// Find its first occurence
    return sa[root].minp - s.size() + 1;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

Candidate: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    abaabaaabaababaaabaaababaab
Dual:      AABBCCDDEEFFGGHHIIJJKKLLMM?
Compare:   
A: a < b 
B: a = a
C: b > a
D: a = a 
E: b > a 
F: a < b 
G: a < b 
H: a = b
I: a < b
J: a = b
K: a < b
L: a < b 
M: a = b
?: b ?

Candidate: 0 2 5 6 9 12 14 16 18 20 22 24 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    a_a__aa__a__a_a_a_a_a_a_a_b
Dual:      A A  BB  C  C D D E E F F ?
Compare:   
A: ab > aa 
B: aa = aa
C: aa < ab
D: aa < ab
E: aa < ab
F: ab > aa
?: b ?

Candidate: 2 5 9 14 18 24 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    __a__a___a____a___a_____a_b
Dual:        A  A   B    B   C     C ?
Compare:   
A: aab > aaa 
B: aabab > aaaba
C: aaabab < aababa
?: b ?

Candidate: 5 14 18 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a_______b
Dual:           A        A   B       B
Compare:   
A: aaabaab > aaabaaa 
B: aaabab < babaab

Candidate: 14 18
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    ______________a___a________
Dual:                    A   A
Compare:   
A: aaab = aaab

Winner:  14 - V
Number:  012345678901234567890123456
String:  abaabaaabaababaaabaaababaab
Remain:  ______________a____________
Dual:                  *   
Compare: Stopped

#include <iostream>
#include <vector>

using namespace std;

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size(); /// For convention: n = |s|

    /// Candidate list
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        a[i] = i; /// Acyclic string start from (i) might the one with minimal lexicographical

    /// For convention
    s += s;

    /// Keep doing dual-elimination until we have the final champion
    while (a.size() > 1)
    {
        /// Next Candidate List
        vector<int> b;
        for (int i = 0; i + 1 < a.size(); i += 2)
        {
            /// Notice that for convention, l < r
            int l = a[i];
            int r = a[i + 1];

            /// Compare substring of size d = r - l
            /// -  Left string: A = s[l...l+d]
            /// - Right string: B = s[r...r+d]
            ///
            /// # Case (A < B): Left string is smaller 
            ///   > We will pick (a[i]) as a winner
            ///
            /// # Case (A > B): Right string is smaller
            ///   > We will pick (a[i + 1]) as a winner
            /// 
            /// # Case (A = B): Both string are equal
            ///   > We will pick one whose starting point is smaller
            ///

            if (s.substr(l, r - l) <= s.substr(r, r - l))
                b.push_back(l);
            else 
                b.push_back(r);
        }

        /// The remain candidate that not join the elimination
        if (a.size() & 1) b.push_back(a.back());
        
        /// Do the next elimination
        swap(a, b);
    }

    /// The final winner
    return a.front();
}

int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        a[i] = i;

    s += s;
    while (a.size() > 1)
    {
        vector<int> b;
        for (int i = 0; i + 1 < a.size(); i += 2)
        {
            int l = a[i];
            int r = a[i + 1];
            if (s.substr(l, r - l) <= s.substr(r, r - l))
                b.push_back(l);
            else 
                b.push_back(r);
        }

        if (a.size() & 1) b.push_back(a.back());
        swap(a, b);
    }

    return a.front();
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <deque>

using namespace std;

int min_cyc(const string &s)
{
    char c = *min_element(s.begin(), s.end());
    int n = s.size();
    deque<int> S; 
    for (int i = 0; i < n; ++i)
        if (s[i] == c)
            S.push_back(i); 

    while (S.size() > 1)
    {
        int a = S.front(); S.pop_front();
        int b = S.front(); S.pop_front();
        if (a > b) swap(a, b);
        int res = min(a, b);
        for (int l = a, r = b, p = r - l; p >= 1; --p, ++l, ++r)
        {
            if (l == n) l = 0;
            if (r == n) r = 0;
            if (s[l] < s[r]) { res = a; break; }
            if (s[l] > s[r]) { res = b; break; }
        }
        S.push_back(res);
    }

    return S.back();
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

Candidate: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    abaabaaabaababaaabaaababaab
Candidate Substring:
0 - a 
1 - b
2 - a
3 - a
4 - b
5 - a
6 - a
7 - a
8 - b
9 - a
10 - a
11 - b
12 - a
13 - b 
14 - a
15 - a
16 - a
17 - b
18 - a
19 - a
20 - a
21 - b
22 - a
24 - a
25 - a
26 - b
Winner: a*

Candidate: 0 2 3 5 6 7 9 10 12 14 15 16 18 19 20 22 24 25 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    a_aa_aaa_aa_a_aaa_aaa_a_aa_
Candidate Substring:
0 - ab
2 - aa
3 - ab
5 - aa
6 - aa
7 - ab
9 - aa
10 - ab
12 - ab 
14 - aa
15 - aa
16 - ab
18 - aa
19 - aa
20 - ab
22 - ab
24 - aa
25 - ab
Winner: aa*

Candidate: 2 5 6 9 14 15 18 19 24 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    __aa_aa__a____aa__aa____a__
Candidate Substring:
2 - aab
5 - aaa
6 - aab
9 - aab
14 - aaa
15 - aab
18 - aaa
19 - aab
24 - aab
Winner: aaa*

Candidate: 5 14 18 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Candidate Substring:
5 - aaab
14 - aaab
18 - aaab
Winner: aaab*

Candidate: 5 14 18 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Candidate Substring:
5 - aaaba
14 - aaaba
18 - aaaba
Winner: aaaba*

Candidate: 5 14 18 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Candidate Substring:
5 - aaabaa
14 - aaabaa
18 - aaabab
Winner: aaabaa*

Candidate: 5 14
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a____________
Candidate Substring:
5 - aaabaab
14 - aaabaaa
Winner: aaabaaa*

Winner:   14 - VI
Number:   012345678901234567890123456
String:   abaabaaabaababaaabaaababaab
Remain:   ______________a____________
Champion: aaabaaa*

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size(); /// For convention: n = |s|
    s += s;

    /// For convention
    char mx = *max_element(s.begin(), s.end());
    char mn = *min_element(s.begin(), s.end());

    /// Candidate list
    vector<int> a;

    /// Pre-elimination
    for (int i = 0; i < n; ++i)
        if (s[i] == mn)
            a.push_back(i);

    /// Doing dth elimination
    for (int d = 1; d < n; ++d)
    {
        /// Minimal character among substrings
        char c = mx;
        for (int x : a) c = min(c, s[x + d]);

        /// New candidate list
        vector<int> b;

        /// Elimination
        for (int x : a)
            if (s[x + d] == c)
                b.push_back(x);

        swap(a, b);
        if (a.size() == 1) break; /// Found final candidate
    }

    return a.front(); /// The one with smallest index
}

int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    char mx = *max_element(s.begin(), s.end());
    char mn = *min_element(s.begin(), s.end());
    vector<int> a;
    for (int i = 0; i < n; ++i)
        if (s[i] == mn)
            a.push_back(i);

    for (int d = 1; d < n; ++d)
    {
        char c = mx;
        for (int x : a) c = min(c, s[x + d]);

        vector<int> b;
        for (int x : a)
            if (s[x + d] == c)
                b.push_back(x);

        swap(a, b);
        if (a.size() == 1) break;
    }

    return a.front();
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

Candidate: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    abaabaaabaababaaabaaababaab
Minimal Elimination: a*  -> 0 2 3 5 6 7 9 10 12 14 15 16 18 19 20 22 24 25 
Collide Elimination: aa* -> 0 2 5 7 9 12 14 16 18 20 22 24 

Candidate: 0 2 5 7 9 12 14 16 18 20 22 24 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    a_a__a___a__a_a___a___a_a__
Minimal Elimination: aa*   -> 2 5 9 14 18 24
Collide Elimination: aaaa* -> 2 5 9 14 18 24 

Candidate: 2 5 9 14 18 24 
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    __a__a___a____a___a_____a__
Minimal Elimination: aaa*    -> 5 14 18 
Collide Elimination: aaaaaa* -> 5 14 18 

Candidate: 5 14 18
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Minimal Elimination: aaab*     -> 5 14 18 
Collide Elimination: aaabaaab* -> 5 14

Candidate: 5 14
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a____________
Minimal Elimination: aaaba*      -> 5 14
Collide Elimination: aaabaaaaba* -> 5 14

Candidate: 5 14
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a____________
Minimal Elimination: aaabaa*       -> 5 14
Collide Elimination: aaabaaaaabaa* -> 5 14

Candidate: 5 14
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a____________
Minimal Elimination: aaabaaa*        -> 14
Collide Elimination: aaabaaaaaabaaa* -> 14

Winner:   14 - VI
Number:   012345678901234567890123456
String:   abaabaaabaababaaabaaababaab
Remain:   ______________a____________
Champion: aaabaaa*

#include <algorithm>
#include <iostream>
#include <deque>

using namespace std;

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size(); /// For convention: n = |s|
    s += s;

    /// For convention
    char mx = *max_element(s.begin(), s.end());
    char mn = *min_element(s.begin(), s.end());

    /// Candidate list
    deque<int> a;

    /// Pre-elimination
    for (int i = 0; i < n; ++i) if (s[i] == mn)
        if (a.empty() || a.back() != i - 1)
            a.push_back(i);

    /// Doing dth elimination
    for (int d = 1; d < n; ++d)
    {
        /// Minimal character among substrings
        char c = mx;
        for (int x : a) c = min(c, s[x + d]);

        /// New candidate list
        deque<int> b; 

        /// Elimination
        for (int x : a) if (s[x + d] == c)
            if (b.empty() || b.back() != x - d - 1)
                b.push_back(x);

        swap(a, b);
        if (a.size() == 1) break; /// Found final candidate
    }

    return a.front(); /// The one with smallest index
}

int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <deque>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    char mx = *max_element(s.begin(), s.end());
    char mn = *min_element(s.begin(), s.end());
    deque<int> a;
    for (int i = 0; i < n; ++i) if (s[i] == mn)
        if (a.empty() || a.back() != i - 1)
            a.push_back(i);

    for (int d = 1; d < n; ++d)
    {
        char c = mx;
        for (int x : a) c = min(c, s[x + d]);

        deque<int> b; 
        for (int x : a) if (s[x + d] == c)
            if (b.empty() || b.back() != x - d - 1)
                b.push_back(x);

        swap(a, b);
        if (a.size() == 1) break;
    }

    return a.front();
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

Candidate: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    abaabaaabaababaaabaaababaab
Minimal Elimination: a*           -> 0 2 3 5 6 7 9 10 12 14 15 16 18 19 20 22 24 25 
Merging Elimination: aaa* = (a)3* -> 5 14 18
Teleport Tournament: III

Candidate: 5 14 18
Number:    012345678901234567890123456
String:    abaabaaabaababaaabaaababaab
Remain:    _____a________a___a________
Minimal Elimination: aaab*                           -> 5 14 18 
Merging Elimination: aaabaaab = (aaab)2* = ((a)3b)2* -> 14
Teleport Tournament: VIII

Winner:   14 - VIII
Number:   012345678901234567890123456
String:   abaabaaabaababaaabaaababaab
Remain:   ______________a____________
Champion: aaabaaab*

#include <iostream>
#include <vector>

using namespace std;

/// Finding minimal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    /// For conventions:
    char mx = 0;
    for (char c : s)
    {
        mx = max(mx, c);
    }

    int n = s.size();
    s += s;

    /// Candidate list
    vector<int> a;
    for (int p = 0; p < n; ++p)
        a.push_back(p);

    /// dth elimination
    for (int d = 1; d <= n; ++d)
    {
        /// Minimal character among substrings
        char mn = mx;
        for (int p : a)
        {
            mn = min(mn, s[p + d - 1]);
        } 
        
        /// Longest Duplicated Minimal |d|-length Substring
        int k = 1;
        vector<int> v, f;
        for (int p : a)
        {
            /// This is not a minimal substring
            if (mn == s[p + d - 1])
            {
                /// Elimination
                if (v.empty() || (v.back() + 1LL * f.back() * d) % n != p) /// Maybe next candidate
                {
                    v.push_back(p);
                    f.push_back(1);
                }
                else 
                {
                    k = max(k, ++f.back()); /// Merging Case
                }
            }
        }

        /// Merge the last with the front if possible
        if ((v.back() + 1LL * f.back() * d) % n == v.front())
        {
            k = max(k, f.back() += f.front());
        }

        /// Next candidate list
        a.clear();
        for (int i = 0; i < v.size(); ++i)
        {
            if (f[i] == k) /// Ignore less repeated substrings since they arent optimal 
            {
                a.push_back(v[i]);
            }
        }

        /// Junp to the next tournament
        d = d * k;

        /// Found the winner
        if (a.size() == 1) break;
    }

    /// Return the winner
    return a.front();
}

int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int min_cyc(string s)
{
    char mx = 0;
    for (char c : s)
    {
        mx = max(mx, c);
    }

    int n = s.size();
    s += s;

    vector<int> a;
    for (int p = 0; p < n; ++p)
        a.push_back(p);

    for (int d = 1; d <= n; ++d)
    {
        char mn = mx;
        for (int p : a)
        {
            mn = min(mn, s[p + d - 1]);
        } 
        
        int k = 1;
        vector<int> v, f;
        for (int p : a)
        {
            if (mn != s[p + d - 1]) continue;
            if (v.empty() || (v.back() + 1LL * f.back() * d) % n != p)
            {
                v.push_back(p);
                f.push_back(1);
            }
            else 
            {
                k = max(k, ++f.back());
            }

        }

        if ((v.back() + 1LL * f.back() * d) % n == v.front())
            k = max(k, f.back() += f.front());

        d = d * k;

        a.clear();
        for (int i = 0; i < v.size(); ++i)
        {
            if (f[i] == k)
            {
                a.push_back(v[i]);
            }
        }

        if (a.size() == 1) break;
    }

    return a.front();
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define all(x) (x).begin(), (x).end()
int min_cyc(const string &s)
{
    char mx = *max_element(all(s));
    int n = s.size();

    vector<int> a(n);
    for (int i = 0; i < n; ++i) 
        a[i] = c[i] = c[i + n] = i;
    
    for (int d = 1, k = 1; d <= n; d = k + 1)
    {
        char mn = mx;
        for (int p : a) mn = min(mn, s[c[p + d - 1]]);
        
        vector<int> v;
        for (int p : a) if (mn == s[c[p + d - 1]])
        {
            if (v.empty() || c[v.back() + f[v.back()]] != p)
                v.push_back(p), f[v.back()] = 0;
            
            k = max(k, f[v.back()] += d);
        }

        if (c[v.back() + f[v.back()]] == v.front())
            k = max(k, f[v.back()] += f[v.front()]);

        a.clear();
        for (int p : v) if (f[p] == k) a.push_back(p);
        if (a.size() == 1) return a.front();
    }
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

For string $$$S$$$ of length $$$n$$$. Split string into 3 substring $$$S = S_1 + S_2 + S_3$$$

• $$$S_1$$$ is the part we handled

• $$$S_2$$$ is the part we are handling

• $$$S_3$$$ is the part we will handle

We will try to extend $$$S_2$$$ (also mean shorten $$$S_3$$$) as much as possible that still remain it as a Lyndon word.

Let $$$x = S_2.back$$$, $$$y = S_3.front$$$. We will compare $$$x$$$ with $$$y$$$ and concat $$$y$$$ at the back of $$$S_2$$$ if possible

• If $$$x > y$$$ then $$$S_2 + x$$$ is not a Lyndon word, hence we cut $$$S_2$$$ right here

• If $$$x = y$$$ then $$$S_2 + x$$$ is still a Lyndon word, hence extend it

• If $$$x < y$$$ then $$$S_2 + x$$$ is a repeated string of Lyndon words: $$$S_2 = S_x + S_x + \dots + S_x + S_y$$$ ($$$S_x$$$ and $$$S_y$$$ are Lyndon words, $$$|S_y| < |S_x|$$$)

Notice that after we cut $$$S_2$$$, $$$S_2$$$ might be a repeated string, and we must factorize it into.

#include <iostream>

using namespace std;

void duval(const string &s)
{
    int n = s.size();
    for (int l = 0; l < n; )
    {
        int r = l, p = l + 1;
        for (; r < n && s[r] <= s[p]; ++r, ++p)
            if (s[r] < s[p]) r = l - 1;

        while (l <= r)
        {
            cout << s.substr(l, p - r) << '\n';
            l += p - r;
        }
    }
}

int main()
{
    string s;
    cin >> s;
    duval(s);
    return 0;
}

#include <iostream>

using namespace std;

/// Factorize all lyndon word in s
void duval(const string &s)
{
    int n = s.size();

    ///
    /// s = s1 + s2 + s3
    /// s1 = s[1..l-1] is handled
    /// s2 = s[l..r]   is handling
    /// s3 = s[p..n]   is going to be handled
    /// 

    for (int l = 0; l < n; )
    {
        /// Extend as much as possible lyndon word s2 = s[l..r]
        int r = l, p = l + 1;
        while (r < n)
        {
            /// (s2 + s[p]) is not a lyndon word
            if (s[r] > s[p]) 
            {
                break;
            }

            /// (s2 + s[p]) is stil a lyndon word, hence extend s2
            if (s[r] == s[p]) 
            {
                ++r;
                ++p;
                continue;
            }
            
            /// (s2 + s[p]) is a repeated string of Lyndon words
            if (s[r] < s[p]) 
            {
                r = l;
                ++p;
                continue;
            }
        }

        /// The lyndon word may have the form of s2 = sx + sx + .. + sx + sy like "1231231231"
        while (l <= r) 
        {
            /// s[l..l + p - r] is sx
            cout << s.substr(l, p - r) << '\n';
            l += p - r;
        }
    }
}

int main()
{
    string s;
    cin >> s;
    duval(s);
    return 0;
}

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    s += s;

    int t = 0;
    for (int i = 1; i < n; ++i)
        if (s.substr(i, n) < s.substr(t, n))
            t = i;

    cout << t;
    return 0;
}

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    s += s;

    int t = 0;
    for (int i = 1; i < n; ++i)
    {
        int cmp = 0; /// EQUAL
        for (int p = n, l = t, r = i; p > 0; --p, ++l, ++r)
        {
            if (s[l] < s[r]) { cmp = -1; break; } ///  LESS 
            if (s[l] > s[r]) { cmp = +1; break; } /// GREATER
        }

        if (cmp == +1) t = i;
    }

    cout << t;
    return 0;
}

• The idea is that when we factorize duplicated string $$$t = s + s$$$

• Then the answer will be a substring of maximum starting position $$$p$$$ not exceed $$$|s|$$$

• The proves is already inside the code

#include <algorithm>
#include <iostream>

using namespace std;

/// Find starting position of minimum acyclic string in (s)
int min_cyc(string s)
{
    int n = s.size(); /// the real size of the string
    s += s; /// for convention since we are deadling with acyclic

    ///
    /// s = s1 + s2 + s3
    /// s1 = s[1..l-1] is handled
    /// s2 = s[l..r]   is handling
    /// s3 = s[p..n]   is going to be handled
    /// 

    int res = 0; /// minimum acyclic string
    /// while (s2) is a lyndon word, try to add s2 with s[p]
    for (int l = 0; l < n; )
    {
        ///
        /// - Case 1: 
        ///     If (s) is fully ordered, then return 0
        ///     Surely will this loop make [l..r] = [0..n-1]
        ///     Ans it is currently that (l = 0) 
        ///     => res = l is a correct answer
        ///
        /// - Case 2:
        ///     Minimum acyclic string s' = s[l..r] that 0 <= l < n <= r < 2n
        ///     Also if s2 is s', then the loop will extend its (r >= n)
        ///     Since l < n, the latest (l) will create s'    
        ///     => res = l is a correct answer
        /// 
        /// Hence in both cases, res = last(l) will return a correct answer
        ///
        res = l;

        /// Extend as much as possible lyndon word s2 = s[l..r]
        int r = l, p = l + 1;
        while (p < s.size())
        {
            /// (s2 + s[p]) is not a lyndon word
            if (s[r] > s[p]) 
            {
                break;
            }

            /// (s2 + s[p]) is stil a lyndon word, hence extend s2
            if (s[r] == s[p]) 
            {
                ++r;
                ++p;
                continue;
            }
            
            /// (s2 + s[p]) is a lyndon word, but it may be a repeated string
            if (s[r] < s[p]) 
            {
                r = l;
                ++p;
                continue;
            }
        }

        /// The lyndon word may have the form of s2 = sx + sx + .. + sx like "12312123"
        while (l <= r) 
        {
            /// s[l..l + p - r] is sx
            l += p - r;
        }
    }

    /// Dont forget to return the value ;)
    return res;
}

/// If you wanna know about that minimum acyclic string
string cyc(string s, int k)
{
    rotate(s.begin(), s.begin() + k, s.end());
    return s;
}

int main()
{
    /// Input 
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s) << '\n';
//  cout << cyc(s, min_cyc(s));
    return 0;
}

#include <iostream>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    s += s;

    int res = 0;
    for (int l = 0; l < n; )
    {
        res = l;
        int r = l, p = l + 1;
        for (; p < s.size() && s[r] <= s[p]; ++r, ++p)
            if (s[r] < s[p]) r = l - 1;

        while (l <= r) l += p - r;
    }

    return res;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s) << '\n';
    return 0;
}

#include <iostream>
    
using namespace std;
    
int min_cyc(const string &s) 
{
    int n = s.size();
    int res = 0;
    for (int l = 0; l < n; )
    {
        res = l;
        int r = l, p = l + 1;
        for (; r < n; ++r, ++p) /// If there is such string found, then its length wont exceed |s|
        {
            char c = (p < n) ? s[p] : s[p - n]; /// to avoid modulo
            if (s[r] > c) break;
            if (s[r] < c) r = l - 1;
        }        
        l = max(r, l + p - r); /// just skip those (s2 = sx + sx + ... + sx + sy) cases
    }
    return res;
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int p[n];
    iota(p, p + n, 0);

    ll res = 0;
    do {
        ll sum_weight = 0;
        ll sum_value = 0;
        for (int i = 0; i < n; ++i)
        {
            int weight = c[p[i]];
            int value = v[p[i]];

            sum_weight += weight;
            sum_value += value;
            if (sum_weight > w) 
            {
                break;
            }
            else
            {
                maximize(res, sum_value);
            }
        }

    }
    while (next_permutation(p, p + n));

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    ll res = 0;
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        int weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        if (weight <= w)
        {
            maximize(res, value);
        }
    }

    cout << res << endl;
    return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct Node 
{
    ll maxval = 0;

    ll value;
    int weight;
    Node (ll value = 0, int weight = 0)
    : value(value), weight(weight) {}
};

int n, w;
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = c.size(); /// Important !!!
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        ll weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        if (weight <= w)
        {
            S.push_back(Node(value, weight));
        }    
    }
}

int main()
{
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int m = n / 2;
    vector<int> cl, cr;
    vector<int> vl, vr;
    for (int i = 0; i < n; ++i)
    {
        if (i < m)
        {
            cl.push_back(c[i]);
            vl.push_back(v[i]);
        }
        else 
        {
            cr.push_back(c[i]);
            vr.push_back(v[i]);
        }
    }

    vector<Node> Sl, Sr;
    solve(cl, vl, Sl);
    solve(cr, vr, Sr);

    sort(all(Sr), [](const Node &a, const Node &b) {
        return (a.weight != b.weight) ? a.weight < b.weight : a.value < b.value;
    });

    ll maxval = 0;
    for (Node &x : Sr)
    {
        maximize(maxval, x.value);
        x.maxval = maxval;
    }

    ll res = 0;
    for (Node &y : Sl)
    {
        for (int l = 0, r = int(Sr.size()) - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            Node x = Sr[m];
            if (x.weight + y.weight <= w)
            {
                maximize(res, x.maxval + y.value);
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }
    }

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (s > w) return -LINF; /// Using too much weight
    if (i > n) return 0;     /// No available item to add into the bag

    ll &res = f[i][s];
    if (res != -1) return res;
        
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    memset(f, -1, sizeof(f));
    cout << magic();
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll res = 0;
    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            for (int j = 1; j < i; ++j)
            {
                for (int t = 0; t <= s; ++t)
                {
                    maximize(f[i][s], f[i][t] + 0);
                }
                
                for (int t = 0; t + c[i] <= s; ++t)
                {
                    maximize(f[i][s], f[i - 1][t] + v[i]);
                }
            }

            maximize(res, f[i][s]);
        }
    }

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = f[i - 1][s];
            if (s >= c[i])
            {
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
            }
        }
    }

    ll res = 0;
    for (int s = 0; s <= w; ++s)
        maximize(res, f[n][s]);

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);
            if (s >= c[i])
            {
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
            }
        }
    }

    cout << f[n][w];
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[2][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 1; s <= w; ++s)
        {
            f[cur][s] = f[pre][s];
            if (s >= c[i])
            {
                maximize(f[cur][s], f[pre][s - c[i]] + v[i]);
            }
        }
    }

    ll res = 0;
    for (int s = 0; s <= w; ++s)
        maximize(res, f[n & 1][s]);

    cout << res;
    return 0;
}

    ll f[2][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 1; s <= w; ++s)
            f[cur][s] = f[pre][s];
        
        for (int s = w; s >= c[i]; --s)
            maximize(f[cur][s], f[pre][s - c[i]] + v[i]);
    }

    ll f[w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 1; s <= w; ++s) /// Unneeded loop
            f[s] = f[s];
        
        for (int s = w; s >= c[i]; --s)
            maximize(f[s], f[s - c[i]] + v[i]);
    }

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = c; s <= w; ++s)
                maximize(f[s], f[s - c] + v);

        equivalent to

            for (int s = c; s <= w; ++s)
                maximize(f[cur][s], f[cur][s - c] + v);

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = w; s >= c; --s)
                maximize(f[s], f[s - c] + v);

        equivalent

            for (int s = w; s >= c; --s)
                maximize(f[cur][s], f[pre][s - c] + v);

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
        for (int s = w; s >= c[i]; --s)
            maximize(f[s], f[s - c[i]] + v[i]);

    cout << f[w];
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll &res = f[i][s];
    if (res != -1) return res;
    res = +LINF;

    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return res;
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    memset(f, -1, sizeof(f));
    for (int res = sum; res >= 0; --res)
    {
        if (magic(1, res) <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[n + 1][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int s = 0; s <= sum; ++s)
        {
            f[i][s] = f[i - 1][s];

            if (s >= v[i])
            {
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
            }
        }
    }

    for (int res = sum; res >= 0; --res)
    {
        if (f[n][res] <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[2][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 0; s <= sum; ++s)
        {
            f[cur][s] = f[pre][s];

            if (s >= v[i])
            {
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);
            }
        }
    }

    for (int res = sum; res >= 0; --res)
    {
        if (f[n & 1][res] <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

    ll f[2][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 0; s <= sum; ++s)
        {
            f[cur][s] = f[pre][s];

            if (s >= v[i])
            {
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);
            }
        }
    }

    ll f[2][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 0; s <= w; ++s) /// Unneeded loop
            f[s] = f[s];
        
        for (int s = sum; s >= v[i]; --s)
            minimize(f[s], f[s - v[i]] + c[i]);
    }

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = v[i]; s <= sum; ++s)
                minimize(f[s], f[s - v[i]] + c[i]);

        equivalent to

            for (int s = v[i]; s <= sum; ++s)
                minimize(f[cur][s], f[cur][s - v[i]] + c[i]);

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = sum; s >= v[i] --s)
                minimize(f[s], f[s - v[i]] + c[i]);

        equivalent to

            for (int s = sum; s >= v[i] --s)
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[sum + 1];
    memset(f, +LINF, sizeof(f));

    f[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int s = sum; s >= v[i]; --s)
            minimize(f[s], f[s - v[i]] + c[i]);

    for (int res = sum; res >= 0; --res)
    {
        if (f[res] <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int p[n];
    iota(p, p + n, 0);

    vector<int> selected;
    ll res = 0;
    do {
        bool better = false;
        vector<int> current;
        ll sum_weight = 0;
        ll sum_value = 0;
        for (int i = 0; i < n; ++i)
        {
            int weight = c[p[i]];
            int value = v[p[i]];

            sum_weight += weight;
            sum_value += value;
            if (sum_weight > w) 
            {
                break;
            }
            else
            {
               current.push_back(p[i]);
                if (res < sum_value)
                {
                    better = true;
                    res = sum_value;
                }
            }
        }

        if (better) selected = current;
    }
    while (next_permutation(p, p + n));

    cout << res << '\n';
    sort(selected.begin(), selected.end());
    for (int p : selected)
    {
        cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    ll res = 0;
    int selected = 0;
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        ll weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        if (weight <= w)
        {
            if (res <= value)
            {
                res = value;
                selected = mask;
            }
        }
    }

    cout << res << '\n';
    for (int i = 0; i < n; ++i)
    {
        if (selected >> i & 1)
        {
            cout << i + 1 << ' ' << c[i] << ' ' << v[i] << '\n';
        }
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct Node 
{
    ll maxval = 0;
    int maxmask = 0;

    int mask;
    ll value;
    int weight;
    Node (int mask = 0, ll value = 0, int weight = 0)
    : mask(mask), value(value), weight(weight) {}
};

int n, w;
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = c.size(); /// Important !!!
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        ll weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        S.push_back(Node(mask, value, weight));
    }
}

int main()
{
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int m = n / 2;
    vector<int> cl, vl;
    for (int i = 0; i < m; ++i)
    {
        cl.push_back(c[i]);
        vl.push_back(v[i]);
    }

    vector<int> cr, vr;
    for (int i = m; i < n; ++i)
    {
        cr.push_back(c[i]);
        vr.push_back(v[i]);
    }

    vector<Node> Sl, Sr;
    solve(cl, vl, Sl);
    solve(cr, vr, Sr);

    sort(all(Sr), [](const Node &a, const Node &b) {
        return (a.weight != b.weight) ? a.weight < b.weight : a.value > b.value;
    });

    ll maxval = 0;
    int maxmask = 0;
    for (Node &x : Sr)
    {
        if (maxval < x.value)
        {
            maxval = x.value;
            maxmask = x.mask;
        }
        x.maxval = maxval;
        x.maxmask = maxmask;
    }

    ll res = 0;
    int mask_l = 0;
    int mask_r = 0;
    for (Node &y : Sl)
    {
        for (int l = 0, r = int(Sr.size()) - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            Node x = Sr[m];
            if (x.weight + y.weight <= w)
            {
                if (res < x.maxval + y.value)
                {
                    res = x.maxval + y.value;
                    mask_l = y.mask;
                    mask_r = x.maxmask;
                }
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }
    }

    vector<int> selected;
    for (int i = 0; i < m; ++i)
        if (mask_l >> i & 1)
            selected.push_back(i);

    for (int i = 0; i < n - m; ++i)
        if (mask_r >> i & 1)
            selected.push_back(i + m);

    cout << res << '\n';
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';
    }

    return 0;
}

• $$$magic(i,s) = magic(i + 1,s + c[i]) + v[i])$$$ take this element will lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s + c[i])+ v[i]$$$ take this element wont lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s + c[i])+ v[i]$$$ either you take or not, you will find best result

• When $$$magic(i, s) = magic(X, Y)$$$, trace to next state $$$(i = X, s = Y)$$$

• When $$$magic(i, s) = magic(X, Y) = magic(P, Q)$$$, you can either trace to next state $$$(i = X, s = Y)$$$ or $$$(i = P, s = Q)$$$

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (s > w) return -LINF; /// Using too much weight
    if (i > n) return 0;     /// No available item to add into the bag

    ll &res = f[i][s];
    if (res != -1) return res;
        
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

vector<int> selected;
void trace(int i = 1, int s = 0)
{
    if (s > w) return ;
    if (i > n) return ;

    ll res = magic(i, s);
    if (res == magic(i + 1, s + 0) + 0)
    {
        return trace(i + 1, s + 0);
    }
    else 
    {
        selected.push_back(i);
        return trace(i + 1, s + c[i]);
    }
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    memset(f, -1, sizeof(f));
    cout << magic() << '\n';

    trace();
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);
            if (s >= c[i])
            {
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
            }
        }
    }

    vector<int> selected;
    for (int i = n, s = w; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])
        {
            selected.push_back(i);
            s -= c[i];
            i -= 1;
            continue;
        }

        if (f[i][s - 1] > f[i - 1][s])
        {
            --s;
        }
        else /// f[i][s] = f[i - 1][s]
        {
            --i;
        }
    }

    cout << f[n][w] << '\n';
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
    }
    return 0;
}

• The idea is based on Lusterdawn's explanation and jiangly's solution

• Let $$$calc(*f, l, r)$$$ is the function that calculate the answer for items $$$l, l + 1, \dots, r$$$ with $$$*f$$$ the 1D memorization table

• For convention, let $$$calc$$$ return the value of $$$min(w, \overset{r}{\underset{i = l}{\Sigma}} c_i)$$$ — maximal possible weight created

• First we calculate $$$calc(*f, 1, n)$$$, after having the maximal value of the whole items, we can find the minimal weight that return such value. Or $$$weight_used = min(p | f[p] = res)$$$

• Let $$$trace(s, l, r)$$$ is the function that tracing for all elements, whose sum weight equal $$$s$$$ and sum value is max

• If $$$(l = r)$$$, we will consider to select this item or not. (This item is selected when $$$s = c_l$$$)

• Split the items into two halves: $$$[l, m]$$$ and $$$(m, r]$$$ and then calculate DP: $$$sleft = calc(*L, l, m + 0)$$$ and $$$sright = calc(*R, m + 1, r)$$$

• We find such $$$pleft$$$ and $$$pright$$$ satisfy $$$pleft + pright = s$$$ that returning $$$max(L[pleft] + R[pright])$$$. Then we trace from $$$trace(pleft, l, m + 0)$$$ to $$$trace(pright, m + 1, r)$$$ (ordered selected item)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
	
using namespace std;
	
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
	
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
	
const int LIM_N = 111;
const int LIM_W = 1e6 + 16;
	
int n, w;
int c[LIM_N], v[LIM_N];
ll f[LIM_W];

int calc(ll *f, int l = 1, int r = n)
{
	ll upper = 0;
	for (int i = l; i <= r; ++i)
		upper += c[i];
	
	minimize(upper, (ll)w);
	for (int s = 0; s <= upper; ++s)
		f[s] = 0;
	
	for (int i = l; i <= r; ++i)
		for (int s = upper; s >= c[i]; --s)
			maximize(f[s], f[s - c[i]] + v[i]);
	
	return upper;
}
	
ll L[LIM_W], R[LIM_W];
vector<int> selected;
void trace(int s = w, int l = 1, int r = n)
{
	if (l == r)
	{
		if (s == c[l])
		{
			selected.push_back(l);
		}
	
		return ;
	}
	
	int m = (l + r) >> 1;
	int sleft  = calc(L, l, m + 0);
	int sright = calc(R, m + 1, r);
	
	ll mx = -1;
	int pleft = 0;
	int pright = s;
	for (int v = max(0, s - sright); v <= min(s, sleft); ++v)
	{
		if (mx < L[v] + R[s - v])
		{
			mx = L[v] + R[s - v];
			pleft = v;
			pright = s - v;
		}
	}
	
	trace(pleft , l, m + 0);
	trace(pright, m + 1, r);
}
		
int main()
{
	cin >> n >> w;
	for (int i = 1; i <= n; ++i)
		cin >> c[i] >> v[i];
	
	calc(f);
	ll res = f[w];
	int weight_used = max_element(f, f + w + 1) - f;
	
	trace(weight_used);	
	cout << res << '\n';	
	cout << selected.size() << '\n';
	for (int p : selected)
	{
	    cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
	}
	return 0;
}

• $$$magic(i,s) = magic(i + 1,s - v[i]) + c[i])$$$ take this element will lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s - v[i]) + c[i]$$$ take this element wont lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s - v[i]) + c[i]$$$ either you take or not, you will find best result

• When $$$magic(i, s) = magic(X, Y)$$$, trace to next state $$$(i = X, s = Y)$$$

• When $$$magic(i, s) = magic(X, Y) = magic(P, Q)$$$, you can either trace to next state $$$(i = X, s = Y)$$$ or $$$(i = P, s = Q)$$$

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll &res = f[i][s];
    if (res != -1) return res;
    res = +LINF;

    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return res;
}

vector<int> selected;
void trace(int i = 1, int s = 0)
{
    if (s < 0) return ;
    if (i > n) return ;

    ll res = magic(i, s);
    if (res == magic(i + 1, s + 0) + 0)
    {
        return trace(i + 1, s + 0);
    }
    else 
    {
        selected.push_back(i);
        return trace(i + 1, s - v[i]);
    }
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    memset(f, -1, sizeof(f));
    for (int res = sum; res >= 0; --res)
    {
        if (magic(1, res) <= w)
        {
            trace(1, res);
            
            cout << res << '\n';
            cout << selected.size() << '\n';
            for (int p : selected)
            {
                cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
            }
            return 0;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[n + 1][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int s = 0; s <= sum; ++s)
        {
            f[i][s] = f[i - 1][s];

            if (s >= v[i])
            {
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
            }
        }
    }

    int res = sum;
    while (f[n][res] > w) --res;
    
    vector<int> selected;
    for (int i = n, s = res; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - v[i]] + c[i])
        {
            selected.push_back(i);
            s -= v[i];
            i -= 1;
        }
        else 
        {
            --i;
        }
    }

    cout << res << '\n';
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
    }
    return 0;
}

• Let $$$calc(*f, l, r)$$$ is the function that calculate the answer for items $$$l, l + 1, \dots, r$$$ with $$$*f$$$ the 1D memorization table

• For convention, let $$$calc$$$ return the value of $$$\overset{r}{\underset{i = l}{\Sigma}} v_i$$$ — maximal possible value created

• First we calculate $$$calc(*f, 1, n)$$$, after having the minimal weight of the whole items, we can find the maximal value that return such weight. Or $$$res = max(p | f[p] \leq w)$$$

• Let $$$trace(s, l, r)$$$ is the function that tracing for all elements, whose sum value equal $$$s$$$ and sum weight is min

• If $$$(l = r)$$$, we will consider to select this item or not. (This item is selected when $$$s = v_l$$$)

• Split the items into two halves: $$$[l, m]$$$ and $$$(m, r]$$$ and then calculate DP: $$$sleft = calc(*L, l, m + 0)$$$ and $$$sright = calc(*R, m + 1, r)$$$

• We find such $$$pleft$$$ and $$$pright$$$ satisfy $$$pleft + pright = s$$$ that returning $$$min(L[pleft] + R[pright])$$$. Then we trace from $$$trace(pleft, l, m + 0)$$$ to $$$trace(pright, m + 1, r)$$$ (ordered selected item)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
	
using namespace std;
	
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
	
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
	
const int LIM_N = 111;
const int LIM_S = 1e6 + 16;
	
int n, w;
int c[LIM_N], v[LIM_N];
ll f[LIM_S + 1];

int calc(ll *f, int l = 1, int r = n)
{
	int upper = 0;
	for (int i = l; i <= r; ++i)
		upper += v[i];

	f[0] = 0;
	for (int s = upper; s >= 1; --s)
		f[s] = +LINF;

	for (int i = l; i <= r; ++i)
		for (int s = upper; s >= v[i]; --s)
			minimize(f[s], f[s - v[i]] + c[i]);
	
	return upper;
}

vector<int> selected;
ll L[LIM_S + 1], R[LIM_S + 1];
void trace(int s = LIM_S, int l = 1, int r = n)
{
	if (l == r)
	{
		if (s == v[l])
		{
			selected.push_back(l);
		}	

		return ;
	}

	int m = (l + r) >> 1;
	int sleft  = calc(L, l, m + 0);
	int sright = calc(R, m + 1, r);

	int mn = +INF;
	int pleft = 0;
	int pright = s;
	for (int v = max(0, s - sright); v <= min(s, sleft); ++v)
	{
		if (mn > L[v] + R[s - v])
		{
			mn = L[v] + R[s - v];
			pleft = v;
			pright = s - v;
		}
	}

	trace(pleft , l, m + 0);
	trace(pright, m + 1, r);
}

int main()
{
	cin >> n >> w;
	for (int i = 1; i <= n; ++i)
		cin >> c[i] >> v[i];

	int res = calc(f);
	while (f[res] > w) --res;
	trace(res);
	
	int ans = 0;
	for (int p : selected)
		ans += v[p];

	cout << ans;
	// cout << res << '\n';
	// cout << selected.size() << '\n';
	// for (int p : selected)
	// {
	// 	cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
	// }

	return 0;
}

• For the $$$ith$$$ query, input the $$$ith$$$ element and iterating all bitmasks with exactly $$$ith$$$ bits

• Optimization (DP bitmask): Effective and reduce $$$O(n)$$$ calculating time with the exchange of $$$O(2^N)$$$ space

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    ll res = 0;
    ll c[n], v[n];
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> v[i];
        int L = 1 << i;
        int R = 1 << (i + 1);
        for (int mask = L; mask < R; ++mask)
        {
            ll weight = 0;
            ll value = 0;
            for (int j = 1; j <= i; ++j)
            {
                if (mask >> j & 1)
                {
                    weight += c[j];
                    value += v[j];
                    if (weight > w) break;
                }
            }

            if (weight <= w)
            {
                maximize(res, value);
            }
        }

        cout << res << '\n';
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

const int LIM = 1 << 20;
ll dpc[LIM], dpv[LIM];
int main()
{
    int n, w;
    cin >> n >> w;

    ll res = 0;
    for (int i = 0; i < n; ++i)
    {
        ll c, v;
        cin >> c >> v;
        for (int mask = (1 << i); mask < (1 << (i + 1)); ++mask)
        {
            dpc[mask] = dpc[mask ^ (1 << i)] + c;
            dpv[mask] = dpv[mask ^ (1 << i)] + v;
            if (dpc[mask] <= w)
                maximize(res, dpv[mask]);
        }
        cout << res << '\n';
    }

    return 0;
}

• Let assume each item in deque is one way to fill up the bag with exact $$$weight$$$ and $$$value$$$

• For the $$$ith$$$ query, we will input the $$$ith$$$ item, then iterating for each element $$$e$$$ in deque to add to deque a new item that is the sum of $$$ith$$$ item and $$$e$$$ item

• Branch and bound (Eliminate all item whose weight > w) — Effective in normal — Highly effective when randomly generating weight

• Branch and bound (Minimizing weight / maximizing value) — Not recommended to use — The good thing is when one branch is used, it would eliminate $$$O(2^k)$$$ cases — The bad thing is it increases both theoretical and practical time and space complexity significantly

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

char __;
template<typename T>
void getUnsign(T &x)
{
    while (__ = getchar(), __ < '0' || __ > '9');
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');
}

template<typename T>
void getSigned(T &x)
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');

    if (sign) x = -x;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;

const int LIM = 0;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct item 
{
    ll weight;
    ll value;
    item (ll weight = 0, ll value = 0)
    : weight(weight), value(value) {}

    void operator += (const item &other)
    {
        weight += other.weight;
        value += other.value;
    }
};

int main()
{
	int n;
    ll w;
	cin >> n >> w;

    ll res = 0;
    deque<item> S;
    S.push_back(item(0, 0));
    for (int i = 1; i <= n; ++i)
    {
        ll c, v;
        cin >> c >> v;
        if (c > w) continue;

        deque<item> T;
        for (item e : S)
        {
            e += item(c, v);
            if (e.weight <= w)
            {
                T.push_back(e);
                maximize(res, e.value);
            }
        }

        for (const item &e : T)
            S.push_back(e);

        cout << res << '\n';
    }
    
	return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
#include <map>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

char __;
template<typename T>
void getUnsign(T &x)
{
    while (__ = getchar(), __ < '0' || __ > '9');
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');
}

template<typename T>
void getSigned(T &x)
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');

    if (sign) x = -x;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;

const int LIM = 0;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct item 
{
    ll weight;
    ll value;
    item (ll weight = 0, ll value = 0)
    : weight(weight), value(value) {}

    void operator += (const item &other)
    {
        weight += other.weight;
        value += other.value;
    }
};

map<ll, ll> minC;
map<ll, ll> maxV;
bool update(ll &c, ll &v)
{
    bool ok = false;
    if (minC.count(v) == false || minC[v] > c)
    {
        minC[v] = c;
        ok = true;
    }

    if (maxV.count(c) == false || maxV[c] < v)
    {
        maxV[c] = v;
        ok = true;
    }

    return ok;
}


int main()
{
	int n;
    ll w;
	cin >> n >> w;

    ll res = 0;
    deque<item> S;

    minC[0] = 0;
    maxV[0] = 0;
    S.push_back(item(0, 0));
    for (int i = 1; i <= n; ++i)
    {
        ll c, v;
        cin >> c >> v;
        if (c > w) continue;

        deque<item> T;
        for (item e : S)
        {
            e += item(c, v);
            if (e.weight > w) continue;
            if (update(e.weight, e.value))
            {
                T.push_back(e);
                maximize(res, e.value);
            }
        }

        for (const item &e : T)
            S.push_back(e);

        cout << res << '\n';
    }
    
	return 0;
}

• Let $$$f(i, s)$$$ is the answer for first $$$i$$$ items and limited by $$$s$$$ weight

• Base cases:

  • $$$s < 0$$$ means we use more weight then required, hence return a bag with negative infinity value
  • $$$i = 0$$$ and $$$s \geq 0$$$ means no item left, hence return an empty bag with 0 value

• Transistion:

  • $$$f(i - 1, s)$$$ = max value when not use this item
  • $$$f(i - 1, s - c_i) + v_i$$$ = max value when use this item
  • $$$f(i, s) = max(f(i - 1, s), f(i - 1, s - c_i) + v_i)$$$

• Optimization:

  • We can add a branch and bound that if prefix sum of weight is already smaller then we can return prefix sum of value.
  • This will make your algorithm faster by $$$O(2^k)$$$ for $$$k = max(p | \overset{p}{\underset{t = 1}{\Sigma}}(c_t) \leq w)$$$

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

char __;
template<typename T>
void getUnsign(T &x)
{
    while (__ = getchar(), __ < '0' || __ > '9');
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');
}

template<typename T>
void getSigned(T &x)
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');

    if (sign) x = -x;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;

const int LIM = 25;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n;
ll w;
ll c[LIM], v[LIM];
ll solve(int i, ll s)
{
    if (s < 0) return -LINF;
    if (i == 0) return 0;

    ll res = 0;
    maximize(res, solve(i - 1, s));
    maximize(res, solve(i - 1, s - c[i]) + v[i]);
    return res;
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> v[i];
        cout << solve(i, w) << '\n';
    }
	return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

char __;
template<typename T>
void getUnsign(T &x)
{
    while (__ = getchar(), __ < '0' || __ > '9');
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');
}

template<typename T>
void getSigned(T &x)
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');

    if (sign) x = -x;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;

const int LIM = 25;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n;
ll w;
ll c[LIM], psc[LIM];
ll v[LIM], psv[LIM];
ll solve(int i, ll s)
{
    if (s >= psc[i]) return psv[i];
    if (s < 0) return -LINF;
    if (i == 0) return 0;

    ll res = 0;
    maximize(res, solve(i - 1, s));
    maximize(res, solve(i - 1, s - c[i]) + v[i]);
    return res;
}

int main()
{
    cin >> n >> w;

    psc[0] = psv[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> v[i];
        psc[i] = psc[i - 1] + c[i];
        psv[i] = psv[i - 1] + v[i];
        cout << solve(i, w) << '\n';
    }
	return 0;
}

Let $$$f[0][s]$$$ be the end state instead of $$$f[n][w]$$$

Convert the transistion to $$$magic(i, s) \rightarrow magic(i - 1, s)$$$

For the $$$ith$$$ item, the answer right now is $$$magic(i, s)$$$ and here we done

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (s > w) return -LINF; /// Using too much weight
    if (i == 0) return 0;     /// No available item to add into the bag

    ll &res = f[i][s];
    if (res != -1) return res;
        
    maximize(res, magic(i - 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i - 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

int main()
{
    memset(f, -1, sizeof(f));

    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> v[i];
        cout << magic(i, 0) << '\n';
    }
    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

The answer is ofcourse $$$f[i][w]$$$ — upto the $$$ith$$$ item

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        int c, v;
        cin >> c >> v;

        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);
            if (s >= c)
            {
                maximize(f[i][s], f[i - 1][s - c] + v);
            }
        }

        cout << f[i][w] << '\n';
    }

    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

The answer is ofcourse $$$f[w]$$$ — upto the $$$ith$$$ item

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    ll f[w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        int c, v;
        cin >> c >> v;

        for (int s = w; s >= c; --s)
            maximize(f[s], f[s - c] + v);
    
        cout << f[w] << '\n';
    }

    return 0;
}

Let $$$f[0][s]$$$ be the end state instead of $$$f[n][w]$$$

Convert the transistion to $$$magic(i, s) \rightarrow magic(i - 1, s)$$$

For the $$$ith$$$ item, the answer right now is $$$result = max(k\ |\ magic(i, k) \leq w$$$

Break the loop after the answer each query is found

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i == 0) return (s == 0) ? 0 : +LINF;

    ll &res = f[i][s];
    if (res != -1) return res;
    res = +LINF;

    minimize(res, magic(i - 1, s - 0) + 0);
    minimize(res, magic(i - 1, s - v[i]) + c[i]);
    return res;
}

int main()
{
    cin >> n >> w;

    int sum = 0;
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> v[i];

        sum += v[i];
        for (int res = sum; res >= 0; --res)
        {
            if (magic(i, res) <= w)
            {
                cout << res << '\n';
                break;
            }
        }
    }

    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

Declare the dp array globally with limit size

The answer is ofcourse $$$res = max(k\ |\ f[i][k]) \leq w$$$ — upto the $$$ith$$$ item

Break the loop after the answer each query is found

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int LIMN = 100;
const int LIMSUM = 1e5 + 15;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

ll f[LIMN][LIMSUM];
int main()
{
    int n, w;
    cin >> n >> w;

    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        int c, v;
        cin >> c >> v;

        sum += v;
        for (int s = sum; s >= 0; --s)
        {
            f[i][s] = f[i - 1][s];

            if (s >= v)
            {
                minimize(f[i][s], f[i - 1][s - v] + c);
            }
        }

        for (int res = sum; res >= 0; --res)
        {
            if (f[i][res] <= w)
            {
                cout << res << '\n';
                break;
            }
        }
    }

    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

Declare the dp array globally with limit size

The answer is ofcourse $$$res = max(k\ |\ f[k]) \leq w$$$ — upto the $$$ith$$$ item

Break the loop after the answer each query is found

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int LIM = 1e6 + 16;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

ll f[LIM];
int main()
{
    int q, w;
    cin >> q >> w;

    memset(f, +LINF, sizeof(f));
    f[0] = 0;

    int sum = 0;
    while (q-->0) /// For each query
    {
        int c, v;
        cin >> c >> v;

        sum += v;
        for (int s = sum; s >= v; --s)
            minimize(f[s], f[s - v] + c);

        
        for (int res = sum; res >= 0; --res)
        {
            if (f[res] <= w)
            {
                cout << res << '\n';
                break;
            }
        }
    }

    return 0;
}

• All items whose weight bigger than the bag limit will be ignored
• All items whose weight equal the bag limit, we have the max value $$$V_1$$$
• All items whose weight less than the bag limit, we calculate it like above and have the max value $$$V_2$$$
• The result will be $$$res = max(V_1, V_2)$$$
• Highly effective for $$$type\ III$$$ knapsack whose testcases randomly generated that item weight can be much bigger than bag limit
• Less effective in normal testcases

• Lets $$$F(C_p, V_p) = $$$ number of existance of $$$(C_p, V_p)$$$ in the array
• Array with $$$F(C_p, V_p) = X > 2$$$ and $$$F(2C_p, 2V_p) = Y$$$ can be converted to $$$F(C_p, V_p) = X - 2$$$ and $$$F(2C_p, 2V_p) + 1)$$$ without changing the result
• Significant effective for testcases having many duplicated items in arrays
• Having the same idea. Significant effective when $$$\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$$$ we can have only $$$O(\sqrt{X})$$$ unique weight, no item whose weight is $$$C$$$ appeared more than twice
• Having the same idea. Significant effective when $$$\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$$$ we can have only $$$O(\sqrt{X})$$$ unique value, , no item whose value is $$$V$$$ appeared more than twice

long long weight = 0;
long long value = 0;

    ll maxval = 0;
    for (Node &x : Sr)
    {
        /// What if x.value > maxval ??
        x.maxval = maxval;
        x.maxmask = maxmask;
        if (maxval < x.value)
        {
            maxval = x.value;
            /// not update maxmask ?
        }
    }

    if (res < x.value + y.value) /// where is maxvalue ?
    {
        res = x.value + y.value;
        mask_l = y.mask;
        mask_r = x.mask;
    }

    if (res < x.maxval + y.value)
    {
        res = x.maxval + y.value;
        mask_l = y.mask;
        mask_r = x.mask; /// this mask might not given the maxval !
    }

    ll maxval = 0;
    int maxmask = 0;
    for (Node &x : Sr)
    {
        if (maxval < x.value)
        {
            maxval = x.value;
            maxmask = x.mask;
        }
        x.maxval = maxval;
        x.maxmask = maxmask;
    }

    if (res < x.maxval + y.value)
    {
        res = x.maxval + y.value;
        mask_l = y.mask;
        mask_r = x.maxmask;
    }

```cpp memset(f, +LINF, sizeof(f)); f[0][0] = 0;

int sum = 0;
for (int i = 1; i <= n; ++i)
{
    int c, v;
    cin >> c >> v;

    sum += v;
    for (int s = sum; s >= 1; --s) /// you have to make a loop from s = sum -> 0
    {
        f[i][s] = f[i - 1][s];

        if (s >= v)
        {
            minimize(f[i][s], f[i - 1][s - v] + c);
        }
    }

    for (int res = sum; res >= 0; --res)
    {
        if (f[i][res] <= w)
        {
            cout << res << '\n';
            break;
        }
    }
}

Assign this at the head of the function


void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = c.size(); /// Important !!!
    ...
}

or

void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = v.size(); /// Important !!!
    ...
}

ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll res = f[i][s]; /// is should be &res = [i][s]
    if (res != -1) return res;
    ll res = +LINF;

    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return res;
}

ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll res = +LINF;
    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return f[i][s] = res; /// It is calculated first then assigning dp value
}

    ll f[sum + 1];

    /// What if f[x > 0] negative ?
    f[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int s = sum; s >= v[i]; --s)
            minimize(f[s], f[s - v[i]] + c[i]);

    ll f[n + 1][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= sum; ++s)
        {
            f[i][s] = min(f[i][s - 1], f[i - 1][s]);

            if (s >= v[i])
            {
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
            }
        }
    }

    int res = 0;
    for (int l = 1, r = sum; l <= r; )
    {
        int m = (l + r) >> 1;
        if (f[n][m] <= w)
        {
            res = m;
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }
    cout << res;

    vector<int> selected;
    for (int i = n, s = w; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])
        {
            selected.push_back(i);
            i -= 1;
            s -= c[i];
        }

        if (f[i][s - 1] > f[i - 1][s])
        {
            --s;
        }
        else /// f[i][s] = f[i - 1][s]
        {
            --i;
        }
    }

    vector<int> selected;
    for (int i = n, s = w; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])
        {
            selected.push_back(i);
            s -= c[i]; /// This first then decrease (i)
            i -= 1;
            continue; /// <--- Important in this case
        }

        if (f[i][s - 1] > f[i - 1][s])
        {
            --s;
        }
        else /// f[i][s] = f[i - 1][s]
        {
            --i;
        }
    }

ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (i > n) return (s <= w) ? 0 : -LINF;     /// No available item to add into the bag

    ll &res = f[i][s]; /// what if (s > w) ?
    if (res != -1) return res;
        
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
        for (int s = w; s >= 0; --s)
            f[i][s] = max(f[i - 1][s], f[i - 1][s - c[i]] + v[i]); /// What if s < c[i] ?

Type $$$IV, V$$$ DP

The statement is in Italian Language

Translated into English: Given an array of length $$$N$$$, find the smallest sum $$$\geq K$$$ of a subset.

Limitation: $$$N,K \leq 5000 , a_i \leq 10^6$$$

Keep adding the items from largest to smallest until they dont fit in the knapsack

• Type $$$IV$$$ DP

• Type $$$V$$$ DP

• Trace

• Type $$$III$$$ DP

• Trace

• Type $$$III$$$ DP — Meet-in-the-middle Approach

• Trace

• Type $$$III$$$ DP — Meet-in-the-middle Approach

#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int p[n];
    iota(p, p + n, 0);

    ll res = 0;
    do {
        ll sum_weight = 0;
        ll sum_value = 0;
        for (int i = 0; i < n; ++i)
        {
            int weight = c[p[i]];
            int value = v[p[i]];

            sum_weight += weight;
            sum_value += value;
            if (sum_weight > w) 
            {
                break;
            }
            else
            {
                maximize(res, sum_value);
            }
        }

    }
    while (next_permutation(p, p + n));

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    ll res = 0;
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        int weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        if (weight <= w)
        {
            maximize(res, value);
        }
    }

    cout << res << endl;
    return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct Node 
{
    ll maxval = 0;

    ll value;
    int weight;
    Node (ll value = 0, int weight = 0)
    : value(value), weight(weight) {}
};

int n, w;
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = c.size(); /// Important !!!
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        ll weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        if (weight <= w)
        {
            S.push_back(Node(value, weight));
        }    
    }
}

int main()
{
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int m = n / 2;
    vector<int> cl, cr;
    vector<int> vl, vr;
    for (int i = 0; i < n; ++i)
    {
        if (i < m)
        {
            cl.push_back(c[i]);
            vl.push_back(v[i]);
        }
        else 
        {
            cr.push_back(c[i]);
            vr.push_back(v[i]);
        }
    }

    vector<Node> Sl, Sr;
    solve(cl, vl, Sl);
    solve(cr, vr, Sr);

    sort(all(Sr), [](const Node &a, const Node &b) {
        return (a.weight != b.weight) ? a.weight < b.weight : a.value < b.value;
    });

    ll maxval = 0;
    for (Node &x : Sr)
    {
        maximize(maxval, x.value);
        x.maxval = maxval;
    }

    ll res = 0;
    for (Node &y : Sl)
    {
        for (int l = 0, r = int(Sr.size()) - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            Node x = Sr[m];
            if (x.weight + y.weight <= w)
            {
                maximize(res, x.maxval + y.value);
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }
    }

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (s > w) return -LINF; /// Using too much weight
    if (i > n) return 0;     /// No available item to add into the bag

    ll &res = f[i][s];
    if (res != -1) return res;
        
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    memset(f, -1, sizeof(f));
    cout << magic();
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll res = 0;
    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            for (int j = 1; j < i; ++j)
            {
                for (int t = 0; t <= s; ++t)
                {
                    maximize(f[i][s], f[i][t] + 0);
                }
                
                for (int t = 0; t + c[i] <= s; ++t)
                {
                    maximize(f[i][s], f[i - 1][t] + v[i]);
                }
            }

            maximize(res, f[i][s]);
        }
    }

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = f[i - 1][s];
            if (s >= c[i])
            {
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
            }
        }
    }

    ll res = 0;
    for (int s = 0; s <= w; ++s)
        maximize(res, f[n][s]);

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);
            if (s >= c[i])
            {
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
            }
        }
    }

    cout << f[n][w];
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[2][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 1; s <= w; ++s)
        {
            f[cur][s] = f[pre][s];
            if (s >= c[i])
            {
                maximize(f[cur][s], f[pre][s - c[i]] + v[i]);
            }
        }
    }

    ll res = 0;
    for (int s = 0; s <= w; ++s)
        maximize(res, f[n & 1][s]);

    cout << res;
    return 0;
}

    ll f[2][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 1; s <= w; ++s)
            f[cur][s] = f[pre][s];
        
        for (int s = w; s >= c[i]; --s)
            maximize(f[cur][s], f[pre][s - c[i]] + v[i]);
    }

    ll f[w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 1; s <= w; ++s) /// Unneeded loop
            f[s] = f[s];
        
        for (int s = w; s >= c[i]; --s)
            maximize(f[s], f[s - c[i]] + v[i]);
    }

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = c; s <= w; ++s)
                maximize(f[s], f[s - c] + v);

        equivalent to

            for (int s = c; s <= w; ++s)
                maximize(f[cur][s], f[cur][s - c] + v);

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = w; s >= c; --s)
                maximize(f[s], f[s - c] + v);

        equivalent

            for (int s = w; s >= c; --s)
                maximize(f[cur][s], f[pre][s - c] + v);

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
        for (int s = w; s >= c[i]; --s)
            maximize(f[s], f[s - c[i]] + v[i]);

    cout << f[w];
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll &res = f[i][s];
    if (res != -1) return res;
    res = +LINF;

    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return res;
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    memset(f, -1, sizeof(f));
    for (int res = sum; res >= 0; --res)
    {
        if (magic(1, res) <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[n + 1][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int s = 0; s <= sum; ++s)
        {
            f[i][s] = f[i - 1][s];

            if (s >= v[i])
            {
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
            }
        }
    }

    for (int res = sum; res >= 0; --res)
    {
        if (f[n][res] <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[2][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 0; s <= sum; ++s)
        {
            f[cur][s] = f[pre][s];

            if (s >= v[i])
            {
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);
            }
        }
    }

    for (int res = sum; res >= 0; --res)
    {
        if (f[n & 1][res] <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

    ll f[2][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 0; s <= sum; ++s)
        {
            f[cur][s] = f[pre][s];

            if (s >= v[i])
            {
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);
            }
        }
    }

    ll f[2][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1;
        bool pre = !cur;

        for (int s = 0; s <= w; ++s) /// Unneeded loop
            f[s] = f[s];
        
        for (int s = sum; s >= v[i]; --s)
            minimize(f[s], f[s - v[i]] + c[i]);
    }

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = v[i]; s <= sum; ++s)
                minimize(f[s], f[s - v[i]] + c[i]);

        equivalent to

            for (int s = v[i]; s <= sum; ++s)
                minimize(f[cur][s], f[cur][s - v[i]] + c[i]);

        for which

            f[cur][s] = f[s] that updated
            f[pre][s] = f[s] that not update yet

        the part

            for (int s = sum; s >= v[i] --s)
                minimize(f[s], f[s - v[i]] + c[i]);

        equivalent to

            for (int s = sum; s >= v[i] --s)
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[sum + 1];
    memset(f, +LINF, sizeof(f));

    f[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int s = sum; s >= v[i]; --s)
            minimize(f[s], f[s - v[i]] + c[i]);

    for (int res = sum; res >= 0; --res)
    {
        if (f[res] <= w)
        {
            cout << res;
            return 0;
        }
    }

    return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int p[n];
    iota(p, p + n, 0);

    vector<int> selected;
    ll res = 0;
    do {
        bool better = false;
        vector<int> current;
        ll sum_weight = 0;
        ll sum_value = 0;
        for (int i = 0; i < n; ++i)
        {
            int weight = c[p[i]];
            int value = v[p[i]];

            sum_weight += weight;
            sum_value += value;
            if (sum_weight > w) 
            {
                break;
            }
            else
            {
               current.push_back(p[i]);
                if (res < sum_value)
                {
                    better = true;
                    res = sum_value;
                }
            }
        }

        if (better) selected = current;
    }
    while (next_permutation(p, p + n));

    cout << res << '\n';
    sort(selected.begin(), selected.end());
    for (int p : selected)
    {
        cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    ll res = 0;
    int selected = 0;
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        ll weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        if (weight <= w)
        {
            if (res <= value)
            {
                res = value;
                selected = mask;
            }
        }
    }

    cout << res << '\n';
    for (int i = 0; i < n; ++i)
    {
        if (selected >> i & 1)
        {
            cout << i + 1 << ' ' << c[i] << ' ' << v[i] << '\n';
        }
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct Node 
{
    ll maxval = 0;
    int maxmask = 0;

    int mask;
    ll value;
    int weight;
    Node (int mask = 0, ll value = 0, int weight = 0)
    : mask(mask), value(value), weight(weight) {}
};

int n, w;
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = c.size(); /// Important !!!
    int lim = 1 << n;
    for (int mask = 0; mask < lim; ++mask)
    {
        ll weight = 0;
        ll value = 0;
        for (int i = 0; i < n; ++i)
        {
            if (mask >> i & 1)
            {
                weight += c[i];
                value += v[i];
                if (weight > w) break;
            }
        }

        S.push_back(Node(mask, value, weight));
    }
}

int main()
{
    cin >> n >> w;

    int c[n], v[n];
    for (int i = 0; i < n; ++i)
        cin >> c[i] >> v[i];

    int m = n / 2;
    vector<int> cl, vl;
    for (int i = 0; i < m; ++i)
    {
        cl.push_back(c[i]);
        vl.push_back(v[i]);
    }

    vector<int> cr, vr;
    for (int i = m; i < n; ++i)
    {
        cr.push_back(c[i]);
        vr.push_back(v[i]);
    }

    vector<Node> Sl, Sr;
    solve(cl, vl, Sl);
    solve(cr, vr, Sr);

    sort(all(Sr), [](const Node &a, const Node &b) {
        return (a.weight != b.weight) ? a.weight < b.weight : a.value > b.value;
    });

    ll maxval = 0;
    int maxmask = 0;
    for (Node &x : Sr)
    {
        if (maxval < x.value)
        {
            maxval = x.value;
            maxmask = x.mask;
        }
        x.maxval = maxval;
        x.maxmask = maxmask;
    }

    ll res = 0;
    int mask_l = 0;
    int mask_r = 0;
    for (Node &y : Sl)
    {
        for (int l = 0, r = int(Sr.size()) - 1; l <= r; )
        {
            int m = (l + r) >> 1;
            Node x = Sr[m];
            if (x.weight + y.weight <= w)
            {
                if (res < x.maxval + y.value)
                {
                    res = x.maxval + y.value;
                    mask_l = y.mask;
                    mask_r = x.maxmask;
                }
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }
    }

    vector<int> selected;
    for (int i = 0; i < m; ++i)
        if (mask_l >> i & 1)
            selected.push_back(i);

    for (int i = 0; i < n - m; ++i)
        if (mask_r >> i & 1)
            selected.push_back(i + m);

    cout << res << '\n';
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';
    }

    return 0;
}

• $$$magic(i,s) = magic(i + 1,s + c[i]) + v[i])$$$ take this element will lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s + c[i])+ v[i]$$$ take this element wont lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s + c[i])+ v[i]$$$ either you take or not, you will find best result

• When $$$magic(i, s) = magic(X, Y)$$$, trace to next state $$$(i = X, s = Y)$$$

• When $$$magic(i, s) = magic(X, Y) = magic(P, Q)$$$, you can either trace to next state $$$(i = X, s = Y)$$$ or $$$(i = P, s = Q)$$$

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (s > w) return -LINF; /// Using too much weight
    if (i > n) return 0;     /// No available item to add into the bag

    ll &res = f[i][s];
    if (res != -1) return res;
        
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

vector<int> selected;
void trace(int i = 1, int s = 0)
{
    if (s > w) return ;
    if (i > n) return ;

    ll res = magic(i, s);
    if (res == magic(i + 1, s + 0) + 0)
    {
        return trace(i + 1, s + 0);
    }
    else 
    {
        selected.push_back(i);
        return trace(i + 1, s + c[i]);
    }
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    memset(f, -1, sizeof(f));
    cout << magic() << '\n';

    trace();
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);
            if (s >= c[i])
            {
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);
            }
        }
    }

    vector<int> selected;
    for (int i = n, s = w; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])
        {
            selected.push_back(i);
            s -= c[i];
            i -= 1;
            continue;
        }

        if (f[i][s - 1] > f[i - 1][s])
        {
            --s;
        }
        else /// f[i][s] = f[i - 1][s]
        {
            --i;
        }
    }

    cout << f[n][w] << '\n';
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
    }
    return 0;
}

• The idea is based on Lusterdawn's explanation and jiangly's solution

• Let $$$calc(*f, l, r)$$$ is the function that calculate the answer for items $$$l, l + 1, \dots, r$$$ with $$$*f$$$ the 1D memorization table

• For convention, let $$$calc$$$ return the value of $$$min(w, \overset{r}{\underset{i = l}{\Sigma}} c_i)$$$ — maximal possible weight created

• First we calculate $$$calc(*f, 1, n)$$$, after having the maximal value of the whole items, we can find the minimal weight that return such value. Or $$$weight_used = min(p | f[p] = res)$$$

• Let $$$trace(s, l, r)$$$ is the function that tracing for all elements, whose sum weight equal $$$s$$$ and sum value is max

• If $$$(l = r)$$$, we will consider to select this item or not. (This item is selected when $$$s = c_l$$$)

• Split the items into two halves: $$$[l, m]$$$ and $$$(m, r]$$$ and then calculate DP: $$$sleft = calc(*L, l, m + 0)$$$ and $$$sright = calc(*R, m + 1, r)$$$

• We find such $$$pleft$$$ and $$$pright$$$ satisfy $$$pleft + pright = s$$$ that returning $$$max(L[pleft] + R[pright])$$$. Then we trace from $$$trace(pleft, l, m + 0)$$$ to $$$trace(pright, m + 1, r)$$$ (ordered selected item)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
	
using namespace std;
	
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
	
typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
	
const int LIM_N = 111;
const int LIM_W = 1e6 + 16;
	
int n, w;
int c[LIM_N], v[LIM_N];
ll f[LIM_W];

int calc(ll *f, int l = 1, int r = n)
{
	ll upper = 0;
	for (int i = l; i <= r; ++i)
		upper += c[i];
	
	minimize(upper, (ll)w);
	for (int s = 0; s <= upper; ++s)
		f[s] = 0;
	
	for (int i = l; i <= r; ++i)
		for (int s = upper; s >= c[i]; --s)
			maximize(f[s], f[s - c[i]] + v[i]);
	
	return upper;
}
	
ll L[LIM_W], R[LIM_W];
vector<int> selected;
void trace(int s = w, int l = 1, int r = n)
{
	if (l == r)
	{
		if (s == c[l])
		{
			selected.push_back(l);
		}
	
		return ;
	}
	
	int m = (l + r) >> 1;
	int sleft  = calc(L, l, m + 0);
	int sright = calc(R, m + 1, r);
	
	ll mx = -1;
	int pleft = 0;
	int pright = s;
	for (int v = max(0, s - sright); v <= min(s, sleft); ++v)
	{
		if (mx < L[v] + R[s - v])
		{
			mx = L[v] + R[s - v];
			pleft = v;
			pright = s - v;
		}
	}
	
	trace(pleft , l, m + 0);
	trace(pright, m + 1, r);
}
		
int main()
{
	cin >> n >> w;
	for (int i = 1; i <= n; ++i)
		cin >> c[i] >> v[i];
	
	calc(f);
	ll res = f[w];
	int weight_used = max_element(f, f + w + 1) - f;
	
	trace(weight_used);	
	cout << res << '\n';	
	cout << selected.size() << '\n';
	for (int p : selected)
	{
	    cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
	}
	return 0;
}

• $$$magic(i,s) = magic(i + 1,s - v[i]) + c[i])$$$ take this element will lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s - v[i]) + c[i]$$$ take this element wont lead to the best result

• $$$magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s - v[i]) + c[i]$$$ either you take or not, you will find best result

• When $$$magic(i, s) = magic(X, Y)$$$, trace to next state $$$(i = X, s = Y)$$$

• When $$$magic(i, s) = magic(X, Y) = magic(P, Q)$$$, you can either trace to next state $$$(i = X, s = Y)$$$ or $$$(i = P, s = Q)$$$

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll &res = f[i][s];
    if (res != -1) return res;
    res = +LINF;

    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return res;
}

vector<int> selected;
void trace(int i = 1, int s = 0)
{
    if (s < 0) return ;
    if (i > n) return ;

    ll res = magic(i, s);
    if (res == magic(i + 1, s + 0) + 0)
    {
        return trace(i + 1, s + 0);
    }
    else 
    {
        selected.push_back(i);
        return trace(i + 1, s - v[i]);
    }
}

int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    memset(f, -1, sizeof(f));
    for (int res = sum; res >= 0; --res)
    {
        if (magic(1, res) <= w)
        {
            trace(1, res);
            
            cout << res << '\n';
            cout << selected.size() << '\n';
            for (int p : selected)
            {
                cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
            }
            return 0;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    int c[n + 1], v[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> c[i] >> v[i];

    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += v[i];

    ll f[n + 1][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int s = 0; s <= sum; ++s)
        {
            f[i][s] = f[i - 1][s];

            if (s >= v[i])
            {
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
            }
        }
    }

    int res = sum;
    while (f[n][res] > w) --res;
    
    vector<int> selected;
    for (int i = n, s = res; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - v[i]] + c[i])
        {
            selected.push_back(i);
            s -= v[i];
            i -= 1;
        }
        else 
        {
            --i;
        }
    }

    cout << res << '\n';
    cout << selected.size() << '\n';
    for (int p : selected)
    {
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
    }
    return 0;
}

• Let $$$calc(*f, l, r)$$$ is the function that calculate the answer for items $$$l, l + 1, \dots, r$$$ with $$$*f$$$ the 1D memorization table

• For convention, let $$$calc$$$ return the value of $$$\overset{r}{\underset{i = l}{\Sigma}} v_i$$$ — maximal possible value created

• First we calculate $$$calc(*f, 1, n)$$$, after having the minimal weight of the whole items, we can find the maximal value that return such weight. Or $$$res = max(p | f[p] \leq w)$$$

• Let $$$trace(s, l, r)$$$ is the function that tracing for all elements, whose sum value equal $$$s$$$ and sum weight is min

• If $$$(l = r)$$$, we will consider to select this item or not. (This item is selected when $$$s = v_l$$$)

• Split the items into two halves: $$$[l, m]$$$ and $$$(m, r]$$$ and then calculate DP: $$$sleft = calc(*L, l, m + 0)$$$ and $$$sright = calc(*R, m + 1, r)$$$

• We find such $$$pleft$$$ and $$$pright$$$ satisfy $$$pleft + pright = s$$$ that returning $$$min(L[pleft] + R[pright])$$$. Then we trace from $$$trace(pleft, l, m + 0)$$$ to $$$trace(pright, m + 1, r)$$$ (ordered selected item)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
	
using namespace std;
	
template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
	
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
	
const int LIM_N = 111;
const int LIM_S = 1e6 + 16;
	
int n, w;
int c[LIM_N], v[LIM_N];
ll f[LIM_S + 1];

int calc(ll *f, int l = 1, int r = n)
{
	int upper = 0;
	for (int i = l; i <= r; ++i)
		upper += v[i];

	f[0] = 0;
	for (int s = upper; s >= 1; --s)
		f[s] = +LINF;

	for (int i = l; i <= r; ++i)
		for (int s = upper; s >= v[i]; --s)
			minimize(f[s], f[s - v[i]] + c[i]);
	
	return upper;
}

vector<int> selected;
ll L[LIM_S + 1], R[LIM_S + 1];
void trace(int s = LIM_S, int l = 1, int r = n)
{
	if (l == r)
	{
		if (s == v[l])
		{
			selected.push_back(l);
		}	

		return ;
	}

	int m = (l + r) >> 1;
	int sleft  = calc(L, l, m + 0);
	int sright = calc(R, m + 1, r);

	int mn = +INF;
	int pleft = 0;
	int pright = s;
	for (int v = max(0, s - sright); v <= min(s, sleft); ++v)
	{
		if (mn > L[v] + R[s - v])
		{
			mn = L[v] + R[s - v];
			pleft = v;
			pright = s - v;
		}
	}

	trace(pleft , l, m + 0);
	trace(pright, m + 1, r);
}

int main()
{
	cin >> n >> w;
	for (int i = 1; i <= n; ++i)
		cin >> c[i] >> v[i];

	int res = calc(f);
	while (f[res] > w) --res;
	trace(res);
	
	int ans = 0;
	for (int p : selected)
		ans += v[p];

	cout << ans;
	// cout << res << '\n';
	// cout << selected.size() << '\n';
	// for (int p : selected)
	// {
	// 	cout << p << ' ' << c[p] << ' ' << v[p] << '\n';
	// }

	return 0;
}

Let $$$f[0][s]$$$ be the end state instead of $$$f[n][w]$$$

Convert the transistion to $$$magic(i, s) \rightarrow magic(i - 1, s)$$$

For the $$$ith$$$ item, the answer right now is $$$magic(i, s)$$$ and here we done

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXW = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (s > w) return -LINF; /// Using too much weight
    if (i == 0) return 0;     /// No available item to add into the bag

    ll &res = f[i][s];
    if (res != -1) return res;
        
    maximize(res, magic(i - 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i - 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

int main()
{
    memset(f, -1, sizeof(f));

    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> v[i];
        cout << magic(i, 0) << '\n';
    }
    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

The answer is ofcourse $$$f[i][w]$$$ — upto the $$$ith$$$ item

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        int c, v;
        cin >> c >> v;

        for (int s = 1; s <= w; ++s)
        {
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);
            if (s >= c)
            {
                maximize(f[i][s], f[i - 1][s - c] + v);
            }
        }

        cout << f[i][w] << '\n';
    }

    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

The answer is ofcourse $$$f[w]$$$ — upto the $$$ith$$$ item

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    int n, w;
    cin >> n >> w;

    ll f[w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        int c, v;
        cin >> c >> v;

        for (int s = w; s >= c; --s)
            maximize(f[s], f[s - c] + v);
    
        cout << f[w] << '\n';
    }

    return 0;
}

Let $$$f[0][s]$$$ be the end state instead of $$$f[n][w]$$$

Convert the transistion to $$$magic(i, s) \rightarrow magic(i - 1, s)$$$

For the $$$ith$$$ item, the answer right now is $$$result = max(k\ |\ magic(i, k) \leq w$$$

Break the loop after the answer each query is found

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101;
const int MAXSUM = 101010;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, w;
int c[MAXN];
int v[MAXN];
ll f[MAXN][MAXSUM];
ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i == 0) return (s == 0) ? 0 : +LINF;

    ll &res = f[i][s];
    if (res != -1) return res;
    res = +LINF;

    minimize(res, magic(i - 1, s - 0) + 0);
    minimize(res, magic(i - 1, s - v[i]) + c[i]);
    return res;
}

int main()
{
    cin >> n >> w;

    int sum = 0;
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> v[i];

        sum += v[i];
        for (int res = sum; res >= 0; --res)
        {
            if (magic(i, res) <= w)
            {
                cout << res << '\n';
                break;
            }
        }
    }

    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

Declare the dp array globally with limit size

The answer is ofcourse $$$res = max(k\ |\ f[i][k]) \leq w$$$ — upto the $$$ith$$$ item

Break the loop after the answer each query is found

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int LIMN = 100;
const int LIMSUM = 1e5 + 15;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

ll f[LIMN][LIMSUM];
int main()
{
    int n, w;
    cin >> n >> w;

    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        int c, v;
        cin >> c >> v;

        sum += v;
        for (int s = sum; s >= 0; --s)
        {
            f[i][s] = f[i - 1][s];

            if (s >= v)
            {
                minimize(f[i][s], f[i - 1][s - v] + c);
            }
        }

        for (int res = sum; res >= 0; --res)
        {
            if (f[i][res] <= w)
            {
                cout << res << '\n';
                break;
            }
        }
    }

    return 0;
}

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.

Declare the dp array globally with limit size

The answer is ofcourse $$$res = max(k\ |\ f[k]) \leq w$$$ — upto the $$$ith$$$ item

Break the loop after the answer each query is found

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int LIM = 1e6 + 16;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

ll f[LIM];
int main()
{
    int q, w;
    cin >> q >> w;

    memset(f, +LINF, sizeof(f));
    f[0] = 0;

    int sum = 0;
    while (q-->0) /// For each query
    {
        int c, v;
        cin >> c >> v;

        sum += v;
        for (int s = sum; s >= v; --s)
            minimize(f[s], f[s - v] + c);

        
        for (int res = sum; res >= 0; --res)
        {
            if (f[res] <= w)
            {
                cout << res << '\n';
                break;
            }
        }
    }

    return 0;
}

• All items whose weight bigger than the bag limit will be ignored
• All items whose weight equal the bag limit, we have the max value $$$V_1$$$
• All items whose weight less than the bag limit, we calculate it like above and have the max value $$$V_2$$$
• The result will be $$$res = max(V_1, V_2)$$$
• Highly effective for $$$type\ III$$$ knapsack whose testcases randomly generated that item weight can be much bigger than bag limit
• Less effective in normal testcases

• Lets $$$F(C_p, V_p) = $$$ number of existance of $$$(C_p, V_p)$$$ in the array
• Array with $$$F(C_p, V_p) = X > 2$$$ and $$$F(2C_p, 2V_p) = Y$$$ can be converted to $$$F(C_p, V_p) = X - 2$$$ and $$$F(2C_p, 2V_p) + 1)$$$ without changing the result
• Significant effective for testcases having many duplicated items in arrays
• Having the same idea. Significant effective when $$$\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$$$ we can have only $$$O(\sqrt{X})$$$ unique weight, no item whose weight is $$$C$$$ appeared more than twice
• Having the same idea. Significant effective when $$$\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$$$ we can have only $$$O(\sqrt{X})$$$ unique value, , no item whose value is $$$V$$$ appeared more than twice

long long weight = 0;
long long value = 0;

    ll maxval = 0;
    for (Node &x : Sr)
    {
        /// What if x.value > maxval ??
        x.maxval = maxval;
        x.maxmask = maxmask;
        if (maxval < x.value)
        {
            maxval = x.value;
            /// not update maxmask ?
        }
    }

    if (res < x.value + y.value) /// where is maxvalue ?
    {
        res = x.value + y.value;
        mask_l = y.mask;
        mask_r = x.mask;
    }

    if (res < x.maxval + y.value)
    {
        res = x.maxval + y.value;
        mask_l = y.mask;
        mask_r = x.mask; /// this mask might not given the maxval !
    }

    ll maxval = 0;
    int maxmask = 0;
    for (Node &x : Sr)
    {
        if (maxval < x.value)
        {
            maxval = x.value;
            maxmask = x.mask;
        }
        x.maxval = maxval;
        x.maxmask = maxmask;
    }

    if (res < x.maxval + y.value)
    {
        res = x.maxval + y.value;
        mask_l = y.mask;
        mask_r = x.maxmask;
    }

    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        int c, v;
        cin >> c >> v;

        sum += v;
        for (int s = sum; s >= 1; --s) /// you have to make a loop from s = sum -> 0
        {
            f[i][s] = f[i - 1][s];

            if (s >= v)
            {
                minimize(f[i][s], f[i - 1][s - v] + c);
            }
        }

        for (int res = sum; res >= 0; --res)
        {
            if (f[i][res] <= w)
            {
                cout << res << '\n';
                break;
            }
        }
    }

Assign this at the head of the function


void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = c.size(); /// Important !!!
    ...
}

or

void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)
{
    int n = v.size(); /// Important !!!
    ...
}

ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll res = f[i][s]; /// is should be &res = [i][s]
    if (res != -1) return res;
    ll res = +LINF;

    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return res;
}

ll magic(int i = 1, int s = 0)
{
    if (s < 0) return +LINF;
    if (i > n) return (s == 0) ? 0 : +LINF;

    ll res = +LINF;
    minimize(res, magic(i + 1, s - 0) + 0);
    minimize(res, magic(i + 1, s - v[i]) + c[i]);
    return f[i][s] = res; /// It is calculated first then assigning dp value
}

    ll f[sum + 1];

    /// What if f[x > 0] negative ?
    f[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int s = sum; s >= v[i]; --s)
            minimize(f[s], f[s - v[i]] + c[i]);

    ll f[n + 1][sum + 1];
    memset(f, +LINF, sizeof(f));
    f[0][0] = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (int s = 1; s <= sum; ++s)
        {
            f[i][s] = min(f[i][s - 1], f[i - 1][s]);

            if (s >= v[i])
            {
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);
            }
        }
    }

    int res = 0;
    for (int l = 1, r = sum; l <= r; )
    {
        int m = (l + r) >> 1;
        if (f[n][m] <= w)
        {
            res = m;
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }
    cout << res;

    vector<int> selected;
    for (int i = n, s = w; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])
        {
            selected.push_back(i);
            i -= 1;
            s -= c[i];
        }

        if (f[i][s - 1] > f[i - 1][s])
        {
            --s;
        }
        else /// f[i][s] = f[i - 1][s]
        {
            --i;
        }
    }

    vector<int> selected;
    for (int i = n, s = w; i >= 1 && s >= 1; )
    {
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])
        {
            selected.push_back(i);
            s -= c[i]; /// This first then decrease (i)
            i -= 1;
            continue; /// <--- Important in this case
        }

        if (f[i][s - 1] > f[i - 1][s])
        {
            --s;
        }
        else /// f[i][s] = f[i - 1][s]
        {
            --i;
        }
    }

ll f[MAXN][MAXW];
ll magic(int i = 1, int s = 0)
{
    if (i > n) return (s <= w) ? 0 : -LINF;     /// No available item to add into the bag

    ll &res = f[i][s]; /// what if (s > w) ?
    if (res != -1) return res;
        
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item
    return res;
}

    ll f[n + 1][w + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
        for (int s = w; s >= 0; --s)
            f[i][s] = max(f[i - 1][s], f[i - 1][s - c[i]] + v[i]); /// What if s < c[i] ?

Type $$$IV, V$$$ DP

The statement is in Italian Language

Translated into English: Given an array of length $$$N$$$, find the smallest sum $$$\geq K$$$ of a subset.

Limitation: $$$N,K \leq 5000 , a_i \leq 10^6$$$

Keep adding the items from largest to smallest until they dont fit in the knapsack

Given a string with 3 types of barracks '()', '[]', '{}'. Calculate minimum number of charactor need to add into string that make it a valid parentheses string.

My question: Solve the problem in $$$O(n^2\ polylog)$$$ or lower

My detailed question is below

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]
int solve(int l = 0, int r = n - 1)
{
    if (l > r) return 0; /// empty substring
    if (l == r) return 1; /// dont pair with other

    int &res = f[l][r];
    if (res != +INF) return res; /// calculated

    if (match(s[l], s[r])) /// paired up, no error
    {
        res = 0 + solve(l + 1, r - 1);
    }
        
    /// Split string into 2 halves
    /// s[l..r] = s[l..k] + s[k+1..r]
    /// f[l..r] = min(f[l..k] + f[k+1..r])
    for (int k = l; k < r; ++k)
    {
        minimize(res, solve(l, k) + solve(k + 1, r));
    }

   return res;
}

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]
int solve()
{
    memset(f, 0, sizeof(f));
    for (int r = 0; r < n; ++r)
    {
        for (int l = r; l >= 0; --l)
        {
            f[l][r] = r - l + 1; /// Add one charactor to each one
            if (match(s[l], s[r])) /// Outside make a good pair of string
            {
                f[l][r] = f[l+1][r-1];
            }

            /// Split string into 2 halves
            /// s[l..r] = s[l..k] + s[k+1..r]
            /// f[l..r] = min(f[l..k] + f[k+1..r])
            for (int k = l; k < r; ++k)
            {
                minimize(f[l][r], f[l][k] + f[k+1][r]);
            }
        }
    }

    return f[0][n - 1];
}

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

const int LIM = 1010;
const int INF = 0x3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n;
string s;

///// One variation
//int solve()
//{
//    int res = 0, diff = 0;
//    for (char c : s)
//    {
//        diff += (c == '(') ? +1 : -1;
//        if (diff < 0)
//        {
//            diff = 0;
//            ++res;
//        }
//    }
//    res += diff;
//
//    return res;
//}

bool match(char l, char r)
{
    return (l == '(' && r == ')')
        || (l == '[' && r == ']')
        || (l == '{' && r == '}');
}

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]

/// Iterative
int solve()
{
    memset(f, 0, sizeof(f));
    for (int r = 0; r < n; ++r)
    {
        for (int l = r; l >= 0; --l)
        {
            f[l][r] = r - l + 1; /// Add one charactor to each one
            if (match(s[l], s[r])) /// Outside make a good pair of string
            {
                f[l][r] = f[l+1][r-1];
            }

            /// Split string into 2 halves
            /// s[l..r] = s[l..k] + s[k+1..r]
            /// f[l..r] = min(f[l..k] + f[k+1..r])
            for (int k = l; k < r; ++k)
            {
                minimize(f[l][r], f[l][k] + f[k+1][r]);
            }
        }
    }

    return f[0][n - 1];
}

/// Recursive
//int solve(int l = 0, int r = n - 1)
//{
//    if (l > r) return 0; /// empty substring
//    if (l == r) return 1; /// dont pair with other
//
//    int &res = f[l][r];
//    if (res != +INF) return res; /// calculated
//
//    if (match(s[l], s[r])) /// paired up, no error
//    {
//        res = 0 + solve(l + 1, r - 1);
//    }
//
//     /// Split string into 2 halves
//     /// s[l..r] = s[l..k] + s[k+1..r]
//     /// f[l..r] = min(f[l..k] + f[k+1..r])
//     for (int k = l; k < r; ++k)
//     {
//         minimize(res, solve(l, k) + solve(k + 1, r));
//     }

//    return res;
// }


int main()
{
    file();
    cin >> s;
    n = s.size();

    memset(f, +INF, sizeof(f));
    cout << solve();
    return 0;
}

int n;
string s;
int f[LIM][LIM];
int magic(int l = 0, int r = n - 1)
{
    /// Base cases
    if (l > r)  return 0; /// Empty string
    if (l == r) return 1; /// Add one charactor to pair it up

    int &res = f[l][r];
    if (res != +INF) return res;

    // Branch and bound cases
    if (isClose(s[l]))         return res = magic(l + 1, r - 0) + 1; // Useless leftmost
    if (isOpen(s[r]))          return res = magic(l + 0, r - 1) + 1; // Useless rightmost
    if (match(s[l], s[l + 1])) return res = magic(l + 2, r - 0) + 0; // Leftmost paired
    if (match(s[r - 1], s[r])) return res = magic(l + 0, r - 2) + 0; // Rightmost paired

    /// Main cases
    for (int k = l; k <= r; ++k)
    {
        if (match(s[k], s[r])) // Match s[k] and s[r]
        {
            minimize(res, magic(l, k - 1) + 0 + magic(k + 1, r - 1));
        }
        else // Insert open barrack at s[k]
        {
            minimize(res, magic(l, k - 0) + 1 + magic(k + 1, r - 1));
        }
    }

    return res;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

char __;
template<typename T>
void getUnsign(T &x)
{
    while (__ = getchar(), __ < '0' || __ > '9');
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');
}

template<typename T>
void getSigned(T &x)
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');

    if (sign) x = -x;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;
const int LIM = 1010;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

bool isOpen(char c)  { return (c == '(') || (c == '[') || (c == '{'); }
bool isClose(char c) { return (c == ')') || (c == ']') || (c == '}'); }
bool match(char l, char r)
{
    return (l == '(' && r == ')')
        || (l == '[' && r == ']')
        || (l == '{' && r == '}');
}

char toMatch(char c)
{
    if (c == '(') return ')';
    if (c == '[') return ']';
    if (c == '{') return '}';
    if (c == ')') return '(';
    if (c == ']') return '[';
    if (c == '}') return '{';
}

int n;
string s;
int f[LIM][LIM];
int magic(int l = 0, int r = n - 1)
{
    /// Base cases
    if (l > r)  return 0; /// Empty string
    if (l == r) return 1; /// Add one charactor to pair it up

    int &res = f[l][r];
    if (res != +INF) return res;

    // Branch and bound cases
    if (isClose(s[l]))         return res = magic(l + 1, r - 0) + 1; // Useless leftmost
    if (isOpen(s[r]))          return res = magic(l + 0, r - 1) + 1; // Useless rightmost
    if (match(s[l], s[l + 1])) return res = magic(l + 2, r - 0) + 0; // Leftmost paired
    if (match(s[r - 1], s[r])) return res = magic(l + 0, r - 2) + 0; // Rightmost paired

    /// Main cases
    for (int k = l; k <= r; ++k)
    {
        if (match(s[k], s[r])) // Match s[k] and s[r]
        {
            minimize(res, magic(l, k - 1) + 0 + magic(k + 1, r - 1));
        }
        else // Insert open barrack at s[k]
        {
            minimize(res, magic(l, k - 0) + 1 + magic(k + 1, r - 1));
        }
    }

    return res;
}

int main()
{
    cin >> s;
    n = s.size();

    memset(f, +INF, sizeof(f));
    cout << magic();
    return 0;
}

Instead of make a for loop of every possible cases for $$$k$$$. Just pick the places where the barrack match to $$$S_r$$$ exists in substring $$$S[l..r]$$$. Hence optimize the algorithm by 8 times

int n;
string s;
/// p[c][x]: Minimum position >= x with charactor c (s[p[c][x]] = c)
int p[256][LIM];
int f[LIM][LIM];
int magic(int l = 0, int r = n - 1)
{
    /// Base cases
    if (l > r)  return 0; /// Empty string
    if (l == r) return 1; /// Add one charactor to pair it up

    int &res = f[l][r];
    if (res != +INF) return f[l][r];

    // Branch and bound cases
    if (isClose(s[l]))         return res = magic(l + 1, r - 0) + 1; // Useless leftmost
    if (isOpen(s[r]))          return res = magic(l + 0, r - 1) + 1; // Useless rightmost
    if (match(s[l], s[l + 1])) return res = magic(l + 2, r - 0) + 0; // Leftmost paired
    if (match(s[r - 1], s[r])) return res = magic(l + 0, r - 2) + 0; // Rightmost paired

    /// Main cases
    bool ok = false;
    int need = toMatch(s[r]);
    for (int k = p[need][l]; k < r; k = p[need][k + 1])
    {
        minimize(res, magic(l, k - 1) + 0 + magic(k + 1, r - 1));
    }

    minimize(res, magic(l, r - 1) + 1);
    return res;
}

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
#include <ctime>
#include <map>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

char __;
template<typename T>
void getUnsign(T &x)
{
    while (__ = getchar(), __ < '0' || __ > '9');
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');
}

template<typename T>
void getSigned(T &x)
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();
 
    x = (__ - '0');
    while (__ = getchar(), __ >= '0' && __ <= '9')
        x = (x << 3) + (x << 1) + (__ - '0');

    if (sign) x = -x;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;
const int LIM = 2001;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

bool isOpen(char c)  { return (c == '(') || (c == '[') || (c == '{'); }
bool isClose(char c) { return (c == ')') || (c == ']') || (c == '}'); }
bool match(char l, char r)
{
    return (l == '(' && r == ')')
        || (l == '[' && r == ']')
        || (l == '{' && r == '}');
}

char toMatch(char c)
{
    if (c == '(') return ')';
    if (c == '[') return ']';
    if (c == '{') return '}';
    if (c == ')') return '(';
    if (c == ']') return '[';
    if (c == '}') return '{';
}

int n;
string s;
/// p[c][x]: Minimum position >= x with charactor c (s[p[c][x]] = c)
int p[256][LIM];
int f[LIM][LIM];
int magic(int l = 0, int r = n - 1)
{
    /// Base cases
    if (l > r)  return 0; /// Empty string
    if (l == r) return 1; /// Add one charactor to pair it up

    int &res = f[l][r];
    if (res != +INF) return f[l][r];

    // Branch and bound cases
    if (isClose(s[l]))         return res = magic(l + 1, r - 0) + 1; // Useless leftmost
    if (isOpen(s[r]))          return res = magic(l + 0, r - 1) + 1; // Useless rightmost
    if (match(s[l], s[l + 1])) return res = magic(l + 2, r - 0) + 0; // Leftmost paired
    if (match(s[r - 1], s[r])) return res = magic(l + 0, r - 2) + 0; // Rightmost paired

    /// Main cases
    bool ok = false;
    int need = toMatch(s[r]);
    for (int k = p[need][l]; k < r; k = p[need][k + 1])
    {
        minimize(res, magic(l, k - 1) + 0 + magic(k + 1, r - 1));
    }

    minimize(res, magic(l, r - 1) + 1);
    return res;
}

/// res: number of barrack need to be added
/// diff: difference between number of '(' - ')', diff can be negative
int solve_unique()
{
    int res = 0, diff = 0;
    for (char c : s) /// for each charactor
    {
        diff += (c == '(') ? +1 : -1;
        if (diff < 0) /// Add a '(' here, since there are more ')' then '('
        {
            diff = 0; /// After adding a '(', diff = 0 <=> equal '(' and ')'
            ++res;
        }
    }
    res += diff; /// Add (diff) close barrack at the end

    return res;
}

void precal()
{
    deque<char> S;
    for (char c : s)
    {
        if (S.empty() || match(S.back(), c) == false)
        {
            S.push_back(c);
        }
        else 
        {
            S.pop_back();
        }
    }

    if (S.size() != s.size())
    {
        s = "";
        for (char c : S)
            s += c;
    }
    n = s.size();

    for (char c : "()[]{}")
    {
        p[c][n] = n;
        for (int i = n - 1; i >= 0; --i)
        {
            p[c][i] = (s[i] == c) ? i : p[c][i + 1];
        }
    }
}

void gen()
{
    s = "";
    for (int i = 0; i < LIM - 1; ++i)
    {
        int x = rand() % 6;
        if (x == 0) s += '(';
        if (x == 1) s += ')';
        if (x == 2) s += '[';
        if (x == 3) s += ']';
        if (x == 4) s += '{';
        if (x == 5) s += '}';
    }
}

// int f[LIM][LIM];
// int solve()
// {
//     memset(f, 0, sizeof(f));
//     for (int r = 0; r < n; ++r)
//     {
//         for (int l = r; l >= 0; --l)
//         {
//             f[l][r] = r - l + 1; /// Add one charactor to each one
//             if (match(s[l], s[r])) /// Outside make a good pair of string
//             {
//                 f[l][r] = f[l+1][r-1];
//             }

//             /// Split string into 2 halves
//             /// s[l..r] = s[l..k] + s[k+1..r]
//             /// f[l..r] = min(f[l..k] + f[k+1..r])
//             for (int k = l; k < r; ++k)
//             {
//                 minimize(f[l][r], f[l][k] + f[k+1][r]);
//             }
//         }
//     }

//     return f[0][n - 1];
// }

int main()
{
    cin >> s;
    gen();
    precal();
    n = s.size();

    memset(f, +INF, sizeof(f));
    cout << magic() << endl;
    return 0;
}

/// res: number of barrack need to be added
/// diff: difference between number of '(' - ')', diff can be negative
int solve()
{
    int res = 0, diff = 0;
    for (char c : s) /// for each charactor
    {
        diff += (c == '(') ? +1 : -1;
        if (diff < 0) /// Add a '(' here, since there are more ')' then '('
        {
            diff = 0; /// After adding a '(', diff = 0 <=> equal '(' and ')'
            ++res;
        }
    }
    res += diff; /// Add (diff) close barrack at the end

    return res;
}

int main()
{
    int n;
    cin >> n;

    /// Input points
    vector<point> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;

    /// Sorted by minimum(y) then minimum(x)
    set<point, cmp_y> S;
    set<point, cmp_y>::iterator it;

    double CMD = 1e9; /// Current Minimum Distance
    ll CMSD = 1e18;   /// Current Minimum Squared Distance
    for (int i = 0; i < n; ++i)
    {
        point lower(a[i].x, a[i].y - CMD); /// Lower   will give longer distance
        point upper(a[i].x, a[i].y + CMD); /// Shorter will give longer distance
        for (it = S.lower_bound(lower); it != S.end() && sorty(*it, upper); ++it) 
        {
            int dx = abs(a[i].x - it->x);
            int dy = abs(a[i].y - it->y); 
            if (dx >= CMD && dy >= CMD) it = S.erase(it); /// This point is not optimal, remove it
            if (dx >= CMD || dy >= CMD) continue;         /// Distance >= CMD -> Skip
         
            ll CD = 1LL * dx * dx + 1LL * dy * dy; /// Current Distance
            minimie(CMSD, CD);                     /// Update Distance
        }
        S.insert(a[i]);   /// Add new point
        CMD = sqrt(CMSD); /// Recalculate Minimum Distance
    }

    cout << CMD; /// Answer
    return 0;
}

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <set>

using namespace std;

#define all(x) (x).begin(), (x).end()

char __;
template <typename _T_>
void getSigned(_T_ &_n_) /// For inputing many numbers
{
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));
    bool sign(__ == '-');
    if (sign) __ = getchar();

    _n_ = __ - '0';
    while (__ = getchar(), __ >= '0' && __ <= '9')
        _n_ = 10 * _n_ + __ - '0';
    
    if (sign) _n_ = -_n_;
}

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

struct point /// (x, y) cordinate
{
    int x, y;
    point(int x = 0, int y = 0)
    : x(x), y(y) {}
};

bool sortx (const point &a, const point &b) { return (a.x != b.x) ? (a.x < b.x) : (a.y < b.y); }
bool sorty (const point &a, const point &b) { return (a.y != b.y) ? (a.y < b.y) : (a.x < b.x); }
struct cmp_x { bool operator() (const point &a, const point &b) { return sortx(a, b); } };
struct cmp_y { bool operator() (const point &a, const point &b) { return sorty(a, b); } };
typedef long long ll;
int main()
{
    int n;
    cin >> n;

    /// Input points
    vector<point> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;

    /// Sorted by minimum(y) then minimum(x)
    set<point, cmp_y> S;
    set<point, cmp_y>::iterator it;

    double CMD = 1e9; /// Current Minimum Distance
    ll CMSD = 1e18;   /// Current Minimum Squared Distance
    for (int i = 0; i < n; ++i)
    {
        point lower(a[i].x, a[i].y - CMD); /// Lower   will give longer distance
        point upper(a[i].x, a[i].y + CMD); /// Shorter will give longer distance
        for (it = S.lower_bound(lower); it != S.end() && sorty(*it, upper); ++it) 
        {
            int dx = abs(a[i].x - it->x);
            int dy = abs(a[i].y - it->y); 
            if (dx >= CMD && dy >= CMD) it = S.erase(it); /// This point is not optimal, remove it
            if (dx >= CMD || dy >= CMD) continue;         /// Distance >= CMD -> Skip
         
            ll CD = 1LL * dx * dx + 1LL * dy * dy; /// Current Distance
            minimie(CMSD, CD);                     /// Update Distance
        }
        S.insert(a[i]);   /// Add new point
        CMD = sqrt(CMSD); /// Recalculate Minimum Distance
    }

    cout << CMD; /// Answer
    return 0;
}

• The equation only have solution when $$$c$$$ is a mutiple of $$$g$$$ where $$$g$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$

• When there is a solution $$$(x, y)$$$ satisfy $$$ax + by = c$$$. We also have $$$(x + kv, y - ku)$$$ a solution of the equation (for arbitrary integer $$$k$$$ and quotients $$$u = \frac{a}{g}$$$ , $$$v = \frac{b}{g}$$$)

/// Return gcd(a,b)
/// Find (&x, &y) satisfy ax + by = gcd(a, b)
template<typename T>
T extgcd(T a, T b, T &x, T &y)
{
    if (a == 0) return x = 0, y = 1, b;
    T p = b / a;
    T g = extgcd(b - p * a, a, y, x);
    x -= p * y;
    return g;
}

/// Return gcd(a,b)
/// Find (&x, &y) satisfy ax + by = gcd(a, b)
template<typename T>
tuple<T, T, T> extgcd(T a, T b)
{
    if (a == 0) return make_tuple(b, 0, 1);
    T g, x, y; tie(g, x, y) = extgcd(b % a, a);
    return make_tuple(g, y - b / a * x, x);
}

/// Return true if there exist such (x, y) satisfy ax + by = c
/// Find (&g) = gcd(a, b)
/// Find (&x, &y) satisfy ax + by = c
template<typename T>
bool find_any_solution(T a, T b, T c, T &x, T &y, T &g)
{
    if (a == 0 && b == 0) /// 0x + 0y = c
    {
        if (c != 0) return false;
        x = y = g = 0;
        return true;
    }

    if (a == 0) /// 0x + by = c
    {
        if (c % b != 0) return false;
        x = 0, y = c / b, g = abs(b);
        return true;
    }

    if (b == 0) /// ax + 0y = c
    {
        if (c % a != 0) return false;
        x = c / a, y = 0, g = abs(a);
        return true;
    }

    /// ax + by = c
    g = extgcd(abs(a), abs(b), x, y);
    if (c % g != 0) return false;

    x *= (a < 0 ? -1 : +1) * c / g;
    y *= (b < 0 ? -1 : +1) * c / g;
    return true;
}

/// Find the next/prev (cnt)-th solution of ax + by = c
template<typename T>
void shift_solution(T & x, T & y, T a, T b, T cnt)
{
    x += cnt * b;
    y -= cnt * a;
}

template<typename T = long long>
T find_all_solutions(T a, T b, T c, T min_x, T max_x, T min_y, T max_y) {
    if (min_x > max_x) return 0; /// Invalid range
    if (min_y > max_y) return 0; /// Invalid range

    if (a == 0 && b == 0) /// 0x + 0y = c
    {
        if (c != 0) return 0; /// No solution
        return 1LL * (max_x - min_x + 1) * (max_y - min_y + 1); /// Ways to select (x) and (y) in range
    }

    if (a == 0) /// 0x + by = c <=> y = c / b
    {
        if (c % b != 0) return 0; /// No solution
        if (1LL * min_y * b > c) return 0; /// Out of range: min > y
        if (1LL * max_y * b < c) return 0; /// Out of range: max < y
        return max_x - min_x + 1; /// Ways to select (x) in range    
    }

    if (b == 0) /// ax + 0y = c <=> x = c / a
    {
        if (c % a != 0) return 0; /// No solution
        if (1LL * min_x * a > c) return 0; /// Out of range: min > x
        if (1LL * max_x * a < c) return 0; /// Out of range: max < x
        return max_y - min_y + 1; /// Ways to select (y) in range    
    }

    T x, y, g;
    if (!find_any_solution(a, b, c, x, y, g)) return 0;
    a /= g;     
    b /= g;

    T sign_a = a > 0 ? +1 : -1;
    T sign_b = b > 0 ? +1 : -1;

    shift_solution(x, y, a, b, (min_x - x) / b);
    if (x < min_x) shift_solution(x, y, a, b, sign_b);
    if (x > max_x) return 0;
    T lx1 = x;

    shift_solution(x, y, a, b, (max_x - x) / b);
    if (x > max_x) shift_solution(x, y, a, b, -sign_b);
    T rx1 = x;

    shift_solution(x, y, a, b, -(min_y - y) / a);
    if (y < min_y) shift_solution(x, y, a, b, -sign_a);
    if (y > max_y) return 0;
    T lx2 = x;

    shift_solution(x, y, a, b, -(max_y - y) / a);
    if (y > max_y) shift_solution(x, y, a, b, sign_a);
    T rx2 = x;

    if (lx2 > rx2) swap(lx2, rx2);
    T lx = max(lx1, lx2);
    T rx = min(rx1, rx2);

    if (lx > rx) return 0;
    return (rx - lx) / abs(b) + 1;
}

typedef long long ll;
long long count_nonegative_solution(int a, int b, int c)
{
    return find_all_solutions(ll(a), ll(b), ll(c), 0LL, ll(c / a + 1), 0LL, ll(c / b + 1));
}

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cstdio>
#include <deque>
#include <cmath>
#include <map>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}
#define all(x) (x).begin(), (x).end()
typedef long long ll;

int n, m;
void flip(int &mask, int i, int j) { mask ^= 1 << (i * m + j); }

int lim;
vector<int> F;
vector<int> trace;
void bfs(int s)
{
    trace.assign(lim, 0);
    F.assign(lim, -1);

    trace[s] = -1;
    F[s] = 0;

    deque<int> S;
    S.push_back(s);
    while (S.size())
    {
        int u = S.front();
        S.pop_front();

        for (int i = 1; i < n; ++i) /// Select row
        {
            for (int j = 1; j < m; ++j) /// Select column
            {
                vector<int> selected_x = {i - 1, i - 0, i - 1, i - 0};
                vector<int> selected_y = {j - 1, j - 1, j - 0, j - 0};

                int t = u; /// Make new mask
                for (int k = 0; k < 4; ++k) /// Fully 2x2 modified
                    flip(t, selected_x[k], selected_y[k]);

                for (int k = 0; k < 4; ++k) /// Select 1x1 cell not be modified
                {
                    int v = t;
                    flip(v, selected_x[k], selected_y[k]);

                    if (F[v] == -1) /// If not visited
                    {
                        trace[v] = u;
                        F[v] = F[u] + 1;
                        S.push_back(v);
                    }
                }
            }
        }
    }
}

void analize()
{
    int maximum = *max_element(all(F));
    ll total = accumulate(all(F), 0LL);
    vector<int> C(maximum + 1, 0);
    for (int mask = 0; mask < lim; ++mask)
        ++C[F[mask]];
    
    double closest = 1e9;
    int numerator = 0;
    int denominator = 0;
    int test = sqrt(lim);
    for (int nume = test; nume >= 1; --nume)
    {
        for (int deno = test; deno >= 1; --deno)
        {
            double value = double(nume) / deno * n * m;
            double delta = value - maximum;
            if (delta >= 1e-6 && closest >= delta)
            {
                closest = delta;
                numerator = nume;
                denominator = deno;
            }
        }
    }
    double mean = double(total) / lim;
    double rate = (double(total) / (lim * n * m)) * 100;

    cout << "In total amount of " << lim << " binary table " << n << " x " << m << endl;
    for (int operation = 0; operation <= maximum; ++operation)
    {
        cout << " - " << C[operation] << " cases need";
        cout << " minimum " << operation << " operations" << endl;
    }
    cout << endl;

    cout << "In an overkill solution, in each table " << n << " x " << m << endl;

    cout << "   A) In all cases, you need total " << total << " operations of " << lim << " cases" << endl;
    cout << "    > If your code return exact that value then it is operation minimized" << endl;

    cout << "   B) You need averagely " << mean << " operations" << endl;
    cout << "    > Which is about " << rate << "% of " << n * m << " operations" << endl;

    cout << "   C) And the maximum number of operations needed is " << maximum << endl;
    cout << "    > Which is approximately " << numerator << "nm/" << denominator << " operations" << endl;
    cout << "    > Which mean for each " << numerator << " ones in the table" << endl;
    cout << "      We only need maximumly " << denominator << " operations average" << endl;





    const bool show_case = false;
    const bool show_trace = false;
    if (show_case == false) return ;

    /// If you want to output cases
    vector<vector<int> > M(maximum + 1);
    for (int index = 0; index <= maximum; ++index) M[index].resize(C[index]);
    for (int mask = 0; mask < lim; ++mask)
        M[F[mask]][--C[F[mask]]] = mask; /// this look messy :D

    cout << "\n\n";
    for (int operation = 0; operation <= maximum; ++operation)
    {
        cout << "====X====X====X====X====X====X====X====X====X====X====\n";
        for (int mask : M[operation])
        {
            int cntbit = __builtin_popcount(mask);
            cout << "----x----x----x----x----x----x----x----x----\n";
            cout << "At (" << mask << ") = " << cntbit << " ones | Need " << operation << " operations :\n";

            do 
            {
                int sub = mask;
                for (int i = 1; i <= n; ++i)
                {
                    for (int j = 1; j <= m; ++j)
                    {
                        cout << (sub & 1);
                        sub >>= 1;
                    }
                    cout << '\n';
                }
                cout << '\n';
                if (show_trace == false) break; /// If you only want the mask and not the trace
            } while ((mask = trace[mask]) != -1);
        }
    }
}

int main()
{
    // file();
    cin >> n >> m;
    if (1LL * n * m > 20)
    {
        cout << "Well, I dont have enough data for that :(";
        cout << "- Please provide me smaller constraint";
        return 0;
    }

    lim = 1 << (n * m);
    bfs(0); /// fully zero binary table
    analize();

    return 0;
}

In total amount of 512 binary table 3 x 3
 - 1 cases need minimum 0 operations
 - 16 cases need minimum 1 operations
 - 105 cases need minimum 2 operations
 - 220 cases need minimum 3 operations
 - 150 cases need minimum 4 operations
 - 20 cases need minimum 5 operations

In an overkill solution, in each table 3 x 3
   A) In all cases, you need total 1586 operations of 512 cases
    > If your code return exact that value then it is operation minimized
   B) You need averagely 3.09766 operations
    > Which is about 34.4184% of 9 operations
   C) And the maximum number of operations needed is 5
    > Which is approximately 9nm/16 operations
    > Which mean for each 9 ones in the table
      We only need maximumly 16 operations average

In total amount of 16 binary table 2 x 2
 - 1 cases need minimum 0 operations
 - 4 cases need minimum 1 operations
 - 6 cases need minimum 2 operations
 - 4 cases need minimum 3 operations
 - 1 cases need minimum 4 operations

In an overkill solution, in each table 2 x 2
   A) In all cases, you need total 32 operations of 16 cases
    > If your code return exact that value then it is operation minimized
   B) You need averagely 2 operations
    > Which is about 50% of 4 operations
   C) And the maximum number of operations needed is 4
    > Which is approximately 4nm/3 operations
    > Which mean for each 4 ones in the table
      We only need maximumly 3 operations average


====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (0) = 0 ones | Need 0 operations :
00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (14) = 3 ones | Need 1 operations :
01
11

00
00

----x----x----x----x----x----x----x----x----
At (13) = 3 ones | Need 1 operations :
10
11

00
00

----x----x----x----x----x----x----x----x----
At (11) = 3 ones | Need 1 operations :
11
01

00
00

----x----x----x----x----x----x----x----x----
At (7) = 3 ones | Need 1 operations :
11
10

00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (12) = 2 ones | Need 2 operations :
00
11

11
01

00
00

----x----x----x----x----x----x----x----x----
At (10) = 2 ones | Need 2 operations :
01
01

10
11

00
00

----x----x----x----x----x----x----x----x----
At (9) = 2 ones | Need 2 operations :
10
01

01
11

00
00

----x----x----x----x----x----x----x----x----
At (6) = 2 ones | Need 2 operations :
01
10

11
01

00
00

----x----x----x----x----x----x----x----x----
At (5) = 2 ones | Need 2 operations :
10
10

01
11

00
00

----x----x----x----x----x----x----x----x----
At (3) = 2 ones | Need 2 operations :
11
00

01
11

00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (8) = 1 ones | Need 3 operations :
00
01

10
10

01
11

00
00

----x----x----x----x----x----x----x----x----
At (4) = 1 ones | Need 3 operations :
00
10

11
00

01
11

00
00

----x----x----x----x----x----x----x----x----
At (2) = 1 ones | Need 3 operations :
01
00

10
10

01
11

00
00

----x----x----x----x----x----x----x----x----
At (1) = 1 ones | Need 3 operations :
10
00

01
10

11
01

00
00

====X====X====X====X====X====X====X====X====X====X====
----x----x----x----x----x----x----x----x----
At (15) = 4 ones | Need 4 operations :
11
11

00
01

10
10

01
11

00
00

/// The algorithm can be improved with polynomino-generating

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cstdio>
#include <deque>
#include <cmath>
#include <map>

using namespace std;

void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pi;

template<typename T> void maximize(T &res, T val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, T val) { if (res > val) res = val; }

const int mx[] = {+1, +0, -0, -1};
const int my[] = {+0, +1, -1, -0};

int n, m;
void flip(int &mask, int i, int j) { mask ^= 1 << (i * m + j); }
bool consecutive(int mask) /// All ones are connected
{
    vector<int> used(n, 0);
    used[0] = 1 << 0;
    int cnt = 0;

    deque<pi> S;
    S.push_back(pi(0, 0));
    while (S.size())
    {
        int x = S.front().first;
        int y = S.front().second;
        S.pop_front();

        for (int k = 0; k < 4; ++k)
        {
            int nx = x + mx[k];
            int ny = y + my[k];
            if (nx < 0 || nx >= n) continue;
            if (ny < 0 || ny >= m) continue;
            if (used[nx] >> ny & 1) continue;
            if ((mask >> (nx * m + ny)) & 1) 
            {
                ++cnt;
                used[nx] |= 1 << ny;
                S.push_back(pi(nx, ny));
            }
        }
    }

    int cntbit = __builtin_popcount(mask);
    return cnt == cntbit;
}

int lim;
vector<int> F;
vector<int> trace;
void bfs(int s)
{
    trace.assign(lim, 0);
    F.assign(lim, -1);

    trace[s] = -1;
    F[s] = 0;

    deque<int> S;
    S.push_back(s);
    while (S.size())
    {
        int u = S.front();
        S.pop_front();

        for (int i = 1; i < n; ++i) /// Select row
        {
            for (int j = 1; j < m; ++j) /// Select column
            {
                vector<int> selected_x = {i - 1, i - 0, i - 1, i - 0};
                vector<int> selected_y = {j - 1, j - 1, j - 0, j - 0};

                int t = u; /// Make new mask
                for (int k = 0; k < 4; ++k) /// Fully 2x2 modified
                    flip(t, selected_x[k], selected_y[k]);

                for (int k = 0; k < 4; ++k) /// Select 1x1 cell not be modified
                {
                    int v = t;
                    flip(v, selected_x[k], selected_y[k]);

                    if (F[v] == -1) /// If not visited
                    {
                        trace[v] = u;
                        F[v] = F[u] + 1;
                        S.push_back(v);
                    }
                }
            }
        }
    }
}

void analize()
{
    int maximum = *max_element(all(F));
    ll total = accumulate(all(F), 0LL);
    vector<int> C(maximum + 1, 0);
    for (int mask = 0; mask < lim; ++mask)
        ++C[F[mask]];
    
    cout << "In an overkill solution, in each table " << n << " x " << m << endl;
    /// If you want to output cases
    vector<vector<int> > M(maximum + 1);
    for (int index = 0; index <= maximum; ++index) M[index].resize(C[index]);
    for (int mask = 0; mask < lim; ++mask)
        M[F[mask]][--C[F[mask]]] = mask; /// this look messy :D

    int k = min(n, m);
    vector<int> maxi(k + 1, -1e9);
    vector<int> mini(k + 1, +1e9);
    for (int operation = 0; operation <= maximum; ++operation)
    {
        for (int mask : M[operation])
        {
            int cntbit = __builtin_popcount(mask);
            if (cntbit <= k) /// If (cntbit > k) then we lost the case 1x(cntbit) rectangle
            {
                if (consecutive(mask)) /// all ones are consecutive
                {
                    maximize(maxi[cntbit], operation);
                    minimize(mini[cntbit], operation);
                }
            }
        }
    }

    for (int i = 0; i <= k; ++i) 
    {
        cout << "- With " << i << " ones randomly on the table | ";
        cout << "You need " << "atleast " << mini[i] << " and atmost " << maxi[i] << " operations " << endl;
    }
}

int main()
{
    // file();
    cin >> n >> m;
    if (1LL * n * m > 25)
    {
        cout << "Well, I dont have enough data for that :(";
        cout << "- Please provide me smaller constraint";
        return 0;
    }

    lim = 1 << (n * m);
    bfs(0); /// fully zero binary table
    analize();

    return 0;
}
    }

    lim = 1 << (n * m);
    bfs(0); /// fully zero binary table
    analize();

    return 0;
}

For all $$$n \cdot n$$$ tables with $$$S$$$ ones , if we play optimally in some good cases:

XO  |  +   |  OO  |  ++  |  XX  |  ++  |  OO
OO  |  ++  |  XX  |  +   |  OX  |   +  |  OO

XXXX...  |  ++  |  OOXX..  |  ++  |  OOOX..  |  ++..  |  ..OX  |  ++  |  ..XO  |  +   |  ..OO
OOOO...  |   +  |  OXOO..  |   +  |  OOXO..  |   +..  |  ..XO  |   +  |  ..XX  |  ++  |  ..OO

XXX..  |  ++  |  OOX..  |   +..  | ..XXX  |  ++  |  ..OOX  |   +  |  ..XXX
XXX..  |  +   |  OXX..  |  ++..  | ..XXX  |  +   |  ..OXX  |  ++  |  ..XXX

XXX..XOX  |  +__..  |  _++..  |  ..XOX  |  ++_  |  ..OOX  |  __+  |  ..OOO
XXX..XOX  |  ++_..  |  __+..  |  ..XOX  |  +__  |  ..OXX  |  _++  |  ..OOO

XXX..OX  |  +__..  |  _++..  |  ..OX  |  ++  |  ..XO  |  +   |  ..OO
XXX..OX  |  ++_..  |  __+..  |  ..OX  |  +   |  ..XX  |  ++  |  ..OO

In an overkill solution, in each table 9 x 9
- With 0 ones consecutively random on the table | You need atleast 0 and atmost 0 operations 
- With 1 ones consecutively random on the table | You need atleast 3 and atmost 3 operations 
- With 2 ones consecutively random on the table | You need atleast 2 and atmost 2 operations 
- With 3 ones consecutively random on the table | You need atleast 1 and atmost 3 operations 
- With 4 ones consecutively random on the table | You need atleast 2 and atmost 4 operations 
- With 5 ones consecutively random on the table | You need atleast 3 and atmost 5 operations
- With 6 ones consecutively random on the table | You need atleast 2 and atmost 6 operations
- With 7 ones consecutively random on the table | You need atleast 3 and atmost 7 operations
- With 8 ones consecutively random on the table | You need atleast 4 and atmost 8 operations
- With 9 ones consecutively random on the table | You need atleast 3 and atmost 9 operations

Lets $$$DP[i][j] =$$$ number of ways to share first $$$[i]$$$ children with $$$[j]$$$ used candies

• Base case $$$(DP[0][0] = 1)$$$ and $$$(DP[0][x] = 0\ \forall\ x > 0)$$$ and ($$$DP[p][x] = 0\ \forall\ x < 0$$$)

• At state $$$[i][j]$$$, you can share to the $$$[i]$$$ child $$$(0 \leq x \leq a_i)$$$ candies with $$$(DP[i - 1][j - x])$$$ ways to share

So we have $$$DP[i][j] = \underset{x = 0..a_i}{Sigma}(DP[i - 1][j - x])$$$

And the answer is $$$DP[n][k]$$$

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
int main()
{
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            for (int t = max(0, j - a[i]); t <= j; ++t)
                quickadd(dp[i][j], dp[i - 1][t]);

    cout << dp[n][k];
    return 0;
}

Lets $$$F[i][j] = \underset{x = 0..a_i}{Sigma}(DP[i - 1][j - x])$$$$

From the above base case, we also have $$$(F[0][0] = 1)$$$ and $$$(F[x][0] = 1)$$$ and $$$(F[0][x] = 0)$$$ $$$\ \forall\ x \in \mathbb{N}^*$$$

From the above formula, we also have $$$F[i][j] = F[i][j - 1] + F[i - 1][j] - F[i - 1][j - a_i - 1]$$$

From the above answer, we also have $$$F[n][k]$$$

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
void quicksub(int &res, int val) { if ((res -= val)  <  0 ) res += MOD; }
int main()
{
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = 1;
        for (int j = 1; j <= k; ++j)
        {
            dp[i][j] = dp[i][j - 1];
            quickadd(dp[i][j], dp[i - 1][j]);
            if (j > a[i]) quicksub(dp[i][j], dp[i - 1][j - a[i] - 1]);
        }
    }

    cout << dp[n][k];
    return 0;
}

To compress to 1D array, notice that the current array is build from the previous array, we already having the path $$$F[i][x] = F[i - 1][x]\ \forall\ 0 \leq x \leq k$$$

First we subtract the $$$F[j - a_i - 1]$$$ path $$$\ \forall\ a_i < j \leq k$$$

Then we keep the prefixsum with $$$F[j] += F[j - 1]$$$

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
void quicksub(int &res, int val) { if ((res -= val)  <  0 ) res += MOD; }
int main()
{
    int n, k;
    cin >> n >> k;
    
    vector<int> f(k + 1, 0);
    f[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        for (int j = k; j >= x + 1; --j) quicksub(f[j], f[j - 1 - x]);
        for (int j = 1; j <= k    ; ++j) quickadd(f[j], f[j - 1]);
    }
    cout << f[k];
    return 0;
}