Submission #146729

#	Time	Username	Problem	Language	Result	Execution time	Memory
146729		karma	Boxes with souvenirs (IOI15_boxes)	C++11	100 / 100	718 ms	293880 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define ll       long long

using namespace std;

const int N = int(1e7);

ll f[N], g[N], res, cur, n, k, last, pos;

int Irene(int x) {return last + 1 + (k - last + x - 1 + k * n) % k;}

ll delivery(int _n, int _k, int l, int p[])
{
   n = _n, k = _k, last = -1;
   for(int i = 0; i < n; ++i) {
      f[i] = 2 * p[i] + (i >= k? f[i - k]: 0);
      if(p[i] * 2 <= l) last = i;
   }
   if(last == n - 1) return f[n - 1];
   for(int i = n - 1; i >= 0; --i) g[i] = 2 * (l - p[i]) + (i + k < n? g[i + k]: 0);
   if(last == -1) return g[0];
   pos = Irene(0);
   cur = l * pos / k;
   if(pos < n) cur += g[pos];
   res = cur;
   for(int i = 0; i <= last; ++i) {
      pos = Irene(i + 1);
      cur = 1ll * l * (Irene(i + 1) - i - 1) / k + f[i];
      if(pos < n) cur += g[pos];
      res = min(res, cur);
   }
   return res;
}

/*int _n, _k, _l, _pos[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> _n >> _k >> _l;
    for(int i = 0; i < _n; ++i) cin >> _pos[i];
    cout << delivery(_n, _k, _l, _pos);
}*/

Compilation message (stderr)

boxes.cpp: In function 'int Irene(int)':
boxes.cpp:11:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 int Irene(int x) {return last + 1 + (k - last + x - 1 + k * n) % k;}
                          ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:21:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    for(int i = n - 1; i >= 0; --i) g[i] = 2 * (l - p[i]) + (i + k < n? g[i + k]: 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