Submission #979392

#	Time	Username	Problem	Language	Result	Execution time	Memory
979392		KasymK	Boxes with souvenirs (IOI15_boxes)	C++17	35 / 100	2 ms	600 KiB

boxes

#include "bits/stdc++.h"
#include "boxes.h"

using namespace std;

long long delivery(int n, int k, int l, int p[]){
    long long answer = 0;
    if(k == 1){
        for(int i = 0; i < n; ++i)
            answer += (min(p[i], l - p[i]) << 1LL);
        return answer;
    }
    if(k == n){
        vector<int> v, v2;
        for(int i = 0; i < n; ++i){
            if(p[i] < (l >> 1))
                v.push_back(p[i]);
            else
                v2.push_back(p[i]);
        }
        sort(v.begin(), v.end());
        sort(v2.begin(), v2.end());
        int ad = 0, ad2 = 0;
        if(v.size())
            ad = v.back();
        if(v2.size())
            ad2 = l - v2.front();
        answer = min(l*1LL, ((ad << 1LL) + (ad2 << 1LL))*1LL);
        return answer;
    }
    answer = LLONG_MAX;
    for(int mk = 0; mk < (1 << n); ++mk){
        vector<int> v, v2;
        for(int i = 0; i < n; ++i){
            if(mk >> i & 1)
                v.push_back(p[i]);
            else
                v2.push_back(l - p[i]);
        }
        long long id = 0;
        sort(v.begin(), v.end());
        sort(v2.begin(), v2.end());
        for(int i = (int)v.size() - 1; i >= 0; i -= k)
            id += (min((v[i] << 1LL), l));
        for(int i = (int)v2.size() - 1; i >= 0; i -= k)
            id += (min((v2[i] << 1LL), l));
        answer = min(answer, id);
    }
    return answer;
}

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