Submission #786584

#	Time	Username	Problem	Language	Result	Execution time	Memory
786584		ikaurov	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	1 ms	340 KiB

boxes

// #include "boxes.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

const __int128_t INF = 1e25;

long long delivery(int n, int k, int l, int x[]){
  vector<ll> pdp(n), sdp(n);
  for (int i = 0; i < n; i++){
    pdp[i] = (i - k >= 0? pdp[i - k] : 0) + 2 * x[i];
  }
  for (int i = n - 1; i >= 0; i--){
    sdp[i] = (i + k < n? sdp[i + k] : 0) + 2 * (l - x[i]);
  }
  __int128_t ans = INF;
  vector<__int128_t> minval(k, INF);
  minval[n % k] = n * 1ll * l;
  for (int i = n - 1; i >= -1; i--){
    if (minval[(i + 1) % k] != INF){
      ans = min(ans, ((__int128_t)k * pdp[i] - l * 1ll * (i + 1) + minval[(i + 1) % k]) / k);
    }
    ans = min(ans, (__int128_t)(i == -1? 0 : pdp[i]) + (n - i + k - 2) / k * 1ll * l);
    if (i == -1) continue;
    minval[i % k] = min(minval[i % k], (__int128_t)sdp[i] * k + i * 1ll * l);
  }
  return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:35:10: warning: conversion from '__int128' to 'long long int' may change value [-Wconversion]
   35 |   return ans;
      |          ^~~

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