Submission #1120789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120789		SalihSahin	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1 ms	504 KiB

boxes

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "boxes.h"

const long long inf = 1e17;

long long delivery(int N, int K, int L, int p[]) {
    vector<int> pos;
    for(int i = 0; i < N; i++){
        if(p[i] > 0) pos.pb(p[i]);
    }
    N = pos.size();

    vector<pair<int, long long> > lop, rop; // kac kisiyi, ne kadar surede
    lop.pb({0, 0LL}), rop.pb({0, 0LL});

    int ind = N-1;
    for(int i = 1; i <= N/K; i++){
        int wh = K;
        while(wh >= 1 && ind >= 1 && pos[ind-1] >= (N + 1)/2){
            wh--;
            ind--;
        }

        int new_taken = ((N-1) - ind) - rop.back().first;
        long long op = ((N-1) - pos[ind] + 1) * 2 + rop.back().second;
        rop.pb({new_taken, op});
    }

    ind = 0;
    for(int i = 1; i <= N/K; i++){
        int wh = K;
        while(wh >= 1 && ind < N-1 && pos[ind+1] <= (N-1)/2){
            wh--;
            ind++;
        }

        int new_taken = ind - rop.back().first;
        long long op = pos[ind] * 2 + rop.back().second;
        lop.pb({new_taken, op});
    }

    long long ans = inf;
    for(int l = 0; l < lop.size(); l++){
        for(int r = 0; r < rop.size(); r++){
            int rem = N - lop[l].first - rop[r].first;
            long long calc = lop[l].second + rop[r].second + ((rem + K - 1)/K) * L;
            ans = min(ans, calc);
        }
    }

    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:13:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   13 |     N = pos.size();
      |         ~~~~~~~~^~
boxes.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int l = 0; l < lop.size(); l++){
      |                    ~~^~~~~~~~~~~~
boxes.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int r = 0; r < rop.size(); r++){
      |                        ~~^~~~~~~~~~~~

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