Submission #368024

#	Time	Username	Problem	Language	Result	Execution time	Memory
368024		KoD	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	103 ms	39880 KiB

boxes

#ifndef LOCAL
#include "boxes.h"
#endif

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>

template <class T>
using Vec = std::vector<T>;

constexpr long long INF = std::numeric_limits<long long>::max();

template <class Select>
Vec<int> smawk(const int R, const int C, const Select &select) {
    const auto dfs = [&](const auto dfs, const Vec<int> &row, const Vec<int> &column) -> Vec<int> {
        if (row.empty()) {
            return { };
        }
        Vec<int> cs;
        cs.reserve(row.size());
        for (const auto c: column) {
            while (!cs.empty() && select(row[cs.size() - 1], cs.back(), c)) {
                cs.pop_back();
            }
            if (cs.size() < row.size()) {
                cs.push_back(c);
            }
        }
        Vec<int> rs;
        rs.reserve(row.size() / 2);
        for (int i = 1; i < (int) row.size(); i += 2) {
            rs.push_back(row[i]);
        }
        const auto half = dfs(dfs, rs, cs);
        Vec<int> ret(row.size());
        int idx = 0;
        for (int i = 0; i < (int) row.size(); ++i) {
            if (i & 1) {
                ret[i] = half[i / 2];
            }
            else {
                ret[i] = cs[idx];
                const auto next = (i + 1 == (int) row.size() ? cs.back() : half[i / 2]);
                while (cs[idx] < next) {
                    idx += 1;
                    if (select(row[i], ret[i], cs[idx])) {
                        ret[i] = cs[idx];
                    }
                }
            }
        }
        return ret;
    };
    Vec<int> row(R);
    std::iota(row.begin(), row.end(), 0);
    Vec<int> column(C);
    std::iota(column.begin(), column.end(), 0);
    return dfs(dfs, row, column);
}

Vec<long long> convolve(const Vec<long long> &A, const Vec<long long> &B) {
    const int N = (int) A.size();
    const int M = (int) B.size();
    const auto get = [&](const int i, const int j) {
        return A[j] + B[i - j];
    };
    const auto select = [&](const int i, const int j, const int k) {
        if (j > i || i >= M + j) return true;
        if (k > i) return false;
        return get(i, j) >= get(i, k);
    };
    Vec<long long> ret(N + M - 1);
    const auto best = smawk(N + M - 1, N, select);
    for (int i = 0; i < N + M - 1; ++i) {
        ret[i] = get(i, best[i]);
    }
    return ret;
}

long long delivery(int N, int K, int Len, int P[]) {
    Vec<int> left, right;
    left.reserve(N);
    right.reserve(N);
    for (int i = 0; i < N; ++i) {
        const auto l = P[i];
        const auto r = Len - P[i];
        if (l <= r) {
            left.push_back(l);
        }
        else {
            right.push_back(r);
        }
    } 
    std::reverse(right.begin(), right.end());
    const int L = (int) left.size();
    const int R = (int) right.size();
    Vec<long long> dp_l(L + 1), dp_r(R + 1);
    for (int i = 1; i <= L; ++i) {
        dp_l[i] = dp_l[(i >= K ? i - K : 0)] + 2 * left[i - 1];
    }
    for (int i = 1; i <= R; ++i) {
        dp_r[i] = dp_r[(i >= K ? i - K : 0)] + 2 * right[i - 1];
    }
    const auto dp = convolve(dp_l, dp_r);
    long long ret = INF;
    for (int i = 0; i <= N; ++i) {
        const auto first = (long long) Len * ((N - i + K - 1) / K);
        const auto second = dp[i];
        ret = std::min(ret, first + second);
    }
    return ret;
}

#ifdef LOCAL 
int main() {
    int N, K, L;
    std::cin >> N >> K >> L;
    int P[100] = {};
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i];
    }
    std::cout << delivery(N, K, L, P) << '\n';
    return 0;
}
#endif

Compilation message (stderr)

boxes.cpp: In lambda function:
boxes.cpp:17:90: warning: declaration of 'dfs' shadows a previous local [-Wshadow]
   17 |     const auto dfs = [&](const auto dfs, const Vec<int> &row, const Vec<int> &column) -> Vec<int> {
      |                                                                                          ^~~~~~~~
boxes.cpp:17:16: note: shadowed declaration is here
   17 |     const auto dfs = [&](const auto dfs, const Vec<int> &row, const Vec<int> &column) -> Vec<int> {
      |                ^~~
boxes.cpp: In instantiation of 'Vec<int> smawk(int, int, const Select&) [with Select = convolve(Vec<long long int>&, Vec<long long int>&)::<lambda(int, int, int)>; Vec<int> = std::vector<int, std::allocator<int> >]':
boxes.cpp:75:49:   required from here
boxes.cpp:17:22: warning: declaration of 'dfs' shadows a previous local [-Wshadow]
   17 |     const auto dfs = [&](const auto dfs, const Vec<int> &row, const Vec<int> &column) -> Vec<int> {
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   18 |         if (row.empty()) {
      |         ~~~~~~~~~~~~~~~~~~
   19 |             return { };
      |             ~~~~~~~~~~~
   20 |         }
      |         ~             
   21 |         Vec<int> cs;
      |         ~~~~~~~~~~~~  
   22 |         cs.reserve(row.size());
      |         ~~~~~~~~~~~~~~~~~~~~~~~
   23 |         for (const auto c: column) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   24 |             while (!cs.empty() && select(row[cs.size() - 1], cs.back(), c)) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   25 |                 cs.pop_back();
      |                 ~~~~~~~~~~~~~~
   26 |             }
      |             ~         
   27 |             if (cs.size() < row.size()) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   28 |                 cs.push_back(c);
      |                 ~~~~~~~~~~~~~~~~
   29 |             }
      |             ~         
   30 |         }
      |         ~             
   31 |         Vec<int> rs;
      |         ~~~~~~~~~~~~  
   32 |         rs.reserve(row.size() / 2);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~
   33 |         for (int i = 1; i < (int) row.size(); i += 2) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   34 |             rs.push_back(row[i]);
      |             ~~~~~~~~~~~~~~~~~~~~~
   35 |         }
      |         ~             
   36 |         const auto half = dfs(dfs, rs, cs);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   37 |         Vec<int> ret(row.size());
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~
   38 |         int idx = 0;
      |         ~~~~~~~~~~~~  
   39 |         for (int i = 0; i < (int) row.size(); ++i) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   40 |             if (i & 1) {
      |             ~~~~~~~~~~~~
   41 |                 ret[i] = half[i / 2];
      |                 ~~~~~~~~~~~~~~~~~~~~~
   42 |             }
      |             ~         
   43 |             else {
      |             ~~~~~~    
   44 |                 ret[i] = cs[idx];
      |                 ~~~~~~~~~~~~~~~~~
   45 |                 const auto next = (i + 1 == (int) row.size() ? cs.back() : half[i / 2]);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   46 |                 while (cs[idx] < next) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~
   47 |                     idx += 1;
      |                     ~~~~~~~~~
   48 |                     if (select(row[i], ret[i], cs[idx])) {
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   49 |                         ret[i] = cs[idx];
      |                         ~~~~~~~~~~~~~~~~~
   50 |                     }
      |                     ~ 
   51 |                 }
      |                 ~     
   52 |             }
      |             ~         
   53 |         }
      |         ~             
   54 |         return ret;
      |         ~~~~~~~~~~~   
   55 |     };
      |     ~                 
boxes.cpp:17:16: note: shadowed declaration is here
   17 |     const auto dfs = [&](const auto dfs, const Vec<int> &row, const Vec<int> &column) -> Vec<int> {
      |                ^~~

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