Submission #548904

#	Time	Username	Problem	Language	Result	Execution time	Memory
548904		perchuts	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	589 ms	293796 KiB

boxes

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e7+10;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

ll R[maxn], L[maxn];

ll delivery(int n, int k, int l, int p[]){
    ll cur = 0;
    int y = 0;
    for(int i=0;i<n;++i)if(p[i]!=0)++y;
    for(int i=0;i<y;++i)p[i] = p[n-y+i];
    n = y;
    for(int i=n-1;~i;--i){
        if(i>=n-k)R[i] = min(ll(l), ll(2*(l-p[i])));
        else R[i] = min(ll(l), ll(2*(l-p[i]))) + R[i+k];
    }

    for(int i=0;i<n;++i){
        if(i<k)L[i] = min(ll(l), ll(2*p[i]));
        else L[i] = min(ll(l), ll(2*p[i])) + L[i-k];
    }

    ll resp = min(R[0], L[n-1]);
    
    for(int i=1;i<n;++i)ckmin(resp, R[i] + L[i-1]);

    return resp;
}
// int positions[maxn];
// int main(){
//     int n,k,l;cin>>n>>k>>l;
//     for(int i=0;i<n;++i)cin>>positions[i];
//     cout<<delivery(n,k,l,positions)<<endl;
// }

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:25:8: warning: unused variable 'cur' [-Wunused-variable]
   25 |     ll cur = 0;
      |        ^~~

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