oj.uz

Submission #626203

# Submission time Handle Problem Language Result Execution time Memory
626203 2022-08-11T09:48:37 Z Eae02 Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 30584 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<array<ll, 2>> dpv(piers.size() + 1);
	array<ll, 2>* 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();
		for (ll allowNext = 0; allowNext < 2; allowNext++) {
			ll ans = 0;
			for (ll np = lp + 1; np < (ll)piers.size(); np++) {
				auto [nx, ny] = piers[np];
				if (nx == cx + 1) {
					if (allowNext) {
						if (ny <= cy) {
							ans = max(ans, dp[np][0]
								+ weightSum(nx + 1, ny)
								- weightSum(nx, ny)
							);
						} else {
							ans = max(ans, dp[np][1]
								+ 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][1] + weightSum(nx + 1, ny));
					} else {
						ans = max(ans, dp[np][1]
							+ weightSum(nx + 1, ny)
							+ weightSum(nx - 1, ny)
							- weightSum(cx + 1, cy)
						);
					}
				} else if (nx > cx + 2) {
					ans = max(ans, dp[np][1] + weightSum(nx + 1, ny) + weightSum(nx - 1, ny));
				}
			}
			dp[lp][allowNext] = ans;
		}
	}
	
	return dp[-1][1];
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 18352 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 1087 ms 30584 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9684 KB Output is correct
2 Correct 15 ms 9680 KB Output is correct
3 Execution timed out 1085 ms 17224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 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 6 ms 400 KB Output is correct
10 Correct 109 ms 724 KB Output is correct
11 Correct 30 ms 340 KB Output is correct
12 Correct 64 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 28 ms 468 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 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 6 ms 400 KB Output is correct
10 Correct 109 ms 724 KB Output is correct
11 Correct 30 ms 340 KB Output is correct
12 Correct 64 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 28 ms 468 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 953 ms 664 KB Output is correct
17 Execution timed out 1090 ms 6444 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 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 6 ms 400 KB Output is correct
10 Correct 109 ms 724 KB Output is correct
11 Correct 30 ms 340 KB Output is correct
12 Correct 64 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 28 ms 468 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 953 ms 664 KB Output is correct
17 Execution timed out 1090 ms 6444 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9684 KB Output is correct
2 Correct 15 ms 9680 KB Output is correct
3 Execution timed out 1085 ms 17224 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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