Submission #348788

#	Time	Username	Problem	Language	Result	Execution time	Memory
348788		Sprdalo	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	703 ms	382816 KiB

boxes

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

ll delivery(int n, int k, int l, int positions[]){
    vi a;
    for (int i = 0; i < n; ++i)
        if (positions[i])
            a.push_back(positions[i]);
    n = a.size();

    vl dp(n,0);
    for (int i = 0; i < n; ++i){
        if (i < k)
            dp[i] = min(2 * a[i], l);
        else
            dp[i] = min(2 * a[i], l) + dp[i-k];
    }

    vl dpc(n, 0);
    for (int i = n - 1; i > -1; --i){
        if (i > n-k-1)
            dpc[i] = min(2*(l-a[i]), l);
        else
            dpc[i] = min(2*(l-a[i]), l) + dpc[i+k];
    }
    dpc.push_back(0);

    ll sol = min(dp[n-1], dpc[0]);
    for (int i = 0; i < n; ++i){
        sol = min(sol, dp[i] + dpc[i+1]);
    }

    for (int i = 0; i < n; ++i){
        sol = min(sol, dp[i] + l + dpc[min(n,i+k+1)]);
    }

    return sol;
}
/*
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n, k, l;
    cin >> n >> k >> l;

    int positions[n];
    for (int i = 0; i < n; ++i)
        cin >> positions[i];

    cout << delivery(n,k,l,positions) << '\n';
}*/

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:23:15: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   23 |     n = a.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