Submission #1126626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126626		heavylightdecomp	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	470 ms	196180 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
using pii = pair<int,int>;
#define vt vector
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
//BUG: you went dead on your template
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
#define debug(x) {auto _x=x;cerr<<#x<<": "<<_x<<'\n';};
#define i32 signed
const int maxn = 1e7+5;
const int INF = 1e18;
int ldp[maxn], rdp[maxn];
long long delivery(i32 N, i32 K, i32 L, i32 pos[]) {
    auto ret = [&](int i) { return min(pos[i], L-pos[i]); };
    fill(ldp,ldp+maxn,INF);
    fill(rdp,rdp+maxn,INF);
    // debug("what?")
    f0r(i,0,N) {
        if(i < K) {
            ldp[i] = pos[i] + ret(i);
        } else {
            ldp[i] = ldp[i-K] + pos[i] + ret(i);
        }
    }
    r0f(i,N-1,0) {
        if(i+K < N) {
            rdp[i] = rdp[i+K] + L-pos[i] + ret(i);
        } else {
            rdp[i] = L-pos[i] + ret(i);
        }
    }
    
    int res = min(ldp[N-1], rdp[0]);
    f0r(i,0,N-1) {
        res = min(res, ldp[i] + rdp[i+1]);
    }
    return res;
}

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