Submission #407341

#	Time	Username	Problem	Language	Result	Execution time	Memory
407341		MDario	Boxes with souvenirs (IOI15_boxes)	C++11	50 / 100	2084 ms	33996 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
long long delivery(int n, int K, int L, int p[]){
    vector<pair<ll, ll>> v1, v2;
    ll k=K, l=L;
    v1.push_back({0, 0});
    v2.push_back({0, 0});
    for(int i=0; i<n; i++){
        if(p[i]<=l/2)v1.push_back({p[i], 0});
    }
    for(int i=n-1; i>=0; i--){
        if(p[i]!=0){
            if(p[i]>l/2)v2.push_back({l-p[i], 0});
        }
    }
    for(int i=0; i<v1.size(); i++){
        if(i<k)v1[i].S=v1[i].F*2;
        else v1[i].S=v1[i].F*2+v1[i-k].S;
    }
    for(int i=0; i<v2.size(); i++){
        if(i<k)v2[i].S=v2[i].F*2;
        else v2[i].S=v2[i].F*2+v2[i-k].S;
    }
    ll r=v1.back().S+v2.back().S;
    for(int i=0; i<v1.size(); i++){
        for(int t=0; t<v2.size(); t++){
            r=min(r, v1[i].S+v2[t].S+((n-i-t+k-1)/k)*l);
        }
    }
    return r;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0; i<v1.size(); i++){
      |                  ~^~~~~~~~~~
boxes.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0; i<v2.size(); i++){
      |                  ~^~~~~~~~~~
boxes.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0; i<v1.size(); i++){
      |                  ~^~~~~~~~~~
boxes.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int t=0; t<v2.size(); t++){
      |                      ~^~~~~~~~~~

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