oj.uz

Submission #626199

# Submission time Handle Problem Language Result Execution time Memory
626199 2022-08-11T09:43:27 Z Eae02 Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 17072 KB 
#include "fish.h"

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define all(x) begin(x),end(x)

vector<vector<pair<ll, ll>>> fishAtX;
vector<vector<pair<ll, ll>>> fishWeightSum;

ll weightSum(ll x, ll y) {
	if (x < 0 || x >= (ll)fishWeightSum.size())
		return 0;
	
	ll w = 0;
	for (auto [fy, fw] : fishAtX[x])
		if (fy <= y)
			w += fw;
	return w;
	//ll idx = lower_bound(all(fishWeightSum[x]), make_pair(y, LLONG_MIN)) - fishWeightSum[x].begin();
	//if (fishWeightSum[x][idx].first > y)
	//	idx--;
	//return fishWeightSum[x][idx].second;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	if (M == 0) return 0;
	
	vector<pair<ll, ll>> piers;
	vector<tuple<ll, ll, ll>> fish;
	for (ll i = 0; i < M; i++) {
		fish.emplace_back(X[i], Y[i], W[i]);
		if (X[i] != 0)
			piers.emplace_back(X[i] - 1, Y[i]);
		if (X[i] != N - 1)
			piers.emplace_back(X[i] + 1, Y[i]);
	}
	sort(all(piers));
	piers.erase(unique(all(piers)), piers.end());
	
	fishAtX.resize(N);
	for (ll i = 0; i < M; i++)
		fishAtX[X[i]].emplace_back(Y[i], W[i]);
	
	sort(all(fish));
	fishWeightSum.resize(N);
	for (ll i = 0; i < N; i++) {
		fishWeightSum[i].emplace_back(LLONG_MIN, 0);
	}
	for (auto [x, y, w] : fish) {
		fishWeightSum[x].emplace_back(y, fishWeightSum[x].back().second + w);
	}
	for (ll i = 0; i < N; i++) {
		fishWeightSum[i].emplace_back(LLONG_MAX, fishWeightSum[i].back().second);
	}
	
	vector<ll> dpv(piers.size() + 1);
	ll* dp = &dpv[1];
	for (ll lp = (ll)piers.size() - 1; lp >= -1; lp--) {
		ll cx = lp == -1 ? -5 : piers[lp].first;
		ll cy = lp == -1 ? -5 : piers[lp].second;
		
		//ll x1ShortFirstIdx = lower_bound(all(piers), make_pair(cx + 1, LLONG_MIN)) - piers.begin();
		//ll x1LongFirstIdx = lower_bound(all(piers), make_pair(cx + 1, cy)) - piers.begin();
		//ll x2FirstIdx = lower_bound(all(piers), make_pair(cx + 2, LLONG_MIN)) - piers.begin();
		
		ll ans = LLONG_MIN;
		for (ll np = lp + 1; np < (ll)piers.size(); np++) {
			auto [nx, ny] = piers[np];
			if (nx == cx + 1) {
				if (ny <= cy) {
					ans = max(ans, dp[np]
						+ weightSum(nx + 1, ny)
						- weightSum(nx, ny)
					);
				} else {
					ans = max(ans, dp[np]
						+ weightSum(nx + 1, ny)
						+ weightSum(nx - 1, ny)
						- weightSum(cx, cy)
						- weightSum(cx + 1, cy)
					);
				}
			} else if (nx == cx + 2) {
				if (ny <= cy) {
					ans = max(ans, dp[np] + weightSum(nx + 1, ny));
				} else {
					ans = max(ans, dp[np]
						+ weightSum(nx + 1, ny)
						+ weightSum(nx - 1, ny)
						- weightSum(cx + 1, cy)
					);
				}
			} else if (nx > cx + 2) {
				ans = max(ans, dp[np] + weightSum(nx + 1, ny) + weightSum(nx - 1, ny));
			}
		}
		dp[lp] = ans;
	}
	
	return dp[-1];
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 9688 KB 1st lines differ - on the 1st token, expected: '10082010', found: '-9223372036844693798'
2 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: '-9223372036854775805'
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: '-9223372036854775805'
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: '-9223372036854775805'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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