Submission #1120828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120828		SalihSahin	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	1 ms	592 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;
    for(int i = 1; i <= N/K; i++){
        int wh = K;
        while(wh >= 1 && ind >= 1 && pos[ind-1] >= (L+1)/2){
            wh--;
            ind--;
        }

        if(ind == N) break;

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

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

        //int new_taken = ind - lop.back().first;
        if(ind < 0) break;

        long long op = pos[ind] * 2 + lop.back().second;
        if(lop.back().first == ind + 1) break;
        lop.pb({ind + 1, 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;
            //cout<<"l = "<<lop[l].first<<" "<<lop[l].second<<" r = "<<rop[r].first<<" "<<rop[r].second<<" calc = "<<calc<<endl;
            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:28:13: warning: unused variable 'new_taken' [-Wunused-variable]
   28 |         int new_taken = rop.back().first - ind;
      |             ^~~~~~~~~
boxes.cpp:51: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]
   51 |     for(int l = 0; l < lop.size(); l++){
      |                    ~~^~~~~~~~~~~~
boxes.cpp:52: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]
   52 |         for(int r = 0; r < rop.size(); r++){
      |                        ~~^~~~~~~~~~~~

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