Submission #1218515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218515		LIA	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	0 ms	324 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e20;
ll n,k,l;
vll p;
vll r;
long long delivery(int N, int K, int L, int P[]) {
    n=N,k=K,l=L;
    p.resize(n);
    r.resize(n);
    loop(i,0,n) {
        p[i] = P[i];
        r[i] = l-p[i];
    }
    sort(all(p));
    sort(all(r));
    vll suml(n), sumr(n);
    {
        vb new_round(n);
        ll in  = 0, rounds = 0, mx = 0;
        loopr(i,n,0) {
            in++;
            ll pos = p[i];
            if (rounds*k >=in ) {// do not open
                suml[i] = mx;
            }
            else {//open new
                new_round[i] = 1;
                suml[i] = pos + min(pos, l-pos);
                mx = suml[i];
                rounds++;
            }
        }
        ll sum  = 0;
        loop(i,0,n) {
            suml[i]+=sum;
            if (new_round[i]) {
                sum+=suml[i];
            }
        }
    }

    {
        vb new_round(n);
        ll in  = 0, rounds = 0, mx = 0;
        loopr(i,n,0) {
            in++;
            ll pos = r[i];
            if (rounds*k >=in ) {// do not open
                sumr[i] = mx;
            }
            else {//open new
                new_round[i] = 1;
                sumr[i] = l-pos + min(pos, l-pos);
                mx = sumr[i];
                rounds++;
            }
        }
        ll sum  = 0;
        loop(i,0,n) {
            sumr[i]+=sum;
            if (new_round[i]) {
                sum+=sumr[i];
            }
        }
    }


    ll ans = inf;
    reverse(all(sumr));
    suml.push_back(0);
    sumr.push_back(0);
    loop(i,0,n) {
        ans = min(ans,suml[i] + sumr[(i+1)]);
    }
    ans = min(ans, sumr[0]);
    return ans;
}

Compilation message (stderr)

boxes.cpp:17:16: warning: overflow in conversion from 'double' to 'll' {aka 'long long int'} changes value from '1.0e+20' to '9223372036854775807' [-Woverflow]
   17 | const ll inf = 1e20;
      |                ^~~~

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