Submission #1264682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264682		InvMOD	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	405 ms	274512 KiB

boxes

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define pi pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())

template<class T> using upq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());}
template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());}

#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define sumof(x) accumulate(all(x), 0ll)
#define dbg(x) "[" << #x " = " << (x) << "]"
#define el "\n"

using ll = long long;
using ld = long double;

template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);}
template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);}


ll delivery(int n, int k, int L, int a[]){

    vector<ll> pos(n + 1);
    FOR(i, 1, n){
        pos[i] = a[i - 1];
    }

    vector<ll> pre(n + 1), suf(n + 2);
    FOR(i, 1, n){
        pre[i] = pre[max(0, i - k)] + pos[i] * 2;
    }

    ROF(i, n, 1){
        suf[i] = suf[min(n + 1, i + k)] + (L - pos[i]) * 2;
    }

    ll ans = 1e18;
    FOR(i, 0, n){
        ckmn(ans, pre[i] + suf[i + 1]);
        if(i> 0 && i + k <= n + 1){
            ckmn(ans, pre[i - 1] + suf[i + k] + L);
        }
    }

    return ans;
}

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