oj.uz

Submission #60692

# Submission time Handle Problem Language Result Execution time Memory
60692 2018-07-24T14:22:04 Z istlemin Boxes with souvenirs (IOI15_boxes) C++14
50 / 100
 2000 ms 20080 KB 
#include "boxes.h"
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll ceilDiv(ll a,ll b){
    return a/b+(a%b!=0);
}

long long delivery(int N, int K, int L, int p[]) {
	ll n = N;
	ll k = K;
	ll l = L;
    vi left;
    vi right;
	rep(i,0,n){
        if(p[i]<=l/2) left.push_back(p[i]);
        else right.push_back(l-p[i]);
	}
	sort(all(left));
	sort(all(right));

    vi costLeft(left.size()+1);
    rep(i,0,left.size()){
        if(i<k) costLeft[i+1] = left[i]*2;
        else costLeft[i+1] = left[i]*2 + costLeft[i-k+1];
    }
    vi costRight(right.size()+1);
    rep(i,0,right.size()){
        if(i<k) costRight[i+1] = right[i]*2;
        else costRight[i+1] = right[i]*2 + costRight[i-k+1];
    }

    ll best = 1e18;

    rep(i,0,costLeft.size()){
		rep(j,0,costRight.size()){
			ll curr = costLeft[i]+costRight[j];
            curr += ceilDiv(n-i-j,k)*l;
            best = min(best,curr);
		}
    }
	//cout<<best<<endl;
    return best;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 4 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 252 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 4 ms 376 KB Output is correct
25 Correct 4 ms 380 KB Output is correct
26 Correct 2 ms 252 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 4 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Execution timed out 2037 ms 20080 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 4 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 252 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 4 ms 376 KB Output is correct
25 Correct 4 ms 380 KB Output is correct
26 Correct 2 ms 252 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 4 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Execution timed out 2037 ms 20080 KB Time limit exceeded
34 Halted 0 ms 0 KB -