Submission #1108692

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1108692	2024-11-04T19:12:11 Z	akzytr	Nile (IOI24_nile)	C++17	67 / 100	2000 ms	14124 KB

nile

#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

#	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	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	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	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

#	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	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

#	Verdict	Execution time	Memory	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

#	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	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	-

Submission #1108692

Compilation message