Submission #130916

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
130916	2019-07-16T08:44:46 Z	antimirage	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2000 ms	92120 KB

boxes

#include "boxes.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e7 + 5;

long long dp[N];

long long delivery(int n, int k, int l, int pos[]) {		
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= min(k, i + 1); j++) {
			if (j > i) {
				dp[i] = min(dp[i], min( pos[i] * 2, min( l, (l - pos[0]) * 2 ) ) * 1ll );	
			} else { 
				dp[i] = min(dp[i], dp[i - j] + min( pos[i] * 2, min( l, (l - pos[i - j + 1]) * 2 ) ) );
			}
		}
	}
	return dp[n - 1];
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	78584 KB	Output is correct
2	Correct	67 ms	78584 KB	Output is correct
3	Correct	67 ms	78584 KB	Output is correct
4	Correct	66 ms	78552 KB	Output is correct
5	Correct	66 ms	78584 KB	Output is correct
6	Correct	66 ms	78584 KB	Output is correct
7	Correct	67 ms	78652 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	78612 KB	Output is correct
2	Correct	68 ms	78556 KB	Output is correct
3	Correct	70 ms	78600 KB	Output is correct
4	Correct	69 ms	78584 KB	Output is correct
5	Correct	68 ms	78584 KB	Output is correct
6	Correct	68 ms	78656 KB	Output is correct
7	Correct	72 ms	78696 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	78584 KB	Output is correct
2	Correct	67 ms	78584 KB	Output is correct
3	Correct	77 ms	78520 KB	Output is correct
4	Correct	68 ms	78672 KB	Output is correct
5	Correct	76 ms	78648 KB	Output is correct
6	Correct	79 ms	78584 KB	Output is correct
7	Correct	67 ms	78712 KB	Output is correct
8	Correct	67 ms	78588 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	78584 KB	Output is correct
2	Correct	67 ms	78584 KB	Output is correct
3	Correct	67 ms	78584 KB	Output is correct
4	Correct	66 ms	78552 KB	Output is correct
5	Correct	66 ms	78584 KB	Output is correct
6	Correct	66 ms	78584 KB	Output is correct
7	Correct	67 ms	78652 KB	Output is correct
8	Correct	68 ms	78612 KB	Output is correct
9	Correct	68 ms	78556 KB	Output is correct
10	Correct	70 ms	78600 KB	Output is correct
11	Correct	69 ms	78584 KB	Output is correct
12	Correct	68 ms	78584 KB	Output is correct
13	Correct	68 ms	78656 KB	Output is correct
14	Correct	72 ms	78696 KB	Output is correct
15	Correct	66 ms	78584 KB	Output is correct
16	Correct	67 ms	78584 KB	Output is correct
17	Correct	77 ms	78520 KB	Output is correct
18	Correct	68 ms	78672 KB	Output is correct
19	Correct	76 ms	78648 KB	Output is correct
20	Correct	79 ms	78584 KB	Output is correct
21	Correct	67 ms	78712 KB	Output is correct
22	Correct	67 ms	78588 KB	Output is correct
23	Correct	68 ms	78544 KB	Output is correct
24	Correct	67 ms	78584 KB	Output is correct
25	Correct	67 ms	78576 KB	Output is correct
26	Correct	68 ms	78584 KB	Output is correct
27	Correct	68 ms	78660 KB	Output is correct
28	Correct	68 ms	78584 KB	Output is correct
29	Correct	69 ms	78600 KB	Output is correct
30	Correct	68 ms	78584 KB	Output is correct
31	Correct	73 ms	78532 KB	Output is correct
32	Correct	80 ms	78584 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	78584 KB	Output is correct
2	Correct	67 ms	78584 KB	Output is correct
3	Correct	67 ms	78584 KB	Output is correct
4	Correct	66 ms	78552 KB	Output is correct
5	Correct	66 ms	78584 KB	Output is correct
6	Correct	66 ms	78584 KB	Output is correct
7	Correct	67 ms	78652 KB	Output is correct
8	Correct	68 ms	78612 KB	Output is correct
9	Correct	68 ms	78556 KB	Output is correct
10	Correct	70 ms	78600 KB	Output is correct
11	Correct	69 ms	78584 KB	Output is correct
12	Correct	68 ms	78584 KB	Output is correct
13	Correct	68 ms	78656 KB	Output is correct
14	Correct	72 ms	78696 KB	Output is correct
15	Correct	66 ms	78584 KB	Output is correct
16	Correct	67 ms	78584 KB	Output is correct
17	Correct	77 ms	78520 KB	Output is correct
18	Correct	68 ms	78672 KB	Output is correct
19	Correct	76 ms	78648 KB	Output is correct
20	Correct	79 ms	78584 KB	Output is correct
21	Correct	67 ms	78712 KB	Output is correct
22	Correct	67 ms	78588 KB	Output is correct
23	Correct	68 ms	78544 KB	Output is correct
24	Correct	67 ms	78584 KB	Output is correct
25	Correct	67 ms	78576 KB	Output is correct
26	Correct	68 ms	78584 KB	Output is correct
27	Correct	68 ms	78660 KB	Output is correct
28	Correct	68 ms	78584 KB	Output is correct
29	Correct	69 ms	78600 KB	Output is correct
30	Correct	68 ms	78584 KB	Output is correct
31	Correct	73 ms	78532 KB	Output is correct
32	Correct	80 ms	78584 KB	Output is correct
33	Execution timed out	2052 ms	92120 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	78584 KB	Output is correct
2	Correct	67 ms	78584 KB	Output is correct
3	Correct	67 ms	78584 KB	Output is correct
4	Correct	66 ms	78552 KB	Output is correct
5	Correct	66 ms	78584 KB	Output is correct
6	Correct	66 ms	78584 KB	Output is correct
7	Correct	67 ms	78652 KB	Output is correct
8	Correct	68 ms	78612 KB	Output is correct
9	Correct	68 ms	78556 KB	Output is correct
10	Correct	70 ms	78600 KB	Output is correct
11	Correct	69 ms	78584 KB	Output is correct
12	Correct	68 ms	78584 KB	Output is correct
13	Correct	68 ms	78656 KB	Output is correct
14	Correct	72 ms	78696 KB	Output is correct
15	Correct	66 ms	78584 KB	Output is correct
16	Correct	67 ms	78584 KB	Output is correct
17	Correct	77 ms	78520 KB	Output is correct
18	Correct	68 ms	78672 KB	Output is correct
19	Correct	76 ms	78648 KB	Output is correct
20	Correct	79 ms	78584 KB	Output is correct
21	Correct	67 ms	78712 KB	Output is correct
22	Correct	67 ms	78588 KB	Output is correct
23	Correct	68 ms	78544 KB	Output is correct
24	Correct	67 ms	78584 KB	Output is correct
25	Correct	67 ms	78576 KB	Output is correct
26	Correct	68 ms	78584 KB	Output is correct
27	Correct	68 ms	78660 KB	Output is correct
28	Correct	68 ms	78584 KB	Output is correct
29	Correct	69 ms	78600 KB	Output is correct
30	Correct	68 ms	78584 KB	Output is correct
31	Correct	73 ms	78532 KB	Output is correct
32	Correct	80 ms	78584 KB	Output is correct
33	Execution timed out	2052 ms	92120 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-