Submission #572077

#	Time	Username	Problem	Language	Result	Execution time	Memory
572077		nohaxjustsoflo	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	654 ms	333040 KiB

boxes

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen(-1e9, 1e8); ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 1e6+50000;
const int mod = 1e9+7;
const int mxlogN = 34;
const int mxK = 26;
const ll inf = 1e18;
const int K = 100000;

ll delivery(int N, int K, int L, int p[])
{
    ll n=N, k=K;
    ll cnt=0;
    if(n%2==0) for(int i=0; i<n; i++) cnt+=p[i]==n/2;
    ll ans=cnt/k*n;
    cnt=cnt%k;
    vector<int> a;
    for(int i=0; i<n; i++)
    {
        if(n%2==0&&p[i]==n/2)
        {
            if(cnt)
            {
                cnt--;
                a.push_back(p[i]);
            }
        }
        else a.push_back(p[i]);
    }
    n=a.size();
    vector<ll> pre(n), suf(n);
    for(int i=0; i<n; i++)
    {
        if(i>=k) pre[i]+=pre[i-k];
        pre[i]+=a[i]*2;
        //cout << pre[i] << " ";
    }
    //cout << "\n";
    for(int i=n-1; i>=0; i--)
    {
        if(i+k<n) suf[i]+=suf[i+k];
        suf[i]+=(L-a[i])*2;
        //cout << suf[i] << " ";
    }
    //cout << "\n";
    ll ans2=1e18;
    for(int j=0; j<3; j++)
    {
        for(int i=0; i+j*K<=n; i++)
        {
            //pre[i-1]+suf[i];
            ans2=min(ans2,L*j+(i?pre[i-1]:0)+(i+j*K<n?suf[i+j*K]:0));
        }
    }
    return ans+ans2;
}

/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,k,l; cin >> n >> k >> l;
    int p[n];
    for(int i=0; i<n; i++) cin >> p[i];
    cout << delivery(n,k,l,p) << "\n";

}*/
/*
3 2 8
1 2 5
*/

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:21:24: warning: declaration of 'K' shadows a global declaration [-Wshadow]
   21 | ll delivery(int N, int K, int L, int p[])
      |                    ~~~~^
boxes.cpp:19:11: note: shadowed declaration is here
   19 | const int K = 100000;
      |           ^
boxes.cpp:50:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     for(int i=n-1; i>=0; i--)
      |               ~^~

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