Submission #308257

#	Time	Username	Problem	Language	Result	Execution time	Memory
308257		amunduzbaev	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	1192 ms	196704 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
//#include "grader.cpp"
#define ll long long
using namespace std;
ll pref[10000001], suf[10000001];
ll delivery(int N, int K, int L, int p[]) {

    ll k=K,l=L,n=N;
    vector <ll> a,b;
    sort(p, p+n);
    for(int  i=0;i<n;i++){
        if(p[i] <= l/2)
            a.push_back(p[i]);
        else
            b.push_back(L-p[i]);
    }
    sort(b.begin(), b.end());
    ll res = 0;

    for(long long  i = 0 ; i < a.size();i++){
        pref[i] = (i<k ? a[i]*2 : a[i]*2+pref[i-k]);
    }
    for(int  i = 0 ; i < b.size();i++){
        suf[i] = (i<k ? b[i]*2:b[i] * 2 + suf[i-k]);
    }

    if( a.size()==0)     res = suf[b.size()-1];
    else if(b.size()==0) res = pref[a.size()-1];
    else                 res = pref[a.size()-1]+suf[b.size()-1];

    long long t = 0;
    for(long long i  = a.size() - 2, j= 1; j <= k && i>=0 ; j++,i--){

        if(b.size()>=k-j) t = suf[b.size()-(k-j)-1];
        else              t = 0;

        res = min (res, pref[i]+l+t);
    }
    if(k==n)
        res = min (res, l);
    return res;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:21:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(long long  i = 0 ; i < a.size();i++){
      |                            ~~^~~~~~~~~~
boxes.cpp:24:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int  i = 0 ; i < b.size();i++){
      |                      ~~^~~~~~~~~~
boxes.cpp:35:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |         if(b.size()>=k-j) t = suf[b.size()-(k-j)-1];
      |            ~~~~~~~~^~~~~

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