제출 #1161478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161478		The_Samurai	메기 농장 (IOI22_fish)	C++17	100 / 100	649 ms	77284 KiB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second

template<typename T> int sz(const T &x) { return x.size(); }
void maxs(ll &a, ll b) {
    if (a < b) a = b;
}

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    for (int i = 0; i < m; i++) Y[i]++;
    vector all(n, vector<int>{0});
    for (int i = 0; i < m; i++) all[X[i]].emplace_back(Y[i]);
    for (int i = 0; i < m; i++) all[X[i]].emplace_back(Y[i] - 1);
    for (int i = 0; i < n; i++) {
        sort(all[i].begin(), all[i].end());
        if (all[i].back() != n) all[i].emplace_back(n);
    }
    for (int i = n - 1; i >= 0; i--) {
        set<int> st;
        for (int j = max(i - 2, 0); j <= i; j++) {
            for (int x: all[j]) st.insert(x);
        }
        all[i].clear();
        for (int x: st) all[i].emplace_back(x);
    }
    auto get = [&](int x, int y) -> int {
        return upper_bound(all[x].begin(), all[x].end(), y) - all[x].begin() - 1;
    };


    vector<vector<ll>> pre(n);
    for (int i = 0; i < n; i++) pre[i].assign(all[i].size(), 0ll);
    for (int i = 0; i < m; i++) pre[X[i]][get(X[i], Y[i])] += W[i];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < pre[i].size(); j++) pre[i][j] += pre[i][j - 1];
    }


    vector<vector<pair<ll, ll>>> dp(n);
    // dp[i][j] - birinchi i'ta qatorni hisobga osak ohirgi qatorni boyi j bosa max javob
    // ff - o'zinikini qo'shilgan, ss - o'ziniki qo'shilmagan
    for (int i = 0; i < n; i++) dp[i].assign(all[i].size(), make_pair(0ll, 0ll));
    for (int i = 1; i < n; i++) {
        // i > 0
        ll mx = -1e18, mx2 = -1e18;
        for (int j = 0, k = 0; j < dp[i].size() and i > 0; j++) {
            while (k < sz(dp[i - 1]) and all[i - 1][k] <= all[i][j]) {
                maxs(mx, dp[i - 1][k].ss - pre[i - 1][k]);
                maxs(mx2, dp[i - 1][k].ff);
                k++;
            }
            // cout << '\t' << i << ' ' << j << ' ' << k << ' ' << mx << endl;
            // cout << '\t' << pre[i - 1][get(i - 1, all[i][j])] << ' ' << get(i - 1, all[i][j]) << endl;
            maxs(dp[i][j].ss, max(mx + pre[i - 1][get(i - 1, all[i][j])], mx2));
            
        }
        mx = -1e18, mx2 = -1e18;
        for (int j = sz(dp[i]) - 1, k = -2; j >= 0 and i > 0; j--) {
            if (k == -2) k = sz(dp[i - 1]) - 1;
            while (k >= 0 and all[i - 1][k] > all[i][j]) {
                maxs(mx, dp[i - 1][k].ff + pre[i][get(i, all[i - 1][k])]);
                maxs(mx2, dp[i - 1][k].ff);
                k--;
            }
            maxs(dp[i][j].ff, mx - pre[i][j]);
            maxs(dp[i][j].ss, mx2);
        }

        // i > 1
        mx = -1e18;
        for (int j = 0, k = 0; j < dp[i].size() and i > 1; j++) {
            while (k < sz(dp[i - 2]) and all[i - 2][k] <= all[i][j]) {
                maxs(mx, dp[i - 2][k].ff);
                k++;
            }
            maxs(dp[i][j].ss, mx + pre[i - 1][get(i - 1, all[i][j])]);
        }
        mx = -1e18;
        for (int j = sz(dp[i]) - 1, k = -2; j >= 0 and i > 1; j--) {
            if (k == -2) k = sz(dp[i - 2]) - 1;
            while (k >= 0 and all[i - 2][k] > all[i][j]) {
                maxs(mx, dp[i - 2][k].ff + pre[i - 1][get(i - 1, all[i - 2][k])]);
                k--;
            }
            maxs(dp[i][j].ss, mx);
        }

        // i > 2
        if (i > 2) {
            mx = -1e18;
            for (int k = 0; k < sz(dp[i - 3]); k++) {
                maxs(mx, dp[i - 3][k].ff + pre[i - 2][get(i - 2, all[i - 3][k])]);
            }
            for (int j = 0; j < sz(dp[i]); j++) {
                maxs(dp[i][j].ss, mx + pre[i - 1][get(i - 1, all[i][j])]);
            }
        }

        for (int j = 0; j < sz(dp[i]); j++) maxs(dp[i][j].ff, dp[i][j].ss);
        // cout << i << endl;
        // for (int j = 0; j < sz(dp[i]); j++) {
        //     cout << all[i][j] << ' ' << dp[i][j].ff << ' ' << dp[i][j].ss << endl;
        // }
    }


    // for (int i = 1; i < n; i++) {
    //     ll mx = -1e18, mx2 = -1e18, mx3 = -1e18;
    //     for (int j = 0; j <= n; j++) {
    //         maxs(mx, dp[i - 1][j].ss - pre[i - 1][j]);
    //         maxs(mx2, dp[i - 1][j].ff);
    //         maxs(dp[i][j].ss, max(mx + pre[i - 1][j], mx2));

    //         if (i > 1) {
    //             maxs(mx3, dp[i - 2][j].ff);
    //             maxs(dp[i][j].ss, mx3 + pre[i - 1][j]);
    //         }





            

    //     }

    //     mx = -1e18;
    //     for (int j = 0; j <= n and i > 2; j++) {
    //         maxs(mx, dp[i - 3][j].ff + pre[i - 2][j]);
    //     }
    //     for (int j = 0; j <= n; j++) maxs(dp[i][j].ss, mx + pre[i - 1][j]);

    //     mx = -1e18, mx2 = -1e18, mx3 = -1e18;
    //     for (int j = n; j >= 0; j--) {
    //         maxs(dp[i][j].ff, mx - pre[i][j]);
    //         maxs(dp[i][j].ss, mx2);
    //         maxs(mx, dp[i - 1][j].ff + pre[i][j]);
    //         maxs(mx2, dp[i - 1][j].ff);

    //         if (i > 1) {
    //             maxs(mx3, dp[i - 2][j].ff + pre[i - 1][j]);
    //             maxs(dp[i][j].ss, mx3);
    //         }
            
    //         maxs(dp[i][j].ff, dp[i][j].ss);
    //         // maxlash esdan chiqmasin
    //     }
    // }


    ll ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < sz(dp[i]); j++) maxs(ans, dp[i][j].ff);
    }
    return ans;
}

// g++ -o fish -O2 fish.cpp grader.cpp -std=c++20 && .\fish < input.txt > output.txt

• 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