Submission #513987

#	Time	Username	Problem	Language	Result	Execution time	Memory
513987		Leo121	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	588 ms	268536 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp male_pair
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)

using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;
typedef vector<ll> vl;

long long delivery(int N, int K, int L, int p[]) {
    vl menores;
    vl mayores;
    menores.pb(0LL);
    forn(i, 0, N - 1){
        if(!p[i]){
            continue;
        }
        if(p[i] <= L / 2){
            menores.pb((ll) p[i] * 2LL);
        }
        else{
            mayores.pb(((ll) L - (ll) p[i]) * 2LL);
        }
    }
    mayores.pb(0LL);
    int lon1 = menores.size(), lon2 = mayores.size();
    forn(i, K + 1, lon1 - 1){
        menores[i] += menores[i - K];
    }
    reverse(mayores.begin(), mayores.end());
    forn(i, K + 1, lon2){
        mayores[i] += mayores[i - K];
    }
    if(lon1 == 1 && lon2 == 1){
        return 0LL;
    }
    if(lon1 == 1){
        return mayores[lon2 - 1];
    }
    if(lon2 == 1){
        return menores[lon1 - 1];
    }
    ll res = mayores[lon2 - 1] + menores[lon1 - 1];
    forn(i, 1, K - 1){
        res = min(res, menores[max(lon1 - i - 1, 0)] + mayores[max(lon2 - (K - i) - 1, 0)] + L);
    }
    return res;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:32:28: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   32 |     int lon1 = menores.size(), lon2 = mayores.size();
      |                ~~~~~~~~~~~~^~
boxes.cpp:32:51: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   32 |     int lon1 = menores.size(), lon2 = mayores.size();
      |                                       ~~~~~~~~~~~~^~

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