Submission #1061595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061595		anango	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	703 ms	323556 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

int INF = 1LL<<62;

int getdist(int L, int l, int r) {
    //go from sections l to r, with L
    if (r<l) swap(l,r);
    return min(min(2*r,(L-l)*2),L);
}

long long delivery(signed N, signed K, signed L, signed p[]) {
    int k = K; int n = N;
    int l = L;
    vector<int> vals(N);
    for (int i=0; i<N; i++) {
        vals[i] = p[i];
    }
    sort(vals.begin(), vals.end());
    int rem = N%K;
    vector<int> pref(n+1,INF);
    vector<int> suff(n+1,INF);
    int co = INF;
    pref[0] = 0;
    for (int i=1; i<=n; i++) {
        if (i<K) {
            pref[i] = min(l,2*vals[i-1]);
        }
        else {
            pref[i] = pref[i-K]+min(l,2*vals[i-1]);
        }
    }
    suff[n] = 0;
    for (int i=n-1; i>=0; i--) {
        if (n-i<K) {
            suff[i] = min(l,2*(l-vals[i]));
        }
        else {
            suff[i] = suff[i+K]+min(l,2*(l-vals[i]));
        }
    }
    for (int i=0; i<=n; i++) {
        co=min(co,pref[i]+suff[i]);
    }
    //cout << co1 <<" " << co2 << " " << rem << " " << N <<" " << K << " " << L << endl;
    return co;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:15:9: warning: unused variable 'k' [-Wunused-variable]
   15 |     int k = K; int n = N;
      |         ^
boxes.cpp:22:9: warning: unused variable 'rem' [-Wunused-variable]
   22 |     int rem = N%K;
      |         ^~~

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