oj.uz

Submission #1108642

# Submission time Handle Problem Language Result Execution time Memory
1108642 2024-11-04T17:31:15 Z akzytr Nile (IOI24_nile) C++17
23 / 100
 2000 ms 11240 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);
				int idxone = W2[i[0]][1];
				int idxn = W2[i[sz_cc - 1]][1];
				ll mi = tb + A[idxone] - B[idxone];
				mi = min(mi, tb + A[idxn] - B[idxn]);

				for(int j = 1; j < sz_cc - 1; j++) {
					if(W2[i[j + 1]][0] - W2[i[j - 1]][0] <= diff) {
						int idx = W2[i[j]][1];
						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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory 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 508 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 5656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7836 KB Output is correct
2 Correct 39 ms 7564 KB Output is correct
3 Correct 42 ms 7496 KB Output is correct
4 Correct 40 ms 7368 KB Output is correct
5 Correct 54 ms 6916 KB Output is correct
6 Correct 48 ms 11240 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory 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 508 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Incorrect 2 ms 592 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory 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 508 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Incorrect 30 ms 5656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7836 KB Output is correct
2 Correct 39 ms 7564 KB Output is correct
3 Correct 42 ms 7496 KB Output is correct
4 Correct 40 ms 7368 KB Output is correct
5 Correct 54 ms 6916 KB Output is correct
6 Correct 48 ms 11240 KB Output is correct
7 Execution timed out 2070 ms 9252 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory 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 508 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 30 ms 5656 KB Output isn't correct
9 Halted 0 ms 0 KB -