oj.uz

Submission #630563

# Submission time Handle Problem Language Result Execution time Memory
630563 2022-08-16T14:33:37 Z JustInCase Catfish Farm (IOI22_fish) C++17
0 / 100
 122 ms 53240 KB 
#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;
	mutable int64_t prefSum;

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

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

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::set<Catfish>> catfishByColumn(n);

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

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

	std::vector<std::set<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].insert(DpState(x.row + 1));
			}
		}
		if(i < n) {
			for(auto &x : catfishByColumn[i + 1]) {
				dp[i].insert(DpState(x.row + 1));
			}
		}

		dp[i].insert(DpState(0));
	}

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

		auto it = catfishByColumn[column].lower_bound(Catfish(row + 1, -1));
		if(it == catfishByColumn[column].begin()) {
			return 0;
		}

		it--;
		return it->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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 53240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 32084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 32084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 53240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -