Submission #1185010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185010		sano	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	562 ms	199312 KiB

boxes

//#pragma GCC optimize("O3")
//#pragma GCC target("tune=native")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "boxes.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 47
#define prv2 43
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
//using namespace __gnu_pbds;

//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;

ll int delivery(int n, int k, int l, int positions[]) {
	vec<ll> a, b;
	For(i, n) {
		if (positions[i] <= l / 2) {
			a.push_back(positions[i]);
		}
		else b.push_back(l - positions[i]);
	}
	sort(all(a)); sort(all(b));
	vec<ll> dp1(a.size() + 1, 0);
	vec<ll> dp2(b.size() + 1, 0);
	For(i, a.size()) {
		if (i + 1 - k < 0) dp1[i + 1] = 2*a[i];
		else dp1[i + 1] = dp1[i + 1 - k] + 2*a[i];
	}
	For(i, b.size()) {
		if (i + 1 - k < 0) dp2[i + 1] = 2*b[i];
		else dp2[i + 1] = dp2[i + 1 - k] + 2*b[i];
	}
	//bez otocky
	ll mini = dp1[a.size()] + dp2[b.size()];
	//s otockou
	ll as = a.size(), bs = b.size();
	For(i, k + 1) {
		ll x, y;
		if (as - i >= 0) {
			x = dp1[as - i];
		}
		else {
			x = 0;
		}
		if ((bs - (k - i)) >= 0) {
			y = dp2[bs - (k - i)];
		}
		else {
			y = 0;
		}
		mini = min(mini, x + y + l);
	}
	return mini;
}

/*
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, k, l; cin >> n >> k >> l;
	int p[100];
	For(i, n) cin >> p[i];
	cout << delivery(n, k, l, p) << '\n';
	return 0;
}*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30