Submission #276011

#	Time	Username	Problem	Language	Result	Execution time	Memory
276011		stoyan_malinin	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2069 ms	29856 KiB

boxes

#include "boxes.h"
//#include "grader.cpp"

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n, k, l;

long long evalVector(vector <int> v, int sz)
{
    long long answer = 0;
    for(int i = sz;i>=0;i-=k) answer += 2*min(v[i], l-v[i]);//, cout << v[i] << '\n'

    return answer;
}

long long solve(vector <int> v1, vector <int> v2)
{
    long long answer = 0;
    answer = evalVector(v1, v1.size()-1) + evalVector(v2, v2.size()-1);

    for(int rem = 1;rem<=min(k, int(v2.size()));rem++)
    {
        answer = min(answer, l + evalVector(v1, v1.size()-1-(k-rem)) + evalVector(v2, v2.size()-1-rem));
    }

    return answer;
}

vector <int> invertVector(vector <int> v)
{
    vector <int> out;
    for(int x: v) out.push_back(l-x);

    return out;
}

long long delivery(int N, int K, int L, int p[])
{
    n = N;
    k = K;
    l = L;

    vector <int> v1, v2;
    for(int i = 0;i<n;i++)
    {
        if(p[i]==0) continue;

        if(p[i]<L-p[i]) v1.push_back(p[i]);
        else v2.push_back(p[i]);
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end(), greater <int>());

    return min(solve(v1, v2), solve(invertVector(v2), invertVector(v1)));

    //return solve(invertVector(v2), invertVector(v1));
    //return solve(v1, v2);
}

Compilation message (stderr)

boxes.cpp: In function 'long long int solve(std::vector<int>, std::vector<int>)':
boxes.cpp:23:38: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   23 |     answer = evalVector(v1, v1.size()-1) + evalVector(v2, v2.size()-1);
      |                             ~~~~~~~~~^~
boxes.cpp:23:68: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   23 |     answer = evalVector(v1, v1.size()-1) + evalVector(v2, v2.size()-1);
      |                                                           ~~~~~~~~~^~
boxes.cpp:27:60: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   27 |         answer = min(answer, l + evalVector(v1, v1.size()-1-(k-rem)) + evalVector(v2, v2.size()-1-rem));
      |                                                 ~~~~~~~~~~~^~~~~~~~
boxes.cpp:27:98: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   27 |         answer = min(answer, l + evalVector(v1, v1.size()-1-(k-rem)) + evalVector(v2, v2.size()-1-rem));
      |                                                                                       ~~~~~~~~~~~^~~~

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