oj.uz

답안 #1074102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074102 2024-08-25T07:59:35 Z Gromp15 메기 농장 (IOI22_fish) C++17
12 / 100
 931 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 k = 0; k < sz(dp[0]); k++) {
				for (int l = 0; l < N; l++) {
					// val[i-2][j][2] <= val[i][l][0]
					int ans = 0;
					{
						int l = 0, r = i-2 >= 0 ? sz(each[i-2]) - 1 : -1;
						while (l <= r) {
							int mid = (l+r)/2;
							if (val[i-2][mid][2] <= val[i][l][0]) ans = mid, l = mid+1;
							else r = mid-1;
						}
					}
					for (int j = 0; j <= ans; j++) {
						int L = k, R = val[i][l][0];
						ckmax(dp2[k][l], dp[j][k] + (L <= R ? each[i-1][R][1] - each[i-1][L][1] : 0));
					}
					for (int j = ans+1; j < sz(dp); j++) {
						int L = k, R = val[i-2][j][2];
						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 70 ms 23004 KB Output is correct
2 Correct 108 ms 25836 KB Output is correct
3 Correct 38 ms 12892 KB Output is correct
4 Correct 32 ms 12884 KB Output is correct
5 Correct 198 ms 42764 KB Output is correct
6 Correct 217 ms 47060 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 931 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 12888 KB Output is correct
2 Correct 30 ms 12892 KB Output is correct
3 Correct 58 ms 16468 KB Output is correct
4 Correct 51 ms 16080 KB Output is correct
5 Correct 105 ms 21804 KB Output is correct
6 Correct 81 ms 21076 KB Output is correct
7 Correct 73 ms 21584 KB Output is correct
8 Correct 86 ms 21632 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '56941582046', found: '56900089829'
14 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '56941582046', found: '56900089829'
14 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '56941582046', found: '56900089829'
14 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 12888 KB Output is correct
2 Correct 30 ms 12892 KB Output is correct
3 Correct 58 ms 16468 KB Output is correct
4 Correct 51 ms 16080 KB Output is correct
5 Correct 105 ms 21804 KB Output is correct
6 Correct 81 ms 21076 KB Output is correct
7 Correct 73 ms 21584 KB Output is correct
8 Correct 86 ms 21632 KB Output is correct
9 Correct 92 ms 23120 KB Output is correct
10 Correct 65 ms 14084 KB Output is correct
11 Correct 173 ms 27648 KB Output is correct
12 Correct 0 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 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 29 ms 12892 KB Output is correct
19 Correct 32 ms 12892 KB Output is correct
20 Correct 32 ms 12892 KB Output is correct
21 Correct 34 ms 12872 KB Output is correct
22 Incorrect 102 ms 24144 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45065264384913'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 23004 KB Output is correct
2 Correct 108 ms 25836 KB Output is correct
3 Correct 38 ms 12892 KB Output is correct
4 Correct 32 ms 12884 KB Output is correct
5 Correct 198 ms 42764 KB Output is correct
6 Correct 217 ms 47060 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Runtime error 931 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -