Submission #176098

#	Time	Username	Problem	Language	Result	Execution time	Memory
176098		mat_v	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	2 ms	376 KiB

boxes

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#include "boxes.h"
#define maxn 10000005
using namespace std;
typedef long long ll;
int n,k;
int niz[maxn];
int d;
set<int>s;
ll dist(int l, int r){
    if(l > r)swap(l, r);
    ll res = min(r - l, l + d - r);
    return res;
}

ll levi[maxn];
ll desni[maxn];
long long delivery(int N, int K, int L, int p[]) {
    n = N, k = K, d = L;
    ff(i,1,n)niz[i] = p[i - 1];
    sort(niz + 1, niz + 1 + n);
    levi[0] = 0;
    desni[n + 1] = 0;
    ff(i,1,n){
        if(k == 1 || i%k == 1){
            levi[i] = levi[i - 1] + 2*niz[i];
        }
        else{
            levi[i] = levi[i - 1] - niz[i - 1] + niz[i] - niz[i - 1] + niz[i];
        }
    }
    fb(i,n,1){
        int kol = n - i + 1;
        if(kol%k == 1 || k == 1){
            desni[i] = desni[i + 1] + 2*(d-niz[i]);
            //cout << i << " " << desni[i] << endl;
            //exit(0);
        }
        else{
            desni[i] = desni[i + 1] - (d-niz[i + 1]) + (d-niz[i]) - (d-niz[i + 1]) + (d-niz[i]);
        }
    }
    ll res = levi[1] + desni[2];
    ff(i,1,n){
        res = min(res, levi[i] + desni[i + 1]);
    }
    ff(i,1,n){
        res = min(res, levi[i - 1] + d + desni[i + k]);
    }
    return res;
}
/*
int aa[maxn];
int N,K,L;
int main(){
    freopen("03", "r", stdin);
    cin >> N >> K >> L;
    ff(i,0,N - 1)cin >> aa[i];
    cout << delivery(N,K,L,aa);
    return 0;
}
/*
3 2 8
1 2 5
*/

Compilation message (stderr)

boxes.cpp:64:1: warning: "/*" within comment [-Wcomment]
 /*

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