Submission #404752

#	Time	Username	Problem	Language	Result	Execution time	Memory
404752		Dakto	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	693 ms	342904 KiB

boxes

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


long long delivery(int n, int k, int l, int V[]){
    vector<long long> v(V, V+n);
    v.erase(v.begin(),lower_bound(v.begin(),v.end(),1));
    n=v.size();
    if(n==0) return 0;
    vector<long long> ps, ps2(n);
    long long c=0;
    for(long long i=0; i<n; i++){
        ps.push_back(min(2*v[i], (long long)l)+(i>=k?ps[i-k]:0));
        if((i+1)%k==0){
            c+=min(2*v[i],(long long)l);
        }
    }

    c=0;
    long long j=0;
    for(long long i=n-1; i>=0; i--,j++){
        ps2[i]=min(2*(l-v[i]), (long long)l)+(i+k<n?ps2[i+k]:0);
        if((j+1)%k==0){
            c+=min(2*(l-v[i]),(long long)l);
        }
    }

    long long res=min(ps[n-1],ps2[0]);
    for(long long i=0; i<n-1; i++) res=min(res,ps[i]+ps2[i+1]);
    for(long long i=0; i<n-k-1; i++) res=min(res,ps[i]+ps2[i+k+1]+l);
    return res;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:8:13: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
    8 |     n=v.size();
      |       ~~~~~~^~

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