Submission #424023

#	Time	Username	Problem	Language	Result	Execution time	Memory
424023		InternetPerson10	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	696 ms	280500 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

vector<ll> a1, a2;
vector<ll> s1, s2;

long long delivery(int N, int K, int L, int p[]) {
    ll ans = (ll)999999999999999999;
    for(int i = 0; i < N; i++) {
        if(p[i] <= L/2) a1.push_back(p[i]);
        else a2.push_back(p[i]);
    }
    reverse(a2.begin(), a2.end());
    for(int i = 0; i < a2.size(); i++) a2[i] = L - a2[i];
    // for(int i = 0; i < a1.size(); i++) cout << a1[i] << ' ';
    // cout << '\n';
    // for(int i = 0; i < a2.size(); i++) cout << a2[i] << ' ';
    // cout << '\n';
    s1.resize(a1.size()+1);
    s2.resize(a2.size()+1);
    s1[0] = s2[0] = 0;
    for(int i = 1; i <= a1.size(); i++) {
        if(i < K) s1[i] = 2*a1[i-1];
        else s1[i] = 2*a1[i-1] + s1[i-K];
        // cout << s1[i] << ' ';
    }
    // cout << '\n';
    for(int i = 1; i <= a2.size(); i++) {
        if(i < K) s2[i] = 2*a2[i-1];
        else s2[i] = 2*a2[i-1] + s2[i-K];
        // cout << s2[i] << ' ';
    }
    // cout << '\n';
    int x1 = s1.size(), x2 = s2.size();
    ans = s1[x1-1] + s2[x2-1];
    for(int i = 0; i <= K; i++) {
        int y1 = x1 - 1 - i, y2 = x2 - 1 - K + i;
        if(y1 < 0 || y1 >= x1) continue;
        if(y2 < 0 || y2 >= x2) continue;
        ans = min(ans, L + s1[y1] + s2[y2]);
    }
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0; i < a2.size(); i++) a2[i] = L - a2[i];
      |                    ~~^~~~~~~~~~~
boxes.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 1; i <= a1.size(); i++) {
      |                    ~~^~~~~~~~~~~~
boxes.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 1; i <= a2.size(); i++) {
      |                    ~~^~~~~~~~~~~~
boxes.cpp:37:21: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   37 |     int x1 = s1.size(), x2 = s2.size();
      |              ~~~~~~~^~
boxes.cpp:37:37: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   37 |     int x1 = s1.size(), x2 = s2.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