Submission #1269909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269909		antonn	Catfish Farm (IOI22_fish)	C++20	9 / 100	1096 ms	23620 KiB

fish

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    vector<vector<pi>> occ(n + 1);
    for (int i = 0; i < m; ++i) {
        occ[x[i]].push_back({y[i], w[i]});
    }
    for (int i = 0; i < n; ++i) occ[i].push_back({n, 0});
    for (int i = 0; i < n; ++i) sort(occ[i].begin(), occ[i].end());
    
    auto between = [&](int x, int l, int r) {
        ll ans = 0;
        for (auto [a, b] : occ[x]) if (l <= a && a <= r) ans += b;
        return ans;
    };
    
    vector<vector<ll>> dp0(n + 1), dp1(n);
    for (int i = 0; i < n; ++i) dp0[i].assign(occ[i].size(), 0);
    for (int i = 0; i < n; ++i) dp1[i].assign(occ[i].size(), 0);
    for (int i = 1; i < n; ++i) {
        // p[i] < p[i - 1]
        for (int j = 0; j < occ[i].size(); ++j) {
            for (int k = 0; k < occ[i - 1].size(); ++k) {
                if (occ[i - 1][k].F - 1 >= occ[i][j].F) {
                    ckmax(dp0[i][j], dp0[i - 1][k] + between(i, occ[i][j].F, occ[i - 1][k].F - 1));
                    ckmax(dp0[i][j], dp1[i - 1][k] + between(i, occ[i][j].F, occ[i - 1][k].F - 1));
                }
            }
        }
        // p[i] > p[i - 1]
        for (int j = 0; j < occ[i].size(); ++j) {
            for (int k = 0; k < occ[i - 1].size(); ++k) {
                if (occ[i - 1][k].F - 1 <= occ[i][j].F - 1) {
                    ckmax(dp1[i][j], dp1[i - 1][k] + between(i - 1, occ[i - 1][k].F, occ[i][j].F - 1));
                }
            }
            if (i >= 2) {
                for (int k = 0; k < occ[i - 2].size(); ++k) {
                    ckmax(dp1[i][j], dp0[i - 2][k] + between(i - 1, 0, max(occ[i][j].F - 1, occ[i - 1][k].F - 1)));
                    ckmax(dp1[i][j], dp1[i - 2][k] + between(i - 1, 0, max(occ[i][j].F - 1, occ[i - 1][k].F - 1)));
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp0[n - 1][i]);
    for (int i = 0; i < occ[n - 1].size(); ++i) ckmax(ans, dp1[n - 1][i]);
    return ans;
}

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