Submission #619090

#	Time	Username	Problem	Language	Result	Execution time	Memory
619090		Hazem	Boxes with souvenirs (IOI15_boxes)	C++14	20 / 100	1 ms	340 KiB

boxes

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const LL LINF = 1e18;

LL a[100010];
vector<LL>vec[2];
LL n,k,L1;

LL solve1(){

    vec[0].clear();
    vec[1].clear();

    for(int i=1;i<=n;i++){
        if(a[i]<=L1/2)
            vec[0].push_back(a[i]);
        else 
            vec[1].push_back(a[i]);
    }

    reverse(vec[1].begin(),vec[1].end());
    LL ans = 0;
    while(vec[0].size()>=k){
        ans += vec[0][vec[0].size()-k]*2;
        for(int i=0;i<k;i++)
            vec[0].pop_back();
    }

    while(vec[1].size()>=k){
        ans += (L1-vec[1].back())*2;
        for(int i=0;i<k;i++)
            vec[1].pop_back();
    }

    for(int i=0;i<vec[1].size();i++)
        vec[0].push_back(vec[1][i]);

    sort(vec[0].begin(),vec[0].end());
    LL ans1 = LINF;
    if(vec[0].empty())
        ans1 = 0;

    for(int i=0;i<=min(k,(LL)vec[0].size());i++){
        if(vec[0].size()-i>k)
            continue;
        
        ans1 = min(ans1,min(L1,i?vec[0][i-1]*2:0)+min(L1,i!=vec[0].size()?(L1-vec[0][i])*2:0));
    }

    return ans1+ans;
}

LL solve2(){

    vec[0].clear();
    vec[1].clear();
    
    for(int i=1;i<=n;i++){
        if(a[i]<=L1/2)
            vec[0].push_back(a[i]);
        else 
            vec[1].push_back(a[i]);
    }
 
    reverse(vec[0].begin(),vec[0].end());
    LL ans = 0;
    while(vec[0].size()>=k){
        ans += vec[0][vec[0].size()-k]*2;
        for(int i=0;i<k;i++)
            vec[0].pop_back();
    }
 
    while(vec[1].size()>=k){
        ans += (L1-vec[1][vec[1].size()-k])*2;
        for(int i=0;i<k;i++)
            vec[1].pop_back();
    }
 
    reverse(vec[0].begin(),vec[0].end());
    for(int i=0;i<vec[1].size();i++)
        vec[0].push_back(vec[1][i]);
 
    LL ans1 = LINF;
    for(int i=0;i<=min(k,(LL)vec[0].size());i++){
        if(vec[0].size()-i>k)
            continue;
        
        ans1 = min(ans1,min(L1,i?vec[0][i-1]*2:0)+min(L1,i!=vec[0].size()?(L1-vec[0][i])*2:0));
    }
 
    return ans+ans1;


}

long long delivery(int N, int K, int L, int p[]) {
    
    n = N,k = K;    
    L1 = L;
    for(int i=1;i<=n;i++)
        a[i] = p[i-1];

    sort(a+1,a+n+1);
    
    return min(solve1(),solve2());
}

Compilation message (stderr)

boxes.cpp: In function 'long long int solve1()':
boxes.cpp:26:24: 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]
   26 |     while(vec[0].size()>=k){
      |           ~~~~~~~~~~~~~^~~
boxes.cpp:32:24: 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]
   32 |     while(vec[1].size()>=k){
      |           ~~~~~~~~~~~~~^~~
boxes.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=0;i<vec[1].size();i++)
      |                 ~^~~~~~~~~~~~~~
boxes.cpp:47:27: 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]
   47 |         if(vec[0].size()-i>k)
      |            ~~~~~~~~~~~~~~~^~
boxes.cpp:50:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         ans1 = min(ans1,min(L1,i?vec[0][i-1]*2:0)+min(L1,i!=vec[0].size()?(L1-vec[0][i])*2:0));
      |                                                          ~^~~~~~~~~~~~~~~
boxes.cpp: In function 'long long int solve2()':
boxes.cpp:70:24: 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]
   70 |     while(vec[0].size()>=k){
      |           ~~~~~~~~~~~~~^~~
boxes.cpp:76:24: 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]
   76 |     while(vec[1].size()>=k){
      |           ~~~~~~~~~~~~~^~~
boxes.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<vec[1].size();i++)
      |                 ~^~~~~~~~~~~~~~
boxes.cpp:88:27: 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]
   88 |         if(vec[0].size()-i>k)
      |            ~~~~~~~~~~~~~~~^~
boxes.cpp:91:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         ans1 = min(ans1,min(L1,i?vec[0][i-1]*2:0)+min(L1,i!=vec[0].size()?(L1-vec[0][i])*2:0));
      |                                                          ~^~~~~~~~~~~~~~~

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