oj.uz

Submission #720316

# Submission time Handle Problem Language Result Execution time Memory
720316 2023-04-08T02:22:43 Z baojiaopisu Catfish Farm (IOI22_fish) C++17
100 / 100
 425 ms 112552 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e12;
const int N = 2e5 + 10;

struct Data {
	int t, y, w;
};
vector<Data> fish[N];
vector<ll> dp[N], pref[N], pref2[N], suff[N], g[N], suff2[N];
ll f[N];

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
	for(int i = 0; i < m; i++) {
		if(x[i] > 0) fish[x[i] - 1].pb({1, y[i], w[i]});
		fish[x[i]].pb({0, y[i], w[i]});
		fish[x[i] + 1].pb({-1, y[i], w[i]});
	}

	for(int i = 0; i < n; i++) {
		sort(all(fish[i]), [&](Data x, Data y) {
			if(x.y == y.y) return (x.t == 0);
			return x.y < y.y;
		});
	}

	ll ans = 0;
	for(int i = 0; i < n; i++) {
		ll left = 0;
		ll right = 0;
		ll hide = 0;

		dp[i].resize(fish[i].size() + 2);
		g[i].resize(fish[i].size() + 2);
		for(int j = 0; j < fish[i].size(); j++) {
			if(fish[i][j].t == -1) left += fish[i][j].w;
			if(fish[i][j].t == 0) hide += fish[i][j].w;
			if(fish[i][j].t == 1) right += fish[i][j].w;
			dp[i][j] = left + right;
			if(i >= 3) maximize(dp[i][j], left + right + f[i - 3]);
			if(i >= 2) {
				int l = 0, r = fish[i - 2].size() - 1, pos = -1;
				while(l <= r) {
					int mid = (l + r) >> 1;
					if(fish[i - 2][mid].y >= fish[i][j].y) {
						pos = mid;
						r = mid - 1;
					} else l = mid + 1;
				}
				if(pos >= 0) maximize(dp[i][j], right + suff[i - 2][pos]);
				if(pos == -1) pos = fish[i - 2].size();
				pos--;
				if(pos >= 0) maximize(dp[i][j], right + left + pref[i - 2][pos]);
			}

			if(i >= 1) {
				g[i][j] = left + right;
				int l = 0, r = fish[i - 1].size() - 1, pos = -1;
				while(l <= r) {
					int mid = (l + r) >> 1;
					if(fish[i - 1][mid].y >= fish[i][j].y) {
						pos = mid;
						r = mid - 1;
					} else l = mid + 1;
				}
				if(pos >= 0) maximize(g[i][j], right - hide + suff[i - 1][pos]);
				if(pos == -1) pos = fish[i - 1].size();
				pos--;
				if(pos >= 0) maximize(dp[i][j], right + left + pref2[i - 1][pos]);
			}
			if(j + 1 < fish[i].size() && fish[i][j].y == fish[i][j + 1].y) dp[i][j] = -INF;
		}

		suff[i].resize(fish[i].size() + 2);
		pref[i].resize(fish[i].size() + 2);
		pref2[i].resize(fish[i].size() + 2);
		for(int j = fish[i].size(); j >= 0; j--) {
			suff[i][j] = max(suff[i][j + 1], max(g[i][j], dp[i][j]));
		}

		left = right = hide = 0;
		for(int j = 0; j < fish[i].size(); j++) {
			if(fish[i][j].t == -1) left += fish[i][j].w;
			if(fish[i][j].t == 0) hide += fish[i][j].w;
			if(fish[i][j].t == 1) right += fish[i][j].w;
			pref[i][j] = max(g[i][j], dp[i][j]) - right;
			pref2[i][j] = dp[i][j] - right - hide;
			if(j > 0) {
				maximize(pref[i][j], pref[i][j - 1]);
				maximize(pref2[i][j], pref2[i][j - 1]);
			}
		}

		for(int j = 0; j < fish[i].size(); j++) maximize(f[i], max(g[i][j], dp[i][j]));
		if(i > 0) maximize(f[i], f[i - 1]);
		maximize(ans, f[i]);
	}

	return ans;
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int j = 0; j < fish[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
fish.cpp:137:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    if(j + 1 < fish[i].size() && fish[i][j].y == fish[i][j + 1].y) dp[i][j] = -INF;
      |       ~~~~~~^~~~~~~~~~~~~~~~
fish.cpp:148:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for(int j = 0; j < fish[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
fish.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for(int j = 0; j < fish[i].size(); j++) maximize(f[i], max(g[i][j], dp[i][j]));
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 59432 KB Output is correct
2 Correct 103 ms 63888 KB Output is correct
3 Correct 46 ms 49612 KB Output is correct
4 Correct 45 ms 49484 KB Output is correct
5 Correct 289 ms 108692 KB Output is correct
6 Correct 412 ms 112368 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33108 KB Output is correct
2 Correct 170 ms 75196 KB Output is correct
3 Correct 194 ms 83168 KB Output is correct
4 Correct 94 ms 59444 KB Output is correct
5 Correct 108 ms 63900 KB Output is correct
6 Correct 16 ms 33108 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 16 ms 33108 KB Output is correct
9 Correct 16 ms 33192 KB Output is correct
10 Correct 45 ms 49612 KB Output is correct
11 Correct 47 ms 49600 KB Output is correct
12 Correct 113 ms 63688 KB Output is correct
13 Correct 125 ms 68968 KB Output is correct
14 Correct 106 ms 61496 KB Output is correct
15 Correct 119 ms 64800 KB Output is correct
16 Correct 105 ms 61680 KB Output is correct
17 Correct 116 ms 64780 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 49484 KB Output is correct
2 Correct 56 ms 48776 KB Output is correct
3 Correct 96 ms 57776 KB Output is correct
4 Correct 87 ms 56004 KB Output is correct
5 Correct 134 ms 67916 KB Output is correct
6 Correct 128 ms 67304 KB Output is correct
7 Correct 139 ms 67892 KB Output is correct
8 Correct 138 ms 67904 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33192 KB Output is correct
2 Correct 16 ms 33188 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33180 KB Output is correct
5 Correct 19 ms 33200 KB Output is correct
6 Correct 17 ms 33108 KB Output is correct
7 Correct 17 ms 33188 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 17 ms 33320 KB Output is correct
10 Correct 19 ms 33692 KB Output is correct
11 Correct 17 ms 33344 KB Output is correct
12 Correct 17 ms 33356 KB Output is correct
13 Correct 16 ms 33216 KB Output is correct
14 Correct 17 ms 33364 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33192 KB Output is correct
2 Correct 16 ms 33188 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33180 KB Output is correct
5 Correct 19 ms 33200 KB Output is correct
6 Correct 17 ms 33108 KB Output is correct
7 Correct 17 ms 33188 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 17 ms 33320 KB Output is correct
10 Correct 19 ms 33692 KB Output is correct
11 Correct 17 ms 33344 KB Output is correct
12 Correct 17 ms 33356 KB Output is correct
13 Correct 16 ms 33216 KB Output is correct
14 Correct 17 ms 33364 KB Output is correct
15 Correct 16 ms 33236 KB Output is correct
16 Correct 19 ms 33532 KB Output is correct
17 Correct 56 ms 42680 KB Output is correct
18 Correct 54 ms 42292 KB Output is correct
19 Correct 52 ms 42288 KB Output is correct
20 Correct 49 ms 42236 KB Output is correct
21 Correct 48 ms 42288 KB Output is correct
22 Correct 87 ms 51208 KB Output is correct
23 Correct 24 ms 35028 KB Output is correct
24 Correct 41 ms 39700 KB Output is correct
25 Correct 17 ms 33424 KB Output is correct
26 Correct 24 ms 35068 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33192 KB Output is correct
2 Correct 16 ms 33188 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33180 KB Output is correct
5 Correct 19 ms 33200 KB Output is correct
6 Correct 17 ms 33108 KB Output is correct
7 Correct 17 ms 33188 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 17 ms 33320 KB Output is correct
10 Correct 19 ms 33692 KB Output is correct
11 Correct 17 ms 33344 KB Output is correct
12 Correct 17 ms 33356 KB Output is correct
13 Correct 16 ms 33216 KB Output is correct
14 Correct 17 ms 33364 KB Output is correct
15 Correct 16 ms 33236 KB Output is correct
16 Correct 19 ms 33532 KB Output is correct
17 Correct 56 ms 42680 KB Output is correct
18 Correct 54 ms 42292 KB Output is correct
19 Correct 52 ms 42288 KB Output is correct
20 Correct 49 ms 42236 KB Output is correct
21 Correct 48 ms 42288 KB Output is correct
22 Correct 87 ms 51208 KB Output is correct
23 Correct 24 ms 35028 KB Output is correct
24 Correct 41 ms 39700 KB Output is correct
25 Correct 17 ms 33424 KB Output is correct
26 Correct 24 ms 35068 KB Output is correct
27 Correct 20 ms 34092 KB Output is correct
28 Correct 209 ms 76204 KB Output is correct
29 Correct 278 ms 94508 KB Output is correct
30 Correct 276 ms 100056 KB Output is correct
31 Correct 278 ms 99996 KB Output is correct
32 Correct 264 ms 94240 KB Output is correct
33 Correct 267 ms 99880 KB Output is correct
34 Correct 268 ms 99916 KB Output is correct
35 Correct 116 ms 57840 KB Output is correct
36 Correct 278 ms 95200 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 49484 KB Output is correct
2 Correct 56 ms 48776 KB Output is correct
3 Correct 96 ms 57776 KB Output is correct
4 Correct 87 ms 56004 KB Output is correct
5 Correct 134 ms 67916 KB Output is correct
6 Correct 128 ms 67304 KB Output is correct
7 Correct 139 ms 67892 KB Output is correct
8 Correct 138 ms 67904 KB Output is correct
9 Correct 117 ms 67648 KB Output is correct
10 Correct 106 ms 63012 KB Output is correct
11 Correct 209 ms 92996 KB Output is correct
12 Correct 16 ms 33108 KB Output is correct
13 Correct 17 ms 33108 KB Output is correct
14 Correct 19 ms 33188 KB Output is correct
15 Correct 16 ms 33108 KB Output is correct
16 Correct 16 ms 33108 KB Output is correct
17 Correct 16 ms 33192 KB Output is correct
18 Correct 53 ms 49592 KB Output is correct
19 Correct 47 ms 49612 KB Output is correct
20 Correct 45 ms 48852 KB Output is correct
21 Correct 46 ms 48736 KB Output is correct
22 Correct 157 ms 69520 KB Output is correct
23 Correct 214 ms 93096 KB Output is correct
24 Correct 207 ms 93644 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 59432 KB Output is correct
2 Correct 103 ms 63888 KB Output is correct
3 Correct 46 ms 49612 KB Output is correct
4 Correct 45 ms 49484 KB Output is correct
5 Correct 289 ms 108692 KB Output is correct
6 Correct 412 ms 112368 KB Output is correct
7 Correct 17 ms 33108 KB Output is correct
8 Correct 170 ms 75196 KB Output is correct
9 Correct 194 ms 83168 KB Output is correct
10 Correct 94 ms 59444 KB Output is correct
11 Correct 108 ms 63900 KB Output is correct
12 Correct 16 ms 33108 KB Output is correct
13 Correct 16 ms 33108 KB Output is correct
14 Correct 16 ms 33108 KB Output is correct
15 Correct 16 ms 33192 KB Output is correct
16 Correct 45 ms 49612 KB Output is correct
17 Correct 47 ms 49600 KB Output is correct
18 Correct 113 ms 63688 KB Output is correct
19 Correct 125 ms 68968 KB Output is correct
20 Correct 106 ms 61496 KB Output is correct
21 Correct 119 ms 64800 KB Output is correct
22 Correct 105 ms 61680 KB Output is correct
23 Correct 116 ms 64780 KB Output is correct
24 Correct 56 ms 49484 KB Output is correct
25 Correct 56 ms 48776 KB Output is correct
26 Correct 96 ms 57776 KB Output is correct
27 Correct 87 ms 56004 KB Output is correct
28 Correct 134 ms 67916 KB Output is correct
29 Correct 128 ms 67304 KB Output is correct
30 Correct 139 ms 67892 KB Output is correct
31 Correct 138 ms 67904 KB Output is correct
32 Correct 15 ms 33192 KB Output is correct
33 Correct 16 ms 33188 KB Output is correct
34 Correct 16 ms 33108 KB Output is correct
35 Correct 16 ms 33180 KB Output is correct
36 Correct 19 ms 33200 KB Output is correct
37 Correct 17 ms 33108 KB Output is correct
38 Correct 17 ms 33188 KB Output is correct
39 Correct 15 ms 33108 KB Output is correct
40 Correct 17 ms 33320 KB Output is correct
41 Correct 19 ms 33692 KB Output is correct
42 Correct 17 ms 33344 KB Output is correct
43 Correct 17 ms 33356 KB Output is correct
44 Correct 16 ms 33216 KB Output is correct
45 Correct 17 ms 33364 KB Output is correct
46 Correct 16 ms 33236 KB Output is correct
47 Correct 19 ms 33532 KB Output is correct
48 Correct 56 ms 42680 KB Output is correct
49 Correct 54 ms 42292 KB Output is correct
50 Correct 52 ms 42288 KB Output is correct
51 Correct 49 ms 42236 KB Output is correct
52 Correct 48 ms 42288 KB Output is correct
53 Correct 87 ms 51208 KB Output is correct
54 Correct 24 ms 35028 KB Output is correct
55 Correct 41 ms 39700 KB Output is correct
56 Correct 17 ms 33424 KB Output is correct
57 Correct 24 ms 35068 KB Output is correct
58 Correct 20 ms 34092 KB Output is correct
59 Correct 209 ms 76204 KB Output is correct
60 Correct 278 ms 94508 KB Output is correct
61 Correct 276 ms 100056 KB Output is correct
62 Correct 278 ms 99996 KB Output is correct
63 Correct 264 ms 94240 KB Output is correct
64 Correct 267 ms 99880 KB Output is correct
65 Correct 268 ms 99916 KB Output is correct
66 Correct 116 ms 57840 KB Output is correct
67 Correct 278 ms 95200 KB Output is correct
68 Correct 117 ms 67648 KB Output is correct
69 Correct 106 ms 63012 KB Output is correct
70 Correct 209 ms 92996 KB Output is correct
71 Correct 16 ms 33108 KB Output is correct
72 Correct 17 ms 33108 KB Output is correct
73 Correct 19 ms 33188 KB Output is correct
74 Correct 16 ms 33108 KB Output is correct
75 Correct 16 ms 33108 KB Output is correct
76 Correct 16 ms 33192 KB Output is correct
77 Correct 53 ms 49592 KB Output is correct
78 Correct 47 ms 49612 KB Output is correct
79 Correct 45 ms 48852 KB Output is correct
80 Correct 46 ms 48736 KB Output is correct
81 Correct 157 ms 69520 KB Output is correct
82 Correct 214 ms 93096 KB Output is correct
83 Correct 207 ms 93644 KB Output is correct
84 Correct 323 ms 107364 KB Output is correct
85 Correct 334 ms 108356 KB Output is correct
86 Correct 371 ms 110404 KB Output is correct
87 Correct 398 ms 112552 KB Output is correct
88 Correct 16 ms 33108 KB Output is correct
89 Correct 425 ms 112460 KB Output is correct
90 Correct 330 ms 111928 KB Output is correct
91 Correct 307 ms 112044 KB Output is correct