Submission #630817

#	Time	Username	Problem	Language	Result	Execution time	Memory
630817		JustInCase	Catfish Farm (IOI22_fish)	C++17	100 / 100	290 ms	43412 KiB

fish

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>

#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));

#define maxWeights max_weights

const int32_t MAX_N = 1e5;

struct Catfish {
	int32_t row;
	int32_t id;
	mutable int64_t prefSum;

	Catfish(int32_t _row, int32_t _id, int32_t w): row(_row), id(_id), prefSum((int64_t) w) {}

	bool operator< (const Catfish &other) const {
		if(row != other.row) {
			return row <= other.row;
		}
		else {
			return id <= other.id;
		}
	}
};

struct DpState {
	int32_t row;
	mutable int64_t incrVal, decrVal;

	DpState(int32_t _row): row(_row), incrVal(0), decrVal(0) {}

	bool operator< (const DpState &other) const {
		return row <= other.row;
	}
};

int64_t maxWeights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
                      std::vector<int32_t> w) {
	std::vector<std::vector<Catfish>> catfishByColumn(n);

	for(int32_t i = 0; i < m; i++) {
		catfishByColumn[x[i]].push_back(Catfish(y[i], i, w[i]));
	}

	for(int32_t i = 0; i < n; i++) {
		std::sort(catfishByColumn[i].begin(), catfishByColumn[i].end());

		int64_t total = 0;
		for(auto &x : catfishByColumn[i]) {
			total += (int64_t) x.prefSum;
			x.prefSum = total;
		}
	}

	std::vector<std::vector<DpState>> dp(n + 1);
	for(int32_t i = 0; i <= n; i++) {
		if(i > 0 && i != n) {
			for(auto &x : catfishByColumn[i - 1]) {
				dp[i].push_back(DpState(x.row + 1));
			}
		}
		if(i < n - 1) {
			for(auto &x : catfishByColumn[i + 1]) {
				dp[i].push_back(DpState(x.row + 1));
			}
		}

		dp[i].push_back(DpState(0));

		std::sort(dp[i].begin(), dp[i].end());
	}

	auto getWPrefSum = [&](int32_t column, int32_t row) -> int64_t {
		if(column >= n) {
			return 0;
		}

		auto p = std::lower_bound(catfishByColumn[column].begin(), catfishByColumn[column].end(), Catfish(row, -1, 0));
		if(p == catfishByColumn[column].begin()) {
			return 0;
		}

		p--;
		return p->prefSum;
	};

	for(int32_t i = 1; i <= n; i++) {
		{ // compute incrVal
			auto prevIt = dp[i - 1].begin();
			int64_t pref = 0;
			for(auto it = dp[i].begin(); it != dp[i].end(); it++) {
				while(prevIt != dp[i - 1].end() && prevIt->row <= it->row) {
					remax(pref, prevIt->incrVal - getWPrefSum(i - 1, prevIt->row));
					prevIt++;
				}

				it->incrVal = std::max(pref + getWPrefSum(i - 1, it->row), dp[i - 1].begin()->decrVal);
			}
		}

		{ // compute decrVal
			auto prevIt = dp[i - 1].rbegin();
			int64_t suff = 0;
			for(auto it = dp[i].rbegin(); it != dp[i].rend(); it++) {
				while(prevIt != dp[i - 1].rend() && prevIt->row >= it->row) {
					remax(suff, std::max(prevIt->incrVal, prevIt->decrVal) + getWPrefSum(i, prevIt->row));
					prevIt++;
				}

				it->decrVal = suff - getWPrefSum(i, it->row);
			}
		}
	}

	return std::max(dp.back().begin()->incrVal, dp.back().begin()->decrVal);
}

• 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