Submission #1080607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080607		anonymous321	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	360 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = numeric_limits<ll>::max()/4;

ll delivery(int n, int k, int l, int apos []) {
    vector<int> pos (apos, apos + n);
    vector<ll> minl (n+2, INF); // excl
    minl[0] = 0;
    for (int i = 0; i < n; i++) {
        minl[i+1] = minl[(i/k) * k] + pos[i]*2;
    }
    
    vector<ll> minlm (n+2, INF);
    minlm[0] = 0;
    int id = 0;
    for (int i = 0; i < n; i++) {
        for (int j = id; j < n; j++) { // incl. for minl
            ll x = minl[j+1] + ceil((i - j)/ (double) k) * l;
            if (x <= minlm[i+1]) {
                minlm[i+1] = x;
                id = j;
            } else {
                break;
            }
        }
    }
    
    vector<ll> minr (n+1, INF); // incl
    minr[n] = 0;
    for (int i = n-1; i >= 0; i--) {
        minr[i] = minr[ceil(i/(double) k) * k] + (l - pos[i]) * 2;
    }
    
    ll sol = INF;
    for (int i = 0; i < n; i++) { // incl r
        ll x = minlm[i] + minr[i+1];
        sol = min(sol, x);
    }
    
    return sol;
}

Compilation message (stderr)

boxes.cpp: In function 'll delivery(int, int, int, int*)':
boxes.cpp:20:60: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'double' may change value [-Wconversion]
   20 |             ll x = minl[j+1] + ceil((i - j)/ (double) k) * l;
      |                                                            ^
boxes.cpp:20:30: warning: conversion from 'double' to 'll' {aka 'long long int'} may change value [-Wfloat-conversion]
   20 |             ll x = minl[j+1] + ceil((i - j)/ (double) k) * l;
boxes.cpp:33:43: warning: conversion from 'double' to 'std::vector<long long int>::size_type' {aka 'long unsigned int'} may change value [-Wfloat-conversion]
   33 |         minr[i] = minr[ceil(i/(double) k) * k] + (l - pos[i]) * 2;
      |                        ~~~~~~~~~~~~~~~~~~~^~~

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