Submission #97488

#	Time	Username	Problem	Language	Result	Execution time	Memory
97488		wilwxk	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	806 ms	372420 KiB

boxes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=1e7+5;
ll mod[MAXN];
ll pre[MAXN], pos[MAXN];

ll delivery(int n, int k, int x, int v[]) {
    // if(n>1000001) return -1;
    for(int i=0; i<n; i++) {
        ll val=v[i]; val*=2; val=min(val, (ll) x);
        int ind=i%k;
        if(ind<0) return -1;
        mod[ind]+=val;
        pre[i]=mod[ind];
    }
    memset(mod, 0, sizeof(mod));
    for(int i=n-1; i>=0; i--) {
        ll val=x-v[i]; val*=2; val=min(val, (ll) x);
        int ind=i%k;
        if(ind<0) return -1;
        mod[ind]+=val;
        pos[i]=mod[ind];
    }
    ll resp=x; resp*=n;
    for(int i=0; i<n; i++) resp=min(resp, pre[i]+pos[i+1]);
    resp=min(resp, pos[0]);
    return resp;
}

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