oj.uz

답안 #833328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833328 2023-08-22T04:35:52 Z pavement 메기 농장 (IOI22_fish) C++17
61 / 100
 1000 ms 58272 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back
#define mp make_pair

using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int> X, Y, W;
vector<vector<ll> > mem;
vector<ii> col[100005];

ll dp(int p, int ty) {
	ll ret = 0;
	if (ty == 0) {
		if (p == 0) {
			return 0;
		}
		if (p < 0) {
			return -(ll)1e16;
		}
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
		if (p && !col[p - 1].empty()) {
			ret = max(ret, dp(col[p - 1][0].second, 2));
		}
	} else if (ty == 1) {
		if (p == 0) {
			return 0;
		}
		if (p < 0) {
			return -(ll)1e16;
		}
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
		if (p && !col[p - 1].empty()) {
			ret = max(ret, dp(col[p - 1][0].second, 2));
			ret = max(ret, dp(col[p - 1].back().second, 3));
		}
	} else if (ty == 2) {
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		int x = X[p], y = Y[p];
		ll sum_all = 0;
		int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
		assert(ptr != (int)col[x].size());
		for (int i = ptr; i < (int)col[x].size(); i++) {
			sum_all += W[col[x][i].second];
		}
		ret = max(ret, dp(x - 1, 1) + sum_all);
		if (x && !col[x - 1].empty()) {
			ll sum_cur = 0;
			for (auto [y_p, idx_p] : col[x - 1]) {
				if (y_p <= y) {
					continue;
				}
				while (ptr < (int)col[x].size() && y_p > Y[col[x][ptr].second]) {
					sum_cur += W[col[x][ptr].second];
					ptr++;
				}
				ret = max(ret, dp(idx_p, 2) + sum_cur);
			}
		}
	} else {
		if (mem[p][ty] != -1) {
			return mem[p][ty];
		}
		int x = X[p], y = Y[p];
		ll sum_all = 0;
		int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
		assert(ptr != (int)col[x].size());
		for (int i = ptr; i >= 0; i--) {
			sum_all += W[col[x][i].second];
		}
		ret = max(ret, dp(x, 0) + sum_all);
		if (x && !col[x - 1].empty()) {
			ll sum_cur = 0;
			for (int _ = (int)col[x - 1].size() - 1; _ >= 0; _--) {
				auto [y_p, idx_p] = col[x - 1][_];
				if (y_p >= y) {
					continue;
				}
				while (ptr >= 0 && y_p < Y[col[x][ptr].second]) {
					sum_cur += W[col[x][ptr].second];
					ptr--;
				}
				//~ cout << "DP " << p << ' ' << ty << " TO " << idx_p << ' ' << 3 << ' ' << sum_cur << ' ' << y_p << ' ' << y << '\n';
				ret = max(ret, dp(idx_p, 3) + sum_cur);
			}
		}
	}
	//~ cout << "DP " << p << ' ' << ty << ' ' << ret << '\n';
	return mem[p][ty] = ret;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	::N = N;
	::M = M;
	::X = X;
	::Y = Y;
	::W = W;
	mem = vector<vector<ll> >(N + M, vector<ll>(4, -1));
	for (int i = 0; i < M; i++) {
		col[X[i]].eb(Y[i], i);
	}
	for (int i = 0; i < N; i++) {
		sort(col[i].begin(), col[i].end());
	}
	return dp(N, 0);
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 29520 KB Output is correct
2 Correct 48 ms 33584 KB Output is correct
3 Correct 18 ms 22228 KB Output is correct
4 Correct 14 ms 22116 KB Output is correct
5 Correct 119 ms 56532 KB Output is correct
6 Correct 146 ms 58272 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 1089 ms 38696 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 57 ms 27604 KB Output is correct
4 Correct 31 ms 27732 KB Output is correct
5 Correct 73 ms 37632 KB Output is correct
6 Correct 63 ms 36888 KB Output is correct
7 Correct 75 ms 37400 KB Output is correct
8 Correct 79 ms 37484 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 3 ms 2916 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 3 ms 2916 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 3 ms 2900 KB Output is correct
17 Correct 159 ms 8684 KB Output is correct
18 Correct 146 ms 9004 KB Output is correct
19 Correct 74 ms 8864 KB Output is correct
20 Correct 74 ms 8848 KB Output is correct
21 Correct 77 ms 8908 KB Output is correct
22 Correct 308 ms 15052 KB Output is correct
23 Correct 10 ms 3924 KB Output is correct
24 Correct 44 ms 6740 KB Output is correct
25 Correct 3 ms 2772 KB Output is correct
26 Correct 11 ms 3796 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2656 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 3 ms 2916 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 3 ms 2772 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 3 ms 2900 KB Output is correct
17 Correct 159 ms 8684 KB Output is correct
18 Correct 146 ms 9004 KB Output is correct
19 Correct 74 ms 8864 KB Output is correct
20 Correct 74 ms 8848 KB Output is correct
21 Correct 77 ms 8908 KB Output is correct
22 Correct 308 ms 15052 KB Output is correct
23 Correct 10 ms 3924 KB Output is correct
24 Correct 44 ms 6740 KB Output is correct
25 Correct 3 ms 2772 KB Output is correct
26 Correct 11 ms 3796 KB Output is correct
27 Correct 3 ms 3668 KB Output is correct
28 Execution timed out 1032 ms 32564 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 22228 KB Output is correct
2 Correct 15 ms 22228 KB Output is correct
3 Correct 57 ms 27604 KB Output is correct
4 Correct 31 ms 27732 KB Output is correct
5 Correct 73 ms 37632 KB Output is correct
6 Correct 63 ms 36888 KB Output is correct
7 Correct 75 ms 37400 KB Output is correct
8 Correct 79 ms 37484 KB Output is correct
9 Correct 79 ms 37272 KB Output is correct
10 Correct 55 ms 26188 KB Output is correct
11 Correct 142 ms 49968 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2768 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 14 ms 22228 KB Output is correct
19 Correct 17 ms 22200 KB Output is correct
20 Correct 14 ms 22228 KB Output is correct
21 Correct 13 ms 22200 KB Output is correct
22 Correct 67 ms 36904 KB Output is correct
23 Correct 136 ms 49972 KB Output is correct
24 Correct 157 ms 50508 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 29520 KB Output is correct
2 Correct 48 ms 33584 KB Output is correct
3 Correct 18 ms 22228 KB Output is correct
4 Correct 14 ms 22116 KB Output is correct
5 Correct 119 ms 56532 KB Output is correct
6 Correct 146 ms 58272 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Execution timed out 1089 ms 38696 KB Time limit exceeded
9 Halted 0 ms 0 KB -