oj.uz

Submission #630647

# Submission time Handle Problem Language Result Execution time Memory
630647 2022-08-16T19:38:34 Z JustInCase Catfish Farm (IOI22_fish) C++17
6 / 100
 675 ms 86440 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 - 1) {
			for(auto &x : catfishByColumn[i + 1]) {
				dp[i].insert(DpState(x.row + 1));
			}
		}
 
		dp[i].insert(DpState(0));
        dp[i].insert(DpState(n));
	}
 
	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(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 Correct 133 ms 32464 KB Output is correct
2 Correct 143 ms 37568 KB Output is correct
3 Correct 24 ms 22100 KB Output is correct
4 Correct 24 ms 22100 KB Output is correct
5 Incorrect 675 ms 86440 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '149813188221811'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 324 ms 49692 KB Output is correct
3 Correct 376 ms 58904 KB Output is correct
4 Correct 130 ms 32488 KB Output is correct
5 Correct 153 ms 37716 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 27 ms 22196 KB Output is correct
11 Correct 24 ms 22108 KB Output is correct
12 Correct 162 ms 37560 KB Output is correct
13 Correct 230 ms 43748 KB Output is correct
14 Correct 144 ms 35088 KB Output is correct
15 Correct 160 ms 38860 KB Output is correct
16 Correct 133 ms 35148 KB Output is correct
17 Correct 164 ms 38864 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22112 KB Output is correct
2 Correct 30 ms 22156 KB Output is correct
3 Incorrect 70 ms 31748 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '999995196'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22112 KB Output is correct
2 Correct 30 ms 22156 KB Output is correct
3 Incorrect 70 ms 31748 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '999995196'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 32464 KB Output is correct
2 Correct 143 ms 37568 KB Output is correct
3 Correct 24 ms 22100 KB Output is correct
4 Correct 24 ms 22100 KB Output is correct
5 Incorrect 675 ms 86440 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '149813188221811'
6 Halted 0 ms 0 KB -