답안 #313910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
313910	2020-10-17T09:20:37 Z	AmineWeslati	선물상자 (IOI15_boxes)	C++14	100 / 100	931 ms	360056 KB

boxes

//Never stop trying
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 1e7 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

#define dbg(x) cerr << " - " << #x << " : " << x << endl;
#define dbgs(x,y) cerr << " - " << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << " - " << #v << " : " << endl << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;

void IO() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int N,K,L;
vi pos;

V<ll> CW(MX),CCW(MX);

void precompute(){
	FOR(i,0,N){
		ll x=0;
		if(i-K>=0) x+=CW[i-K];
		x+=pos[i]*2;
		CW[i]=x;
	}


	//FOR(i,0,N) cout << CW[i] << ' '; cout << endl;

	ROF(i,0,N){
		ll x=0;
		if(i+K<N) x+=CCW[i+K];
		x+=(L-pos[i])*2;
		CCW[i]=x;
	}
	//FOR(i,0,N) cout << CCW[i] << ' '; cout << endl;
}


ll delivery(int NN, int KK, int LL, int positions[]){
	N=NN; K=KK; L=LL; FOR(i,0,N) pos.pb(positions[i]);

	sort(all(pos));

	precompute();

	ll ans=min(CW[N-1],CCW[0]);
	FOR(i,0,N){
		int l=i,r=i+K-1; ckmin(r,N-1);
		ll x=L;
		if(l) x+=CW[l-1];
		if(r+1<N) x+=CCW[r+1];
		ckmin(ans,x);

		x=CW[i]; if(i+1<N) x+=CCW[i+1];
		ckmin(ans,x);
	}
	return ans;
}




/*
3 2 8
1 2 5
*/

/* Careful!!!
	.Array bounds
	.Infinite loops
	.Uninitialized variables / empty containers
	.Order of input

   Some insights:
	.Binary search
	.Graph representation
	.Write brute force code
	.Change your approach
*/

Compilation message

boxes.cpp: In function 'void IO()':
boxes.cpp:47:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  freopen("input.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boxes.cpp:48:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  freopen("output.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	156916 KB	Output is correct
2	Correct	92 ms	157048 KB	Output is correct
3	Correct	92 ms	157048 KB	Output is correct
4	Correct	91 ms	156872 KB	Output is correct
5	Correct	91 ms	156828 KB	Output is correct
6	Correct	92 ms	156992 KB	Output is correct
7	Correct	91 ms	156920 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	156920 KB	Output is correct
2	Correct	90 ms	156920 KB	Output is correct
3	Correct	91 ms	156920 KB	Output is correct
4	Correct	90 ms	156920 KB	Output is correct
5	Correct	93 ms	156848 KB	Output is correct
6	Correct	93 ms	156920 KB	Output is correct
7	Correct	91 ms	156920 KB	Output is correct
8	Correct	90 ms	156920 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	156924 KB	Output is correct
2	Correct	90 ms	156920 KB	Output is correct
3	Correct	91 ms	156924 KB	Output is correct
4	Correct	90 ms	156920 KB	Output is correct
5	Correct	92 ms	156920 KB	Output is correct
6	Correct	91 ms	156920 KB	Output is correct
7	Correct	90 ms	156920 KB	Output is correct
8	Correct	93 ms	156916 KB	Output is correct
9	Correct	92 ms	157048 KB	Output is correct
10	Correct	92 ms	157048 KB	Output is correct
11	Correct	91 ms	156872 KB	Output is correct
12	Correct	91 ms	156828 KB	Output is correct
13	Correct	92 ms	156992 KB	Output is correct
14	Correct	91 ms	156920 KB	Output is correct
15	Correct	92 ms	156920 KB	Output is correct
16	Correct	90 ms	156920 KB	Output is correct
17	Correct	91 ms	156920 KB	Output is correct
18	Correct	90 ms	156920 KB	Output is correct
19	Correct	93 ms	156848 KB	Output is correct
20	Correct	93 ms	156920 KB	Output is correct
21	Correct	91 ms	156920 KB	Output is correct
22	Correct	90 ms	156920 KB	Output is correct
23	Correct	90 ms	156972 KB	Output is correct
24	Correct	91 ms	156920 KB	Output is correct
25	Correct	93 ms	156920 KB	Output is correct
26	Correct	91 ms	157048 KB	Output is correct
27	Correct	94 ms	156920 KB	Output is correct
28	Correct	90 ms	156920 KB	Output is correct
29	Correct	92 ms	156920 KB	Output is correct
30	Correct	92 ms	157048 KB	Output is correct
31	Correct	91 ms	156920 KB	Output is correct
32	Correct	92 ms	156920 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	156924 KB	Output is correct
2	Correct	90 ms	156920 KB	Output is correct
3	Correct	91 ms	156924 KB	Output is correct
4	Correct	90 ms	156920 KB	Output is correct
5	Correct	92 ms	156920 KB	Output is correct
6	Correct	91 ms	156920 KB	Output is correct
7	Correct	90 ms	156920 KB	Output is correct
8	Correct	93 ms	156916 KB	Output is correct
9	Correct	92 ms	157048 KB	Output is correct
10	Correct	92 ms	157048 KB	Output is correct
11	Correct	91 ms	156872 KB	Output is correct
12	Correct	91 ms	156828 KB	Output is correct
13	Correct	92 ms	156992 KB	Output is correct
14	Correct	91 ms	156920 KB	Output is correct
15	Correct	92 ms	156920 KB	Output is correct
16	Correct	90 ms	156920 KB	Output is correct
17	Correct	91 ms	156920 KB	Output is correct
18	Correct	90 ms	156920 KB	Output is correct
19	Correct	93 ms	156848 KB	Output is correct
20	Correct	93 ms	156920 KB	Output is correct
21	Correct	91 ms	156920 KB	Output is correct
22	Correct	90 ms	156920 KB	Output is correct
23	Correct	90 ms	156972 KB	Output is correct
24	Correct	91 ms	156920 KB	Output is correct
25	Correct	93 ms	156920 KB	Output is correct
26	Correct	91 ms	157048 KB	Output is correct
27	Correct	94 ms	156920 KB	Output is correct
28	Correct	90 ms	156920 KB	Output is correct
29	Correct	92 ms	156920 KB	Output is correct
30	Correct	92 ms	157048 KB	Output is correct
31	Correct	91 ms	156920 KB	Output is correct
32	Correct	92 ms	156920 KB	Output is correct
33	Correct	163 ms	164968 KB	Output is correct
34	Correct	129 ms	167020 KB	Output is correct
35	Correct	131 ms	167548 KB	Output is correct
36	Correct	159 ms	175008 KB	Output is correct
37	Correct	169 ms	174824 KB	Output is correct
38	Correct	162 ms	174868 KB	Output is correct
39	Correct	167 ms	173288 KB	Output is correct
40	Correct	135 ms	168736 KB	Output is correct
41	Correct	167 ms	174952 KB	Output is correct
42	Correct	135 ms	169084 KB	Output is correct

Subtask #6
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	156924 KB	Output is correct
2	Correct	90 ms	156920 KB	Output is correct
3	Correct	91 ms	156924 KB	Output is correct
4	Correct	90 ms	156920 KB	Output is correct
5	Correct	92 ms	156920 KB	Output is correct
6	Correct	91 ms	156920 KB	Output is correct
7	Correct	90 ms	156920 KB	Output is correct
8	Correct	93 ms	156916 KB	Output is correct
9	Correct	92 ms	157048 KB	Output is correct
10	Correct	92 ms	157048 KB	Output is correct
11	Correct	91 ms	156872 KB	Output is correct
12	Correct	91 ms	156828 KB	Output is correct
13	Correct	92 ms	156992 KB	Output is correct
14	Correct	91 ms	156920 KB	Output is correct
15	Correct	92 ms	156920 KB	Output is correct
16	Correct	90 ms	156920 KB	Output is correct
17	Correct	91 ms	156920 KB	Output is correct
18	Correct	90 ms	156920 KB	Output is correct
19	Correct	93 ms	156848 KB	Output is correct
20	Correct	93 ms	156920 KB	Output is correct
21	Correct	91 ms	156920 KB	Output is correct
22	Correct	90 ms	156920 KB	Output is correct
23	Correct	90 ms	156972 KB	Output is correct
24	Correct	91 ms	156920 KB	Output is correct
25	Correct	93 ms	156920 KB	Output is correct
26	Correct	91 ms	157048 KB	Output is correct
27	Correct	94 ms	156920 KB	Output is correct
28	Correct	90 ms	156920 KB	Output is correct
29	Correct	92 ms	156920 KB	Output is correct
30	Correct	92 ms	157048 KB	Output is correct
31	Correct	91 ms	156920 KB	Output is correct
32	Correct	92 ms	156920 KB	Output is correct
33	Correct	163 ms	164968 KB	Output is correct
34	Correct	129 ms	167020 KB	Output is correct
35	Correct	131 ms	167548 KB	Output is correct
36	Correct	159 ms	175008 KB	Output is correct
37	Correct	169 ms	174824 KB	Output is correct
38	Correct	162 ms	174868 KB	Output is correct
39	Correct	167 ms	173288 KB	Output is correct
40	Correct	135 ms	168736 KB	Output is correct
41	Correct	167 ms	174952 KB	Output is correct
42	Correct	135 ms	169084 KB	Output is correct
43	Correct	931 ms	358944 KB	Output is correct
44	Correct	501 ms	281372 KB	Output is correct
45	Correct	535 ms	289180 KB	Output is correct
46	Correct	852 ms	359836 KB	Output is correct
47	Correct	851 ms	360056 KB	Output is correct
48	Correct	855 ms	359836 KB	Output is correct
49	Correct	863 ms	344604 KB	Output is correct
50	Correct	578 ms	298396 KB	Output is correct
51	Correct	912 ms	359740 KB	Output is correct
52	Correct	586 ms	301080 KB	Output is correct

답안 #313910

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 10.0 / 10.0

Subtask #3 15.0 / 15.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #6 30.0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
10.0 / 10.0

Subtask #3
15.0 / 15.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0

Subtask #6
30.0 / 30.0