Submission #41722

#	Time	Username	Problem	Language	Result	Execution time	Memory
41722		funcsr	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	557 ms	141304 KiB

boxes

#include "boxes.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF (1LL<<60)
typedef pair<int, int> P;
int A[10000000], B[10000000];
int HA[10000000], HB[10000000];
long long SA[10000000], SB[10000000];

long long delivery(int N, int K, int L, int X[]) {
  //rep(i, N) cout << X[i]<<",";cout<<"\n";
  rep(i, N) A[i] = min(2LL*X[i], (long long)L);
  rep(i, N) B[i] = min(2LL*(L-X[i]), (long long)L);
  rep(i, N) SB[i%K] += B[i];
  long long m = INF;
  rep(i, N+1) {
    long long s = SB[i%K];
    if (i > 0) {
      int k = (i-1)%K;
      while (HA[k]*K+k <= i-1) SA[k] += A[HA[k]*K+k], HA[k]++;
      s += SA[k];
    }
    //for (int x=i-1; x>=0; x-=K) s += A[x];
    m = min(m, s);
    if (i < N) {
      int k = i%K;
      while (HB[k]*K+k <= i) SB[k] -= B[HB[k]*K+k], HB[k]++;
    }
  }
  return m;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:24:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   rep(i, N) A[i] = min(2LL*X[i], (long long)L);
                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~
boxes.cpp:25:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   rep(i, N) B[i] = min(2LL*(L-X[i]), (long long)L);
                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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