oj.uz

답안 #1074089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074089 2024-08-25T07:50:19 Z Gromp15 메기 농장 (IOI22_fish) C++17
40 / 100
 1000 ms 2097152 KB 
#include <bits/stdc++.h>
#include "fish.h"
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;

const ll INF = 1e18;
template<typename T> bool ckmin(T &a, const T &b ) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b ) { return a < b ? a = b, 1 : 0; }

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w) {
	vector<vector<ar<ll, 2>>> each(n);
	for (int i = 0; i < m; i++) {
		each[x[i]].push_back({y[i], w[i]});
		each[x[i]].push_back({y[i]-1, 0});
	}
	for (int i = 0; i < n; i++) each[i].push_back({n-1, 0}), each[i].push_back({-1, 0});
	for (int i = 0; i < n; i++) {
		sort(all(each[i]));
		vector<ar<ll, 2>> nw;
		ll s = 0;
		for (int j = 0; j < sz(each[i]); j++) {
			int r = j;
			while (r+1 < sz(each[i]) && each[i][r+1][0] == each[i][r][0]) r++;
			for (int k = j; k <= r; k++) s += each[i][k][1];
			nw.push_back({each[i][j][0], s});
			j = r;
		}
		swap(each[i], nw);
	}
	vector<vector<ll>> dp;
	auto query = [&](int pos, int x) {
		return prev(upper_bound(all(each[pos]), ar<ll, 2>{x, LLONG_MAX})) - each[pos].begin();
	};
	vector<vector<ar<int, 3>>> val(n);
	for (int i = 0; i < n; i++) {
		val[i].resize(sz(each[i]));
		for (int k = 0; k < sz(each[i]); k++) {
			for (int j = -1; j <= 1; j++) {
				if (i + j >= 0 && i + j < n) {
					val[i][k][j+1] = query(i + j, each[i][k][0]);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		vector<vector<ll>> dp2;
		const int N = sz(each[i]);
		dp2.resize(i ? sz(each[i-1]) : 1, vector<ll>(N, -INF));
		if (!i) {
			for (int j = 0; j < N; j++) {
				dp2[0][j] = 0;
			}
			swap(dp, dp2);
		}
		else {
			for (int j = 0; j < sz(dp); j++) {
				for (int k = 0; k < sz(dp[j]); k++) {
					for (int l = 0; l < N; l++) {
						int L = k, R = max(i-2 >= 0 ? val[i-2][j][2] : 0, val[i][l][0]);
						ckmax(dp2[k][l], dp[j][k] + (L <= R ? each[i-1][R][1] - each[i-1][L][1] : 0));
					}
				}
			}
			swap(dp, dp2);
		}
	}
	ll ans = -INF;
	for (int i = 0; i < sz(dp); i++) {
		for (int j = 0; j < sz(dp[i]); j++) {
			int L = j, R = val[n-2][i][2];
			ckmax(ans, dp[i][j] + (L <= R ? each[n-1][R][1] - each[n-1][L][1] : 0));
		}
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 23004 KB Output is correct
2 Correct 80 ms 25992 KB Output is correct
3 Correct 31 ms 12888 KB Output is correct
4 Correct 32 ms 12888 KB Output is correct
5 Correct 198 ms 42780 KB Output is correct
6 Correct 241 ms 47060 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12864 KB Output is correct
2 Correct 32 ms 12892 KB Output is correct
3 Correct 53 ms 16464 KB Output is correct
4 Correct 47 ms 16176 KB Output is correct
5 Correct 76 ms 21688 KB Output is correct
6 Correct 70 ms 21072 KB Output is correct
7 Correct 82 ms 21724 KB Output is correct
8 Correct 81 ms 21596 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 444 KB Output is correct
14 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 444 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 26 ms 756 KB Output is correct
17 Execution timed out 1033 ms 5880 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 444 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 26 ms 756 KB Output is correct
17 Execution timed out 1033 ms 5880 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12864 KB Output is correct
2 Correct 32 ms 12892 KB Output is correct
3 Correct 53 ms 16464 KB Output is correct
4 Correct 47 ms 16176 KB Output is correct
5 Correct 76 ms 21688 KB Output is correct
6 Correct 70 ms 21072 KB Output is correct
7 Correct 82 ms 21724 KB Output is correct
8 Correct 81 ms 21596 KB Output is correct
9 Correct 86 ms 23124 KB Output is correct
10 Correct 71 ms 14088 KB Output is correct
11 Correct 125 ms 27720 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 436 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 30 ms 12892 KB Output is correct
19 Correct 29 ms 12888 KB Output is correct
20 Correct 32 ms 12760 KB Output is correct
21 Correct 29 ms 12888 KB Output is correct
22 Correct 95 ms 24400 KB Output is correct
23 Correct 179 ms 35156 KB Output is correct
24 Correct 148 ms 36180 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 23004 KB Output is correct
2 Correct 80 ms 25992 KB Output is correct
3 Correct 31 ms 12888 KB Output is correct
4 Correct 32 ms 12888 KB Output is correct
5 Correct 198 ms 42780 KB Output is correct
6 Correct 241 ms 47060 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1076 ms 2097152 KB Time limit exceeded
9 Halted 0 ms 0 KB -