Submission #725768

#TimeUsernameProblemLanguageResultExecution timeMemory
725768becaidoBoxes with souvenirs (IOI15_boxes)C++17
100 / 100
534 ms292084 KiB
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

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

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {
    cout << '\n';
}
template<typename T, typename...U>
void dout (T t, U...u) {
    cout << t << (sizeof... (u) ? ", " : ""), dout (u...);
}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e7 + 5;

ll L[SIZE], R[SIZE];

ll delivery (int n, int k, int len, int a[]) {
    FOR (i, 0, n - 1) L[i] = (i >= k ? L[i - k] : 0) + min(2 * a[i], len);
    for (int i = n - 1; i >= 0; i--) R[i] = (i+k < n ? R[i+k] : 0) + min(2 * (len-a[i]), len);
    ll ans = min(L[n - 1], R[0]);
    FOR (i, 0, n - 2) ans = min(ans, L[i] + R[i + 1]);
    return ans;
}

#ifdef WAIMAI
int main() {
    int N, K, L, i;
    cin >> N >> K >> L;
    int *p = (int*) malloc (sizeof (int) * (unsigned int) N);
    for (i = 0; i < N; i++) cin >> p[i];
    cout << delivery (N, K, L, p) << '\n';
}
#endif

/*
in1
3 2 8
1 2 5
out1
10
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...