Submission #1129117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129117		vladilius	Catfish Farm (IOI22_fish)	C++20	100 / 100	287 ms	52388 KiB

fish

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
const ll infm = -1e18;

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    int n = N, m = M;
    for (int i = 0; i < m; i++){
        X[i]++; Y[i]++;
    }

    vector<int> dy[n + 1];
    vector<pii> d[n + 1];
    for (int i = 0; i < m; i++){
        d[X[i]].pb({Y[i], i});
    }
    vector<ll> pr[n + 1];
    for (int i = 1; i <= n; i++){
        sort(d[i].begin(), d[i].end());
        pr[i].resize(d[i].size() + 1);
        for (int j = 1; j <= d[i].size(); j++){
            pr[i][j] = pr[i][j - 1] + W[d[i][j - 1].ss];
            dy[i].pb(d[i][j - 1].ff);
        }
        dy[i].pb(n + 1);
    }
    
    vector<int> :: iterator it;
    auto F = [&](int i, int j){
        it = upper_bound(dy[i].begin(), dy[i].end(), j);
        int t = (int) (it - dy[i].begin());
        return pr[i][t];
    };
    
    vector<ll> dp[n + 1][2];
    vector<int> ii[n + 1];
    dp[1][0].pb(0); dp[1][1].pb(0); ii[1].pb(0);
    dp[1][0].pb(0); dp[1][1].pb(0); ii[1].pb(n);
    
    for (int i = 2; i <= n; i++){
        int a = (int) dp[i - 1][0].size();
        vector<ll> pr1(a + 1); pr1[0] = infm;
        for (int j = 1; j <= a; j++){
            pr1[j] = max(pr1[j - 1], dp[i - 1][0][j - 1] - F(i - 1, ii[i - 1][j - 1]));
        }
        vector<ll> pr4(a + 2);
        for (int j = a; j > 0; j--){
            pr4[j] = max(pr4[j + 1], max(dp[i - 1][0][j - 1], dp[i - 1][1][j - 1]) + F(i, ii[i - 1][j - 1]));
        }
        
        a = (int) dp[i - 2][0].size();
        vector<ll> pr2(a + 1), pr3(a + 2);
        if (i > 2){
            for (int j = 1; j <= a; j++){
                pr2[j] = max(pr2[j - 1], max(dp[i - 2][0][j - 1], dp[i - 2][1][j - 1]));
            }
            for (int j = a; j > 0; j--){
                pr3[j] = max(pr3[j + 1], max(dp[i - 2][0][j - 1], dp[i - 2][1][j - 1]) + F(i - 1, ii[i - 2][j - 1]));
            }
        }
        
        for (int x: dy[i]){
            int j = x - 1;
            ll a, b;
            it = upper_bound(ii[i - 1].begin(), ii[i - 1].end(), j);
            int t = (int) (it - ii[i - 1].begin());
            
            a = pr1[t] + F(i - 1, j);
            b = max(0LL, pr4[t + 1] - F(i, j));
            if (i > 2){
                it = upper_bound(ii[i - 2].begin(), ii[i - 2].end(), j);
                int t = (int) (it - ii[i - 2].begin());
                a = max({a, pr2[t] + F(i - 1, j), pr3[t + 1]});
            }
            
            dp[i][0].pb(a);
            dp[i][1].pb(b);
            ii[i].pb(j);
        }
        
        if (ii[i][0]){
            dp[i][0].insert(dp[i][0].begin(), 0);
            dp[i][1].insert(dp[i][1].begin(), 0);
            ii[i].insert(ii[i].begin(), 0);
        }
    }
    
    ll out = 0;
    for (int i = 1; i <= n; i++){
        for (ll j: dp[i][0]){
            out = max(out, j);
        }
        for (ll j: dp[i][1]){
            out = max(out, j);
        }
    }
    return out;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16