Submission #802333

#	Time	Username	Problem	Language	Result	Execution time	Memory
802333		Liudas	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	483 ms	195988 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
vector<long long> get_cost(int N, int K, int L, int pos[]){
    vector<long long> arr(N, 0);
    for(int i = 0; i < N; i ++){
        arr[i] += pos[i];
        if(i >= K)arr[i] += arr[i-K] + pos[i-K];
    }
    return arr;
}
long long delivery(int N, int K, int L, int pos[]){
    int z = count(pos, pos+N, 0);
    N-=z;
    for(int i = 0; i < N; i++){
        pos[i] = pos[i+z];
    }
    vector<long long> l, r;
    l = get_cost(N, K, L, pos);
    reverse(pos, pos + N);
    for(int i = 0; i < N; i ++){
        pos[i] = (pos[i] ? L - pos[i] : pos[i]);
    }
    r = get_cost(N, K, L, pos);
    long long ans = min({l.back()+pos[0], l.back()+L-pos[0], r.back()+pos[N-1], r.back()-pos[N-1]+L});
    reverse(pos, pos + N);
    reverse(r.begin(), r.end());
    for(int i = 0; i < N - 1; i ++){
        ans = min(ans, l[i]+r[i+1]+min(L-pos[i],pos[i])+min(L-pos[i+1], pos[i+1]));
    }
    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'std::vector<long long int> get_cost(int, int, int, int*)':
boxes.cpp:4:46: warning: unused parameter 'L' [-Wunused-parameter]
    4 | vector<long long> get_cost(int N, int K, int L, int pos[]){
      |                                          ~~~~^
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:13:18: warning: conversion from 'std::iterator_traits<int*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   13 |     int z = count(pos, pos+N, 0);
      |             ~~~~~^~~~~~~~~~~~~~~

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