Submission #756654

#	Time	Username	Problem	Language	Result	Execution time	Memory
756654		minhcool	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2016 ms	22372 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 = 3e5 + 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 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 < (n - cnt); i++){
		tol2[i] = (i >= k ? tol2[i - k] : 0) + (l - positions[n - 1 - i]) * 2;
	}
	ll answer = oo;
	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);
	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:40:17: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   40 | ll delivery(int N, int K, int L, int positionss[]){
      |             ~~~~^
boxes.cpp:20:10: note: shadowed declaration is here
   20 | const ll N = 3e5 + 5;
      |          ^

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