Submission #677200

#	Time	Username	Problem	Language	Result	Execution time	Memory
677200		Ninja_Kunai	Catfish Farm (IOI22_fish)	C++17	67 / 100	1073 ms	81088 KiB

fish

/**
*    Author :  Nguyen Tuan Vu
*    Created : 01.01.2023
**/

#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;
namespace sub1 {
	bool check(int m, vector <array <int, 3>> fishes) {
		REP(i, m) {
			if (fishes[i][0] & 1) return false;
		}

		return true;
	}

	long long solve(int m, vector <array <int, 3>> fishes) {
		//assert(1 == 0);
		long long ans = 0;
		REP(i, m) ans += fishes[i][2];
		return ans;
	}
}

namespace sub2 {
	bool check(int m, vector <array <int, 3>> fishes) {
		REP(i, m) if (fishes[i][0] > 1) return false;
		return true;
	}

	long long solve(int n, int m, vector <array <int, 3>> fishes) {
		//assert(1 == 0);
		if (n == 2) {
			long long ans[2] = {0};
			REP(i, m) ans[fishes[i][0]] += fishes[i][2];
			return max(ans[0], ans[1]);
		}

		vector <long long> sum[2];
		REP(i, 2) sum[i].resize(n + 7, 0);
		REP(i, m) sum[fishes[i][0]][fishes[i][1]] += fishes[i][2];
		FOR(i, 1, n - 1) REP(j, 2) sum[j][i] = sum[j][i - 1] + sum[j][i];
		long long ans = sum[1][n - 1];
		REP(i, n) maximize(ans, sum[0][i] + sum[1][n - 1] - sum[1][i]);
		return ans;
	}
}

namespace sub3 {
    bool check(int m, vector <array <int, 3>> fishes) {
        REP(i, m) if (fishes[i][1] != 0) return false;
        return true;
    }

    int cost[N];
    long long dp[N];

    long long solve(int n, int m, vector <array <int, 3>> fishes) {
        REP(i, m) cost[fishes[i][0] + 1] = fishes[i][2];
        FOR(i, 1, n) {
            maximize(dp[i], dp[i - 1]);
            if (i >= 2) maximize(dp[i], dp[i - 2] + cost[i - 1]);
            if (i > 3) maximize(dp[i], dp[i - 3] + cost[i - 1] + cost[i - 2]);
        }

        long long ans = 0;
        FOR(i, 1, n) {
            dp[i] = dp[i] + cost[i + 1];
            maximize(ans, dp[i]);
        }

        return ans;
    }
}

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> X, vector <int> Y, vector <int> W) {
	vector <array <int, 3>> fishes;
	fishes.resize(m + 7);
	REP(i, m) fishes[i] = {X[i], Y[i], W[i]};

	if (sub1::check(m, fishes)) return sub1::solve(m, fishes);
	else if (sub2::check(m, fishes)) return sub2::solve(n, m, fishes);
	else if (sub3::check(m, fishes)) return sub3::solve(n, m, fishes);
	else return sub6::solve(n, m, fishes);
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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