oj.uz

답안 #756675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756675 2023-06-12T04:29:07 Z minhcool 선물상자 (IOI15_boxes) C++17
100 / 100
 684 ms 284848 KB 
//#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 320 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 324 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 320 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 324 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 57 ms 20244 KB Output is correct
34 Correct 33 ms 21840 KB Output is correct
35 Correct 39 ms 22300 KB Output is correct
36 Correct 68 ms 29644 KB Output is correct
37 Correct 72 ms 29644 KB Output is correct
38 Correct 62 ms 29644 KB Output is correct
39 Correct 56 ms 28152 KB Output is correct
40 Correct 38 ms 23500 KB Output is correct
41 Correct 63 ms 29616 KB Output is correct
42 Correct 40 ms 23772 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 320 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 324 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 57 ms 20244 KB Output is correct
34 Correct 33 ms 21840 KB Output is correct
35 Correct 39 ms 22300 KB Output is correct
36 Correct 68 ms 29644 KB Output is correct
37 Correct 72 ms 29644 KB Output is correct
38 Correct 62 ms 29644 KB Output is correct
39 Correct 56 ms 28152 KB Output is correct
40 Correct 38 ms 23500 KB Output is correct
41 Correct 63 ms 29616 KB Output is correct
42 Correct 40 ms 23772 KB Output is correct
43 Correct 647 ms 284848 KB Output is correct
44 Correct 286 ms 223380 KB Output is correct
45 Correct 377 ms 223428 KB Output is correct
46 Correct 631 ms 277624 KB Output is correct
47 Correct 652 ms 273004 KB Output is correct
48 Correct 684 ms 269856 KB Output is correct
49 Correct 585 ms 272852 KB Output is correct
50 Correct 372 ms 240268 KB Output is correct
51 Correct 621 ms 275132 KB Output is correct
52 Correct 386 ms 241424 KB Output is correct