Submission #276014

#	Time	Username	Problem	Language	Result	Execution time	Memory
276014		stoyan_malinin	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	1030 ms	330076 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, vector <long long> &pref, int sz)
{
    if(sz<0) return 0;
    return pref[sz];
}

void initPref(vector <int> &v, vector <long long> &pref)
{
    pref.resize(v.size());
    for(int i = 0;i<v.size();i++)
    {
        pref[i] = min(v[i], l-v[i])*2;
        if(i-k>=0) pref[i] += pref[i-k];
    }
}

long long solve(vector <int> v1, vector <int> v2)
{
    vector <long long> pref1, pref2;
    initPref(v1, pref1);
    initPref(v2, pref2);

    long long answer = 0;
    answer = evalVector(v1, pref1, v1.size()-1) + evalVector(v2, pref2, v2.size()-1);

    for(int rem = 1;rem<=min(k, int(v2.size()));rem++)
    {
        answer = min(answer, l + evalVector(v1, pref1, v1.size()-1-(k-rem)) + evalVector(v2, pref2, 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 evalVector(std::vector<int>&, std::vector<long long int>&, int)':
boxes.cpp:12:36: warning: unused parameter 'v' [-Wunused-parameter]
   12 | long long evalVector(vector <int> &v, vector <long long> &pref, int sz)
      |                      ~~~~~~~~~~~~~~^
boxes.cpp: In function 'void initPref(std::vector<int>&, std::vector<long long int>&)':
boxes.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0;i<v.size();i++)
      |                   ~^~~~~~~~~
boxes.cpp: In function 'long long int solve(std::vector<int>, std::vector<int>)':
boxes.cpp:35:45: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   35 |     answer = evalVector(v1, pref1, v1.size()-1) + evalVector(v2, pref2, v2.size()-1);
      |                                    ~~~~~~~~~^~
boxes.cpp:35:82: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   35 |     answer = evalVector(v1, pref1, v1.size()-1) + evalVector(v2, pref2, v2.size()-1);
      |                                                                         ~~~~~~~~~^~
boxes.cpp:39:67: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   39 |         answer = min(answer, l + evalVector(v1, pref1, v1.size()-1-(k-rem)) + evalVector(v2, pref2, v2.size()-1-rem));
      |                                                        ~~~~~~~~~~~^~~~~~~~
boxes.cpp:39:112: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   39 |         answer = min(answer, l + evalVector(v1, pref1, v1.size()-1-(k-rem)) + evalVector(v2, pref2, v2.size()-1-rem));
      |                                                                                                     ~~~~~~~~~~~^~~~

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