Submission #630805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
630805	2022-08-17T06:45:26 Z	JustInCase	Catfish Farm (IOI22_fish)	C++17	58 / 100	1000 ms	60036 KB

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;
	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 - 1) {
			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 p = catfishByColumn[column].lower_bound(Catfish(row, 0));
		if(p == catfishByColumn[column].begin()) {
			return 0;
		}

		p--;
		return p->prefSum;
		*/

		for(auto it = catfishByColumn[column].rbegin(); it != catfishByColumn[column].rend(); it++) {
			if(it->row < row) {
				return it->prefSum;	
			}
		}

		return 0;
	};

	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);
			}
		}
	}

	/**
	for(int32_t i = 0; i <= n; i++) {
		std::cout << i << ": ";
		for(auto &x : dp[i]) {
			std::cout << "{ " << x.row << ", " << x.incrVal << ", " << x.decrVal << " }, ";
		}
		std::cout << '\n';
	}
	*/

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

Subtask #1
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1056 ms	26616 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Execution timed out	1032 ms	43896 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	15964 KB	Output is correct
2	Correct	16 ms	15916 KB	Output is correct
3	Correct	62 ms	25948 KB	Output is correct
4	Correct	49 ms	23784 KB	Output is correct
5	Correct	122 ms	37024 KB	Output is correct
6	Correct	107 ms	37144 KB	Output is correct
7	Correct	123 ms	37244 KB	Output is correct
8	Correct	114 ms	37320 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	5 ms	852 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct

Subtask #5
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	5 ms	852 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	7 ms	724 KB	Output is correct
17	Correct	347 ms	10628 KB	Output is correct
18	Correct	450 ms	10448 KB	Output is correct
19	Correct	218 ms	10456 KB	Output is correct
20	Correct	232 ms	10552 KB	Output is correct
21	Correct	231 ms	10440 KB	Output is correct
22	Correct	999 ms	20448 KB	Output is correct
23	Correct	16 ms	2260 KB	Output is correct
24	Correct	111 ms	7056 KB	Output is correct
25	Correct	2 ms	468 KB	Output is correct
26	Correct	20 ms	2132 KB	Output is correct

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	5 ms	852 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	7 ms	724 KB	Output is correct
17	Correct	347 ms	10628 KB	Output is correct
18	Correct	450 ms	10448 KB	Output is correct
19	Correct	218 ms	10456 KB	Output is correct
20	Correct	232 ms	10552 KB	Output is correct
21	Correct	231 ms	10440 KB	Output is correct
22	Correct	999 ms	20448 KB	Output is correct
23	Correct	16 ms	2260 KB	Output is correct
24	Correct	111 ms	7056 KB	Output is correct
25	Correct	2 ms	468 KB	Output is correct
26	Correct	20 ms	2132 KB	Output is correct
27	Correct	4 ms	1332 KB	Output is correct
28	Execution timed out	1029 ms	48128 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	15964 KB	Output is correct
2	Correct	16 ms	15916 KB	Output is correct
3	Correct	62 ms	25948 KB	Output is correct
4	Correct	49 ms	23784 KB	Output is correct
5	Correct	122 ms	37024 KB	Output is correct
6	Correct	107 ms	37144 KB	Output is correct
7	Correct	123 ms	37244 KB	Output is correct
8	Correct	114 ms	37320 KB	Output is correct
9	Correct	101 ms	37196 KB	Output is correct
10	Correct	102 ms	29456 KB	Output is correct
11	Correct	257 ms	58484 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	18 ms	15960 KB	Output is correct
19	Correct	16 ms	15956 KB	Output is correct
20	Correct	17 ms	15864 KB	Output is correct
21	Correct	14 ms	15956 KB	Output is correct
22	Correct	131 ms	37084 KB	Output is correct
23	Correct	241 ms	58404 KB	Output is correct
24	Correct	249 ms	60036 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1056 ms	26616 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #630805

Compilation message