oj.uz

답안 #1108692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1108692 2024-11-04T19:12:11 Z akzytr 나일강 (IOI24_nile) C++17
67 / 100
 2000 ms 14124 KB 
#include <bits/stdc++.h>
#define ve vector
#define pb push_back
#define ar array
#define ll long long
#define sz(x) (int)(x.size())
using namespace std;

ve<ll> calculate_costs(ve<int> W, ve<int> A, ve<int> B, ve<int> Q) {
	ve<ll> ans;
	int N = sz(W);
	array<ll, 2> W2[N];

	for(int i = 0; i < N; i++) {
		W2[i] = {W[i], i};
	}
	sort(W2, W2 + N);

	for(int diff : Q) {
		ll tc = 0;
		ve<ve<int>> ccs;
		ve<int> curcc;
		for(int i = 0; i < N; i++) {
			if(i != 0 && W2[i][0] - W2[i - 1][0] > diff) {
				ccs.pb(curcc);
				ve<int> nc;
				curcc = nc;
			}
			curcc.pb(i);
		}
		ccs.pb(curcc);

		for(auto i : ccs) {
			assert(sz(i) >= 1);
			ll tb = 0;
			for(int j : i) {
				int idx = W2[j][1];
				tb += B[idx];
			}

			if(sz(i) % 2) {
				int sz_cc = sz(i);
				ll mi = (ll)91e18;

				for(int j = 0; j < sz_cc; j++) {

					int idx = W2[i[j]][1];
					if(j % 2 == 0) {
						mi = min(mi, tb - B[idx] + A[idx]);
					} else if(W2[i[j + 1]][0] - W2[i[j - 1]][0] <= diff) {
						mi = min(mi, tb - B[idx] + A[idx]);
					}
				}

				tb = mi;
			}

			tc += tb;
		}
		ans.pb(tc);
	}

	return ans;
}

// int main() {
// 	int N;
// 	cin >> N;
//
// 	ve<int> w;
// 	ve<int> a;
// 	ve<int> b;
// 	ve<int> q;
// 	for(int i = 0; i < N; i++) {
// 		int x, y, z;
// 		cin >> x >> y >> z;
// 		w.pb(x);
// 		a.pb(y);
// 		b.pb(z);
// 	}
// 	int Q;
// 	cin >> Q;
// 	for(int i = 0; i < Q; i++) {
// 		int x;
// 		cin >> x;
// 		q.pb(x);
// 	}
//
// 	calculate_costs(w, a, b, q);
// }

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 7104 KB Output is correct
2 Correct 31 ms 8096 KB Output is correct
3 Correct 30 ms 8136 KB Output is correct
4 Correct 30 ms 8128 KB Output is correct
5 Correct 30 ms 8152 KB Output is correct
6 Correct 30 ms 8136 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 8748 KB Output is correct
2 Correct 48 ms 8404 KB Output is correct
3 Correct 44 ms 8520 KB Output is correct
4 Correct 51 ms 8380 KB Output is correct
5 Correct 41 ms 7860 KB Output is correct
6 Correct 53 ms 12316 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 2 ms 592 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 848 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 31 ms 7104 KB Output is correct
8 Correct 31 ms 8096 KB Output is correct
9 Correct 30 ms 8136 KB Output is correct
10 Correct 30 ms 8128 KB Output is correct
11 Correct 30 ms 8152 KB Output is correct
12 Correct 30 ms 8136 KB Output is correct
13 Correct 39 ms 8748 KB Output is correct
14 Correct 48 ms 8404 KB Output is correct
15 Correct 44 ms 8520 KB Output is correct
16 Correct 51 ms 8380 KB Output is correct
17 Correct 41 ms 7860 KB Output is correct
18 Correct 53 ms 12316 KB Output is correct
19 Correct 2 ms 592 KB Output is correct
20 Correct 3 ms 592 KB Output is correct
21 Correct 2 ms 592 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 2 ms 592 KB Output is correct
25 Correct 52 ms 10244 KB Output is correct
26 Correct 45 ms 10188 KB Output is correct
27 Correct 51 ms 10452 KB Output is correct
28 Correct 54 ms 10460 KB Output is correct
29 Correct 50 ms 10204 KB Output is correct
30 Correct 61 ms 14124 KB Output is correct

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 8748 KB Output is correct
2 Correct 48 ms 8404 KB Output is correct
3 Correct 44 ms 8520 KB Output is correct
4 Correct 51 ms 8380 KB Output is correct
5 Correct 41 ms 7860 KB Output is correct
6 Correct 53 ms 12316 KB Output is correct
7 Execution timed out 2062 ms 10280 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 31 ms 7104 KB Output is correct
9 Correct 31 ms 8096 KB Output is correct
10 Correct 30 ms 8136 KB Output is correct
11 Correct 30 ms 8128 KB Output is correct
12 Correct 30 ms 8152 KB Output is correct
13 Correct 30 ms 8136 KB Output is correct
14 Correct 39 ms 8748 KB Output is correct
15 Correct 48 ms 8404 KB Output is correct
16 Correct 44 ms 8520 KB Output is correct
17 Correct 51 ms 8380 KB Output is correct
18 Correct 41 ms 7860 KB Output is correct
19 Correct 53 ms 12316 KB Output is correct
20 Correct 2 ms 592 KB Output is correct
21 Correct 3 ms 592 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 2 ms 592 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 52 ms 10244 KB Output is correct
27 Correct 45 ms 10188 KB Output is correct
28 Correct 51 ms 10452 KB Output is correct
29 Correct 54 ms 10460 KB Output is correct
30 Correct 50 ms 10204 KB Output is correct
31 Correct 61 ms 14124 KB Output is correct
32 Execution timed out 2062 ms 10280 KB Time limit exceeded
33 Halted 0 ms 0 KB -