oj.uz

Submission #198886

# Submission time Handle Problem Language Result Execution time Memory
198886 2020-01-28T01:58:10 Z Sakamotoo Boxes with souvenirs (IOI15_boxes) C++14
50 / 100
 61 ms 19832 KB 
#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;

long long delivery(int n, int k, int l, int p[]) {
	long long dp1[n+1],dp2[n+1];
    long long jaw=1e18;
    dp1[0]=0;
    dp2[0]=0;
   // sort(p,p+n);
    for(int i=0; i<n; i++){
    	int x=i-k+1;
		int y=n-i-1;
    	if(x<0){
    		int y=n-i-1;
    		dp1[i+1]=p[i]+min(p[i],l-p[i]);
    		dp2[i+1]=l-p[y]+min(p[y],l-p[y]);
		}else {
			dp1[i+1]=dp1[x]+p[i]+min(p[i],l-p[i]);
			dp2[i+1]=dp2[x]+l-p[y]+min(p[y],l-p[y]);
		}
		//cout<<dp1[i+1]<<' '<<dp2[i+1]<<endl;
	}
	long long bef=1e18;
	int cnt=0;
	for(int i=0; i<=n; i++){
		jaw=min(jaw,dp1[i]+dp2[n-i]);
		if(jaw<bef) {
			bef=jaw;
			cnt=0;
		}else {
			cnt++;
			if(cnt>1000) break;
		}
	}
	return jaw;
}

Compilation message

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:15:11: warning: declaration of 'y' shadows a previous local [-Wshadow]
       int y=n-i-1;
           ^
boxes.cpp:13:7: note: shadowed declaration is here
   int y=n-i-1;
       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 6 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 6 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 61 ms 19832 KB Output is correct
34 Incorrect 27 ms 19832 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 6 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 61 ms 19832 KB Output is correct
34 Incorrect 27 ms 19832 KB Output isn't correct
35 Halted 0 ms 0 KB -