Submission #853634

#	Time	Username	Problem	Language	Result	Execution time	Memory
853634		errw	Catfish Farm (IOI22_fish)	C++17	58 / 100	1044 ms	81232 KiB

fish

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}

const int N = 1e5 + 5;

const long long INF = 1e18 + 7;
namespace sub6 {
    vector <int> coor[N];
    vector <long long> f[N], g[N];
    vector <pair <int, long long>> sum[N];

    const int M = 3e3 + 5;
    long long sum2[M][M];

    long long get_sum(int n, int i, int x) {
    	if (n <= 3e3) return sum2[i][x];
    	if (sum[i].size() == 0 || x < sum[i][0].first) return 0;
    	if (sum[i].back().first <= x) return sum[i].back().second;

        int pos = upper_bound(ALL(sum[i]), make_pair(x, INF)) - sum[i].begin() - 1;
        if (pos == -1) return 0;
        return sum[i][pos].second;
    }

    long long solve(int n, int m, vector <array <int, 3>> fishes) {
        REP(i, m) {
            if (fishes[i][0] + 1 > 1) coor[fishes[i][0]].push_back(fishes[i][1] + 1);
            if (fishes[i][0] + 1 < n) coor[fishes[i][0] + 2].push_back(fishes[i][1] + 1);

            if (n <= 3e3) sum2[fishes[i][0] + 1][fishes[i][1] + 1] = fishes[i][2];
            sum[fishes[i][0] + 1].push_back({fishes[i][1] + 1, fishes[i][2]});
        }

        if (n <= 3e3) {
        	FOR(i, 1, n) FOR(j, 1, n) sum2[i][j] += sum2[i][j - 1];
        }

        FOR(i, 1, n) {
            coor[i].push_back(0);
            sort (ALL(coor[i]));
            coor[i].erase(unique(ALL(coor[i])), coor[i].end());
            f[i].resize(coor[i].size() + 5, -1);
            g[i].resize(coor[i].size() + 5, -1);

            sort (ALL(sum[i]));
            FOR(j, 1, (int) sum[i].size() - 1) sum[i][j].second += sum[i][j - 1].second;
        }

        // f : roi
        // g : chua
        REP(i, coor[1].size()) g[1][i] = 0;

        FOR(i, 2, n) {
            REP(k, coor[i - 1].size()) if (f[i - 1][k] != -1 || g[i - 1][k] != -1) {
                REP(j, coor[i].size()) if (coor[i - 1][k] <= coor[i][j]) {
                    // f
                    if (f[i - 1][k] != -1) maximize(g[i][j], f[i - 1][k]);

                    // g
                    if (g[i - 1][k] != -1) {
                        long long R = get_sum(n, i - 1, coor[i][j]);
                        long long L = get_sum(n, i - 1, coor[i - 1][k]);

                        maximize(g[i][j], g[i - 1][k] + R - L);
                    }
                }
                else {
                    // update f
                    maximize(f[i][j], max(f[i - 1][k], g[i - 1][k]) + get_sum(n, i, coor[i - 1][k]) - get_sum(n, i, coor[i][j]));

                    // update g
                    maximize(g[i][j], max(f[i - 1][k], g[i - 1][k]));
                }
            }

            if (i > 2) {
                REP(k, coor[i - 2].size()) if (f[i - 2][k] != -1 || g[i - 2][k] != -1) {
                    REP(j, coor[i].size()) {
                        maximize(g[i][j], max(f[i - 2][k], g[i - 2][k]) + get_sum(n, i - 1, max(coor[i - 2][k], coor[i][j])));
                    }
                }
            }

            if (i > 3) {
                REP(k, coor[i - 3].size()) if (f[i - 3][k] != -1 || g[i - 3][k] != -1) {
                    REP(j, coor[i].size()) {
                        maximize(g[i][j], max(f[i - 3][k], g[i - 3][k]) + get_sum(n, i - 1, coor[i][j]) + get_sum(n, i - 2, coor[i - 3][k]));
                    }
                }
            }
        }

        long long ans = 0;
        FOR(i, 1, n) REP(j, coor[i].size()) maximize(ans, max(f[i][j], g[i][j]) + get_sum(n, i + 1, coor[i][j]));

        return ans;
    }
};

long long max_weights(int n, int m, vector <int> xX, vector <int> Y, vector <int> W) {
	vector <array <int, 3>> fishes;
	fishes.resize(m + 7);
	REP(i, m) fishes[i] = {xX[i], Y[i], W[i]};

	return sub6::solve(n, m, fishes);
	return 0;
}

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