Submission #756675

#	Time	Username	Problem	Language	Result	Execution time	Memory
756675		minhcool	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	684 ms	284848 KiB

boxes

//#define local
#ifndef local
#include "boxes.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 1e7 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ll cnt;
ll le[N], ri[N];

ll tol1[N], tol2[N];

ll n, k, l;

ll positions[N];

ll pref[N], suff[N];

ll delivery(int N, int K, int L, int positionss[]){
	for(int i = 0; i < N; i++) positions[i] = positionss[i];
	n = N, k = K, l = L;
	for(ll i = 0; i < n; i++) cnt += (positions[i] <= (l/2));
	//cout << cnt << "\n";
	for(ll i = 0; i < cnt; i++){
		tol1[i] = (i >= k ? tol1[i - k] : 0) + positions[i] * 2;
	}
	for(ll i = 0; i <= k; i++) pref[i] = suff[i] = oo;
	for(ll i = 0; i < (n - cnt); i++){
		tol2[i] = (i >= k ? tol2[i - k] : 0) + (l - positions[n - 1 - i]) * 2;
		pref[(n - cnt - 1 - i) % k] = min(pref[(n - cnt - 1 - i) % k], tol2[i] + (((n - cnt - 1 - i) + (k - 1)) / k) * l);
		suff[(n - cnt - 1 - i) % k] = min(suff[(n - cnt - 1 - i) % k], tol2[i] + (((n - cnt - 1 - i) + (k - 1)) / k) * l);
	}
	pref[(n - cnt) % k] = min(pref[(n - cnt) % k], ((n - cnt + (k - 1)) / k) * l);
	suff[(n - cnt) % k] = min(suff[(n - cnt) % k], ((n - cnt + (k - 1)) / k) * l);
	for(ll i = 2; i < k; i++) pref[i] = min(pref[i], pref[i - 1]);
	//cout << pref[k - 1] << "\n";
	for(ll i = k - 2; i >= 1; i--) suff[i] = min(suff[i], suff[i + 1]);
	ll answer = oo;
	//cout << tol1[cnt - 1] << " " << tol2[n - cnt - 1] << "\n";
	for(ll i = -1; i < cnt; i++){
		ll temp1 = (i >= 0 ? tol1[i] : 0);
		temp1 += ((cnt - 1 - i + (k - 1)) / k) * l;
	//	cout << temp1 << " " << pref[0] << "\n";
		ll md = (cnt - 1 - i) % k;
		if(md){
			answer = min(answer, temp1 + pref[k - md] - l);
			answer = min(answer, temp1 + suff[k - md + 1]);
			answer = min(answer, temp1 + pref[0]);
		}
		else{
			answer = min(answer, temp1 + pref[k - 1]);
			answer = min(answer, temp1 + pref[0]);
		}
	}
	return answer;
	/*
	for(ll i = -1; i < cnt; i++){
		for(ll j = -1; j < (n - cnt); j++){
			ll temp1 = (i >= 0 ? tol1[i] : 0);
			ll temp2 = (j >= 0 ? tol2[j] : 0);
			answer = min(answer, temp1 + temp2 + ((n - 2 - i - j + (k - 1)) / k) * l);
		//	cout << i << " " << j << " " << tol1[i] << " " << tol2[j] << "\n";
		}
	}*/
	return answer;
}

#ifdef local
void process(){
	int n, k, l;
	cin >> n >> k >> l;
	int arr[n];
	for(ll i = 0; i < n; i++) cin >> arr[i];
	cout << delivery(n, k, l, arr) << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen("boxes.inp", "r", stdin);
	ll t = 1;
	//cin >> t;
	while(t--) process();
}
#endif

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:42:17: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   42 | ll delivery(int N, int K, int L, int positionss[]){
      |             ~~~~^
boxes.cpp:20:10: note: shadowed declaration is here
   20 | const ll N = 1e7 + 5;
      |          ^

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