Submission #676852

#	Time	Username	Problem	Language	Result	Execution time	Memory
676852		Ninja_Kunai	Catfish Farm (IOI22_fish)	C++17	18 / 100	89 ms	14380 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;
	}

	long long dp[N][2][2];
	int cost[N];
	long long solve(int n, int m, vector <array <int, 3>> fishes) {
		REP(i, m) cost[fishes[i][0]] = fishes[i][2];
		memset(dp, -1, sizeof dp);
		dp[0][0][0] = 0;
		dp[0][1][1] = 0;
		REP(i, n - 1) {
			REP(j, 2) REP(k, 2) if (dp[i][j][k] != -1) {
				if (j == 0) {
					if (k == 0) {
						maximize(dp[i + 1][0][0], dp[i][j][k]);
						maximize(dp[i + 1][1][1], dp[i][j][k] + cost[i]);
					}
					else {
						maximize(dp[i + 1][0][0], dp[i][j][k]);
						maximize(dp[i + 1][1][1], dp[i][j][k]);
					}
				}
				else {
					maximize(dp[i + 1][1][1], dp[i][j][k]);
					maximize(dp[i + 1][0][1], dp[i][j][k] + cost[i + 1]);
				}
			}
		}

		long long ans = 0;
		REP(j, 2) REP(k, 2) maximize(ans, dp[n - 1][j][k]);
		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);
	return 0;
}

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