Submission #548894

#	Time	Username	Problem	Language	Result	Execution time	Memory
548894		perchuts	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	1 ms	340 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[]){
    int fi = (n-1)%k;
    ll cur = 0;
    for(int i=n-1;~i;--i){
        if(i%k==fi){
            cur += ll(2*(l - p[i])); 
        }else{
            cur -= ll(l - p[i+1]);
            cur += ll(p[i+1]-p[i]);
            cur += ll(l - p[i]);
        }
        R[n-i] = cur;
    }
    cur = 0;
    for(int i=0;i<n;++i){
        if(i%k==0){
            cur += ll(2*p[i]);
        }else{
            cur -= ll(p[i-1]);
            cur += ll(p[i]-p[i-1]);
            cur += ll(p[i]);
        }
        L[i+1] = cur;
    }
    ll resp = R[n];
    for(int i=0;i<n;++i){
        ckmin(resp, R[i] + L[n-i]);
    }
    for(int i=0;i<=n-k;++i){
        ckmin(resp, R[i] + L[n-k-i] + ll(l));
    }
    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;
// }

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