Submission #1108641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108641		akzytr	Nile (IOI24_nile)	C++17	23 / 100	2064 ms	11292 KiB

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);
				int idxone = W2[i[0]][1];
				int idxn = W2[i[sz_cc - 1]][1];
				ll mi = tb + min(A[idxone] - B[idxone], 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
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18