Submission #852686

#	Time	Username	Problem	Language	Result	Execution time	Memory
852686		ntkphong	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	681 ms	333140 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
 
const long long INF = 1e18;
 
long long delivery(int N, int K, int L, int p[]) {
    
    vector<int> positions(N);
    for(int i = 0; i < N; i ++) positions[i] = p[i]; 
    
    sort(positions.begin(), positions.end());
    
    /*for(int i = 0; i < N; i ++) {
        if(positions[i] == 0) {
            K -- ;
            positions.erase(positions.begin());
        }
    }*/
    
    vector<long long> f(N);
    vector<long long> s(N);
    
    for(int i = 0, j = 0; i < N; i ++) {
        j = max(j, i - K + 1);
        f[i] = (j == 0 ? 0 : f[j - 1]) + positions[i] * 2;
    }
    
    for(int i = N - 1, j = N - 1; i >= 0; i --) {
        j = min(j, i + K - 1);
        s[i] = (j == N - 1 ? 0 : s[j + 1]) + (L - positions[i]) * 2;
    }
    
    long long ans = INF;
    
    for(int i = 0; i < N; i ++) {
        ans = min(ans, (i > 0 ? f[i - 1] : 0) + (i < N ? s[i] : 0));
        ans = min(ans, (i >= 0 ? f[i] : 0) + (i + 1 < N ? s[i + 1] : 0));
        
        //cout << i << " " << (i > 0 ? f[i - 1] : 0) + (i < N ? s[i] : 0) << "\n";
        //cout << i << " " << (i >= 0 ? f[i] : 0) + (i + 1 < N ? s[i + 1] : 0) << "\n";
    }
    
    for(int i = 0, j = 0; i < N; i ++) {
        j = max(j, i - K + 1);
        ans = min(ans, (j > 0 ? f[j - 1] : 0) + (i + 1 < N ? s[i + 1] : 0) + L);
    }
    
    return ans;
}
 
/*int main() {
    int N, K, L;
    cin >> N >> K >> L;
    
    int p[N];
    for(int i = 0; i < N; i ++) cin >> p[i];
    
    cout << delivery(N, K, L, p) << "\n";
    return 0;
}*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30