제출 #1205994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205994		vidux	나일강 (IOI24_nile)	C++17	0 / 100	30 ms	8664 KiB

nile

#include <bits/stdc++.h>
using namespace std;

//#define LOCAL

#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

const int INF = 1e9;
const ll LLINF = 1e18;

vl calculate_costs(vi W, vi A, vi B, vi E) {
    int n = SZ(W);
	vector<pair<ll, pll>> arr(n);
	FOR(i, n) arr[i] = {W[i], {A[i], B[i]}};
	sort(ALL(arr));
	vl ans;
	FORR(d, E) {
		vl a, b, w;
		auto checkSeg = [&]() -> ll {
			int m = SZ(a);
			ll cost = accumulate(ALL(b), 0ll);
			if (m&1 == 0) return cost; 
			else {
				ll mn = LLINF;
				for (int i = 0; i < m; i += 2) mn = min(mn, cost-b[i]+a[i]);
				for (int i = 1; i < m; i += 2) if (abs(w[i-1]-w[i+1]) <= d) mn = min(mn, cost-b[i]+a[i]);
				return mn;
			}
		};
		ans.push_back(0);
		FOR(i, n) {
			w.push_back(arr[i].fi);
			a.push_back(arr[i].se.fi);
			b.push_back(arr[i].se.se);
			if (i == n-1 || abs(arr[i].fi-arr[i+1].fi) > d) {
				ans.back() += checkSeg();
				w.clear();
				a.clear();
				b.clear();
			}
		}
	}
	return ans;
}

#ifdef LOCAL
int main() {
	vl ans = calculate_costs(
		{15, 12, 2, 10, 21},
		{5, 4, 5, 6, 3},
		{1, 2, 2, 3, 2},
		{5, 9, 1}
	);
	FORR(x, ans) cout << x << endl;
    return 0;
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18