oj.uz

Submission #626211

# Submission time Handle Problem Language Result Execution time Memory
626211 2022-08-11T09:54:39 Z Eae02 Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 45980 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>>> fishWeightSum;

ll weightSum(ll x, ll y) {
	if (x < 0 || x >= (ll)fishWeightSum.size())
		return 0;
	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());
	
	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 x1ShorterFirstIdx = lower_bound(all(piers), make_pair(cx + 1, LLONG_MIN)) - piers.begin();
		ll x1LongerFirstIdx = lower_bound(all(piers), make_pair(cx + 1, cy)) - piers.begin();
		ll x2ShorterFirstIdx = lower_bound(all(piers), make_pair(cx + 2, LLONG_MIN)) - piers.begin();
		ll x2LongerFirstIdx = lower_bound(all(piers), make_pair(cx + 2, cy)) - piers.begin();
		ll c3FirstIdx = lower_bound(all(piers), make_pair(cx + 3, LLONG_MIN)) - piers.begin();
		
		for (ll allowNext = 0; allowNext < 2; allowNext++) {
			ll ans = 0;
			if (allowNext) {
				for (ll np = x1ShorterFirstIdx; np < x1LongerFirstIdx; np++) {
					auto [nx, ny] = piers[np];
					ans = max(ans, dp[np][0]
						+ weightSum(nx + 1, ny)
						- weightSum(nx, ny)
					);
				}
				for (ll np = x1LongerFirstIdx; np < x2ShorterFirstIdx; np++) {
					auto [nx, ny] = piers[np];
					ans = max(ans, dp[np][1]
						+ weightSum(nx + 1, ny)
						+ weightSum(nx - 1, ny)
						- weightSum(cx, cy)
						- weightSum(cx + 1, cy)
					);
				}
			}
			
			for (ll np = x2ShorterFirstIdx; np < x2LongerFirstIdx; np++) {
				auto [nx, ny] = piers[np];
				ans = max(ans, dp[np][1] + weightSum(nx + 1, ny));
			}
			for (ll np = x2LongerFirstIdx; np < c3FirstIdx; np++) {
				auto [nx, ny] = piers[np];
				ans = max(ans, dp[np][1]
					+ weightSum(nx + 1, ny)
					+ weightSum(nx - 1, ny)
					- weightSum(cx + 1, cy)
				);
			}
			for (ll np = c3FirstIdx; np < (ll)piers.size(); np++) {
				auto [nx, ny] = piers[np];
				ans = max(ans, dp[np][1] + weightSum(nx + 1, ny) + weightSum(nx - 1, ny));
			}
			
			dp[lp][allowNext] = ans;
		}
		
		/*
		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 Correct 66 ms 14948 KB Output is correct
2 Correct 83 ms 17260 KB Output is correct
3 Correct 10 ms 7252 KB Output is correct
4 Correct 11 ms 7328 KB Output is correct
5 Execution timed out 1096 ms 45980 KB Time limit exceeded
6 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 1095 ms 25172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7380 KB Output is correct
2 Correct 11 ms 7328 KB Output is correct
3 Execution timed out 1091 ms 13384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

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 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 1 ms 212 KB Output is correct
9 Correct 7 ms 400 KB Output is correct
10 Correct 117 ms 596 KB Output is correct
11 Correct 36 ms 404 KB Output is correct
12 Correct 107 ms 468 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 57 ms 340 KB Output is correct

Subtask #5
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 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 1 ms 212 KB Output is correct
9 Correct 7 ms 400 KB Output is correct
10 Correct 117 ms 596 KB Output is correct
11 Correct 36 ms 404 KB Output is correct
12 Correct 107 ms 468 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 57 ms 340 KB Output is correct
15 Correct 6 ms 340 KB Output is correct
16 Correct 407 ms 640 KB Output is correct
17 Execution timed out 1048 ms 5584 KB Time limit exceeded
18 Halted 0 ms 0 KB -

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 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 1 ms 212 KB Output is correct
9 Correct 7 ms 400 KB Output is correct
10 Correct 117 ms 596 KB Output is correct
11 Correct 36 ms 404 KB Output is correct
12 Correct 107 ms 468 KB Output is correct
13 Correct 3 ms 212 KB Output is correct
14 Correct 57 ms 340 KB Output is correct
15 Correct 6 ms 340 KB Output is correct
16 Correct 407 ms 640 KB Output is correct
17 Execution timed out 1048 ms 5584 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7380 KB Output is correct
2 Correct 11 ms 7328 KB Output is correct
3 Execution timed out 1091 ms 13384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 14948 KB Output is correct
2 Correct 83 ms 17260 KB Output is correct
3 Correct 10 ms 7252 KB Output is correct
4 Correct 11 ms 7328 KB Output is correct
5 Execution timed out 1096 ms 45980 KB Time limit exceeded
6 Halted 0 ms 0 KB -