Submission #496175

#	Time	Username	Problem	Language	Result	Execution time	Memory
496175		kevin	Boxes with souvenirs (IOI15_boxes)	C++17	70 / 100	989 ms	524292 KiB

boxes

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";

ll delivery(int N, int K, int L, int* ar){
    sort(ar, ar+N);
    vector<vector<ll>> cost(N, vector<ll>(2, 0));
    for(int i=0; i<N; i++){
        if(i<K) {
            cost[i][0] = (ll)ar[i] + min(ar[i], L - ar[i]);
            cost[N-1-i][1] = (ll)(L - ar[N-1-i]) + min(ar[N-1-i], L - ar[N-1-i]);
        }
        else {
            cost[i][0] = (ll)ar[i] + min(ar[i], L - ar[i]) + cost[i-K][0];
            cost[N-1-i][1] = (ll)(L - ar[N-1-i]) + min(ar[N-1-i], L - ar[N-1-i]) + cost[N-1-i+K][1];
        }
    }
    ll ans = cost[0][1];
    ans = min(ans, cost[N-1][0]);
    for(int i=0; i<N-1; i++){
        ans = min(ans, cost[i][0] +  cost[i+1][1]); //- max(min(ar[i], L - ar[i]), min(ar[i+1], L - ar[i+1])));
    }
    return ans;
}

// int main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0);
//     if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
//     int N, K, L;
//     cin>>N>>K>>L;
//     vector<int> ar(N);
//     for(int i=0; i<N; i++) cin>>ar[i];
//     cout<<delivery(N, K, L, ar);
// }

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