Submission #397824

#	Time	Username	Problem	Language	Result	Execution time	Memory
397824		qwerty234	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1 ms	460 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;

vector <ll> val_cw, val_ccw, cf_cw, cf_ccw, dp_cw, dp_ccw;
vector <pair<ll, ll>> cw, ccw;
ll s_cw, s_ccw, add, shift_cw, shift_ccw, n_cw, n_ccw, n, k;
ll ans_cw, ans_ccw, ans, l;

void process_cw(int k) {
  ll cur = 0;
  dp_cw[cur] = ans_cw;
  for (ll i = n_cw - 1; i >= 0; i--) {
    while (cw[i].se > 0) {
      cw[i].se--; cur++;
      s_cw--;
      shift_cw = (shift_cw + 1) % k;
      ans_cw -= val_cw[shift_cw];
      dp_cw[cur] = ans_cw;
    }
    val_cw[shift_cw] -= cf_cw[i];
  }
}

void process_ccw(int k) {
  ll cur = 0;
  dp_ccw[cur] = ans_ccw;
  for (ll i = n_ccw - 1; i >= 0; i--) {
    while (ccw[i].se > 0) {
      ccw[i].se--; cur++;
      s_ccw--;
      shift_ccw = (shift_ccw + 1) % k;
      ans_ccw -= val_ccw[shift_ccw];
      dp_ccw[cur] = ans_ccw;
    }
    val_ccw[shift_ccw] -= cf_ccw[i];
  }
}

// ll delivery(int n, int k, int l, vector <ll> p) {
ll delivery(int n1, int k1, int l1, int p[]) {
  ll n = (ll)n1, k = (ll)k1, l = (ll)l1;
  add = 0;
  cw.clear(); ccw.clear();
  for (ll i = 0; i < n; i++) {
    if (l % 2 == 0 && p[i] == l / 2) {
      add++;
    } else if (p[i] <= l / 2 && p[i] != 0) {
      if (cw.size() == 0 || cw[cw.size() - 1].fi != p[i])
        cw.pb({p[i], 0});
      cw[cw.size() - 1].se++;
    } else if (p[i] != 0) {
      if (ccw.size() == 0 || ccw[ccw.size() - 1].fi != p[i])
        ccw.pb({p[i], 0});
      ccw[ccw.size() - 1].se++;
    }
  }
  reverse(ccw.begin(), ccw.end());
  val_cw.assign(k, 0);
  val_ccw.assign(k, 0);
  n_cw = cw.size();
  n_ccw = ccw.size();
  cf_cw.assign(n_cw, 0);
  dp_cw.assign(n_cw + 1, 0);
  for (ll i = 0; i < n_cw; i++) {
    if (i == 0)
      cf_cw[i] = cw[i].fi;
    else
      cf_cw[i] = cw[i].fi - cw[i - 1].fi;
  }

  cf_ccw.assign(n_ccw, 0);
  dp_ccw.assign(n_ccw + 1, 0);
  for (ll i = 0; i < n_ccw; i++) {
    if (i == 0)
      cf_ccw[i] = l - ccw[i].fi;
    else
      cf_ccw[i] = ccw[i - 1].fi - ccw[i].fi;
  }

  ans_cw = ans_ccw = s_cw = s_ccw = shift_cw = shift_ccw = 0;
  for (ll i = n_cw - 1; i >= 0; i--) {
    s_cw += cw[i].se;
    val_cw[s_cw % k] += cf_cw[i];
    ans_cw += (ll)((s_cw + k - 1) / k) * (ll)cf_cw[i];
  }
  for (ll i = n_ccw - 1; i >= 0; i--) {
    s_ccw += ccw[i].se;
    val_ccw[s_ccw % k] += cf_ccw[i];
    ans_ccw += (ll)((s_ccw + k - 1) / k) * (ll)cf_ccw[i];
  }
  process_cw(k);
  process_ccw(k);
  ans = ((n + k - 1) / k) * l;
  for (ll i = 0; i <= n_cw; i++) {
    ll cnt = (i + add + k - 1) / k;
    ll tmp = cnt * l, mod = cnt * k - (add + i);
    ans = min(ans, 2 * dp_cw[i] + tmp + 2 * dp_ccw[min(mod, n_ccw)]);
  }
  return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'void process_cw(int)':
boxes.cpp:14:22: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   14 | void process_cw(int k) {
      |                      ^
boxes.cpp:11:59: note: shadowed declaration is here
   11 | ll s_cw, s_ccw, add, shift_cw, shift_ccw, n_cw, n_ccw, n, k;
      |                                                           ^
boxes.cpp: In function 'void process_ccw(int)':
boxes.cpp:29:23: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   29 | void process_ccw(int k) {
      |                       ^
boxes.cpp:11:59: note: shadowed declaration is here
   11 | ll s_cw, s_ccw, add, shift_cw, shift_ccw, n_cw, n_ccw, n, k;
      |                                                           ^
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:46:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   46 |   ll n = (ll)n1, k = (ll)k1, l = (ll)l1;
      |      ^
boxes.cpp:11:56: note: shadowed declaration is here
   11 | ll s_cw, s_ccw, add, shift_cw, shift_ccw, n_cw, n_ccw, n, k;
      |                                                        ^
boxes.cpp:46:18: warning: declaration of 'k' shadows a global declaration [-Wshadow]
   46 |   ll n = (ll)n1, k = (ll)k1, l = (ll)l1;
      |                  ^
boxes.cpp:11:59: note: shadowed declaration is here
   11 | ll s_cw, s_ccw, add, shift_cw, shift_ccw, n_cw, n_ccw, n, k;
      |                                                           ^
boxes.cpp:46:30: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   46 |   ll n = (ll)n1, k = (ll)k1, l = (ll)l1;
      |                              ^
boxes.cpp:12:26: note: shadowed declaration is here
   12 | ll ans_cw, ans_ccw, ans, l;
      |                          ^
boxes.cpp:96:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |   process_cw(k);
      |              ^
boxes.cpp:97:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |   process_ccw(k);
      |               ^

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