Submission #548846

#	Time	Username	Problem	Language	Result	Execution time	Memory
548846		perchuts	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	1 ms	324 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 = 1e5+100;

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 delivery(int n, int k, int l, int p[]){
    //comecar tudo r => O(N)
    //transicao de x pra x+1 => O(1)
    //comecar tudo l => O(N)
    //complexidade total: O(3N)    
    ll cur = 0;
    int fi = (n-1)%k;
    for(int i=n-k;i>=0;i-=k){
        cur += ll(l - p[i]);
        cur += ll(min(l - p[i], p[i]));
    }
    if(n%k!=0)cur += ll(l - p[0]) + ll(min(l - p[0], p[0]));
    ll resp = cur;
    for(int i=0;i<n-1;++i){//esq até i, dir resto
        //tratando r
        cur -= ll(l - p[i]);
        cur -= ll(min(l - p[i], p[i]));
        if(i%k!=fi){//tenho que adicionar o proximo
            cur += ll(l - p[i+1]);
            cur += ll(min(l - p[i+1], p[i+1]));
        }
        //tratando l
        if(i%k==0)cur += ll(p[i]) + ll(min(l - p[i], p[i]));
        else{
            cur -= ll(min(l - p[i-1],p[i-1]));
            cur += ll(p[i]-p[i-1]) + ll(min(l-p[i],p[i]));
        }
        // cout<<cur<<" ";
        ckmin(resp,cur);
    }
    cur = 0;
    for(int i=k-1;i<n;i+=k){
        cur += ll(p[i]);
        cur += ll(min(l - p[i], p[i]));
    }
    if(n%k!=0)cur += ll(p[n-1]) + ll(min(l - p[n-1], p[n-1]));
    ckmin(resp,cur);
    // cout<<cur<<endl;
    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