제출 #1312658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312658		Math4Life2020	Boxes with souvenirs (IOI15_boxes)	C++20	0 / 100	0 ms	332 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;

vector<ll> p;
vector<vector<ll>> pf;
ll N,K,L;

pii sfw(ll x) { //{sum forward starting at this index, # of such vertices}
    if (x>=N) {
        return {0LL,0LL};
    }
    ll r = x%K;
    ll bind = x/K;
    return {(pf[r].back()-pf[r][bind]),pf[r].size()-bind};
}

pii sbk(ll x) {
    if (x<0) {
        return {0LL,0LL};
    }
    ll r = x%K;
    ll find = x/K+1;
    return {(pf[r][find]),find};
}

long long delivery(int _N, int _K, int _L, int _p[]) {
    for (ll x=0;x<_N;x++) {
        p.push_back(_p[x]);
    }
    N = _N; K = _K; L = _L;
    K = min(K,N);
    sort(p.begin(),p.end());
    pf = vector<vector<ll>>(K,vector<ll>(1,0));
    for (ll x=0;x<N;x++) {
        pf[x%K].push_back((pf[x%K].back())+p[x]);
    }
    ll ans = INF;
    for (ll t=0;t<=N;t++) {
        ll cval = 0;
        cval += 2*sbk(t-1).first;
        cval += (2*sfw(t).second*L-2*sfw(t).first);
        ans = min(ans,cval);
    }
    for (ll t=0;t<=(N-K);t++) {
        ll cval = L;
        cval += 2*sbk(t-1).first;
        cval += (2*sfw(t+K).second*L-2*sfw(t+K).first);
        ans = min(ans,cval);
    }
    return ans;
}

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