Submission #1275952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275952		quanduongxuan12	Boxes with souvenirs (IOI15_boxes)	C++20	0 / 100	1 ms	652 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define name "boxes"
#define MAXN 10000007
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
    u+=v;
    if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
    u-=v;
    if (u<0) u+=MOD;
}
void minimize(int &u, int v){
    u=min(u,v);
}
void maximize(int &u, int v){
    u=max(u,v);
}
long long Rand(long long l, long long r){
    ll tmp=0;
    FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
    return l+tmp%(r-l+1);
}
ll delivery(int n, int k, int L, int positions[]){
    int mid=-1;
    FOR(i,0,n-1){
        if (positions[i]<=L/2){
            mid=i;
        }
    }
    int l=0,r=0;
    int u=n-1,v=n-1;
    while (l<=n-1&&positions[l]==0) ++l;
    r=l;
    ll ans=0;
    while (1){
        while (r<mid&&r-l+1<k){
            ++r;
        }
        while (v>mid+1&&u-v+1<k){
            --v;
        }
        if (r-l+1==k&&u-v+1==k){
            if (positions[r]*2<=(L-positions[v])*2){
                ans+=1LL*positions[r]*2;
                l=++r;
            }
            else{
                ans+=1LL*(L-positions[v])*2;
                u=--v;
            }
        }
        else if (r-l+1==k){
            ans+=1LL*positions[r]*2;
            l=++r;
        }
        else if (u-v+1==k){
            ans+=1LL*(L-positions[v])*2;
            u=--v;
        }
        else{
            break;
        }
    }
    if (r>mid&&v==mid) return ans;
    if (r>mid){
        return ans+1LL*(L-positions[r])*2;
    }
    else if (v==mid){
        return ans+1LL*positions[v]*2;
    }
    int kq=2*INF;
    if (r<=mid){
        int _l=l,_r=r;
        while (r-l+1<k&&r<u) ++r;
        if (r-l+1<k){
            minimize(kq,L);
        }
        else{
            if (r==u) minimize(kq,L);
            else minimize(kq,L+(L-positions[r+1])*2);
        }
        l=_l,r=_r;
    }
    if (v>mid){
        int _u=u,_v=v;
        while (u-v+1<k&&v>r) --v;
        if (u-v+1<k) minimize(kq,L);
        else{
            if (v==r) minimize(kq,L);
            else minimize(kq,L+positions[v-1]*2);
        }
        u=_u,v=_v;
    }
    return ans+1LL*kq;
}

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