Submission #1015956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015956		Valaki2	Catfish Farm (IOI22_fish)	C++17	3 / 100	133 ms	51748 KiB

fish

#include "fish.h"
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

#define inc inc1337
#define dec dec1337

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 1e5;

int n, m;
vector<pii > fish[1 + maxn];
vector<int> reach[1 + maxn];
int len[1 + maxn];
vector<int> inc[1 + maxn];
vector<int> dec[1 + maxn];
int sm[1 + maxn];
int bi[1 + maxn];
int other;

int solve() {
    for(int i = 0; i <= n; i++) {
        if(fish[i].size() == 1) {
            fish[i].pb(mp(n + 1, 0));
        }
        len[i] = fish[i].size() - 1;
        dec[i].resize(1 + len[i]);
        inc[i].resize(1 + len[i]);
        for(const pii &p : fish[i]) {
            if(p.fi != 0) {
                reach[i].pb(p.fi - 1);
            }
        }
        reach[i].pb(n + 1);
    }
    // for(int i = 0; i <= n; i++) {
    //     cout << i << ":\n";
    //     for(pii p : fish[i]) {
    //         cout << p.fi << " " << p.se << "\n";
    //     }
    //     for(int x : reach[i]) {
    //         cout << x << " ";
    //     }
    //     cout << "\n";
    //     cout << len[i] << "\n";
    //     for(int x : inc[i]) {
    //         cout << x << " ";
    //     }
    //     cout << "\n";
    //     for(int x : dec[i]) {
    //         cout << x << " ";
    //     }
    //     cout << "\n";
    //     cout << sm[i] << " " << bi[i] << "\n";
    //     // other
    // }
    for(int i = 1; i <= n; i++) {
        // inc
        {
            vector<int> v(1 + len[i - 1]);
            v[0] = inc[i - 1][0];
            int pref = 0;
            for(int j = 1; j <= len[i - 1]; j++) {
                pref += fish[i - 1][j].se;
                v[j] = inc[i - 1][j] - pref;
                v[j] = max(v[j], v[j - 1]);
            }
            int k = 0;
            pref = 0;
            for(int j = 1; j <= len[i]; j++) {
                while(k < len[i - 1] && fish[i - 1][k + 1].fi <= reach[i][j]) {
                    k++;
                    pref += fish[i - 1][k].se;
                }
                inc[i][j] = pref + v[k];
                // itt az is benne van, ha az elozo
                // reach-je a mostani fele log es esetleg
                // valamit include-ol, de az nem szamit, 
                // mert nem adjuk hozza, es kulon esetben
                // viszont lekezeljuk
            }
        }
        // dec
        {
            vector<int> v(1 + len[i - 1]);
            int pref = 0;
            for(int j = 1; j <= len[i]; j++) {
                pref += fish[i][j].se;
            }
            int k = len[i];
            for(int j = len[i - 1]; j >= 1; j--) {
                while(fish[i][k].fi > reach[i - 1][j]) {
                    pref -= fish[i][k].se;
                    k--;
                }
                v[j] = dec[i - 1][j] + pref;
                if(j < len[i - 1]) {
                    v[j] = max(v[j], v[j + 1]);
                }
            }
            k = len[i - 1];
            pref = 0;
            for(int j = len[i - 1]; j >= 1; j--) {
                pref += fish[i][j].se;
            }
            for(int j = len[i]; j >= 0; j--) {
                while(k > 0 && fish[i][j].fi <= reach[i - 1][k - 1]) {
                    k--;
                }
                dec[i][j] = v[k] - pref;
                // itt is van hasonlo eset ami
                // mashol kezelve van
                pref -= fish[i][j].se;
            }
        }
        // sm
        if(i >= 2) {
            vector<int> v(1 + len[i - 2]);
            int pref = 0;
            for(int j = 1; j <= len[i - 1]; j++) {
                pref += fish[i - 1][j].se;
            }
            int k = len[i - 1];
            for(int j = len[i - 2]; j >= 1; j--) {
                while(fish[i - 1][k].fi > reach[i - 2][j]) {
                    pref -= fish[i - 1][k].se;
                    k--;
                }
                v[j] = dec[i - 2][j] + pref;
                if(j < len[i - 2]) {
                    v[j] = max(v[j], v[j + 1]);
                }
            }
            for(int j = 1; j <= len[i]; j++) {
                inc[i][j] = max(inc[i][j], v[1]);
            }
            int maxi_prev = 0;
            for(int j = 1; j <= len[i - 2]; j++) {
                maxi_prev = max(maxi_prev, dec[i - 2][j]);
            }
            k = 0;
            pref = 0;
            for(int j = 1; j <= len[i]; j++) {
                while(k < len[i - 1] && fish[i - 1][k + 1].fi <= reach[i][j]) {
                    k++;
                    pref += fish[i - 1][k].se;
                }
                inc[i][j] = max(inc[i][j], maxi_prev + pref);
            }
        }
        // bi
        bi[i] = inc[i][len[i]];
        // other
        dec[i][len[i]] = max(dec[i][len[i]], bi[i]);
    }
    int ans = 0;
    for(int x : inc[n]) {
        ans = max(ans, x);
    }
    for(int y : dec[n]) {
        ans = max(ans, y);
    }
    ans = max(ans, sm[n]);
    ans = max(ans, bi[n]);
    return ans;
}

int max_weights(signed N, signed M, vector<signed> X, vector<signed> Y, vector<signed> W) {
    n = N, m = M;
    for(int i = 0; i <= n; i++) {
        fish[i].pb(mp(0, 0));
    }
    for(int i = 0; i < m; i++) {
        fish[X[i] + 1].pb(mp(Y[i] + 1, W[i]));
    }
    for(int i = 1; i <= n; i++) {
        sort(fish[i].begin(), fish[i].end());
    }
    return solve();
}

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