이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef _DEBUG
#include "boxes.h"
#else
long long delivery(int N, int K, int L, int p[]);
#endif
#define ll long long
ll inf = LLONG_MAX / 10;
struct SegTree
{
vector<ll> b;
vector<ll> a;
SegTree(int n)
{
b.resize(4 * n, inf);
a.resize(n, inf);
}
ll segGet(int l, int r, int i, int ql, int qr)
{
if (qr <= l || r <= ql)
return inf;
if (ql <= l && qr >= r)
return b[i];
int m = (l + r) / 2;
return min(segGet(l, m, i * 2 + 1, ql, qr), segGet(m, r, i * 2 + 2, ql, qr));
}
ll segSet(int l, int r, int i, int k, ll x)
{
if (r <= k || l > k)
return b[i];
if (l + 1 == r)
return a[l] = b[i] = x;
int m = (l + r) / 2;
return b[i] = min(segSet(l, m, i * 2 + 1, k, x), segSet(m, r, i * 2 + 2, k, x));
}
};
vector<ll> calculate_pref(int l, vector<int> a, int k)
{
int n = a.size() + 1;
vector<ll> out(n);
deque<pair<int, int>> sliding_window;
sliding_window.push_back({0, 0});
for (int i = 1; i < n; i++)
{
ll prev = 0;
while (sliding_window.size() > 0 && i - sliding_window.front().second > k)
sliding_window.pop_front();
if (sliding_window.size())
prev = sliding_window.front().first;
ll cost = int64_t(a[i - 1]) + prev + min<ll>(a[i - 1], l - a[i - 1]);
out[i] = cost;
while (sliding_window.size() > 0 && sliding_window.back().first >= cost)
sliding_window.pop_back();
sliding_window.push_back({cost, i});
}
return out;
}
long long delivery(int N, int K, int L, int p[])
{
vector<int> positions(N);
for (int i = 0; i < N; i++)
positions[i] = p[i];
vector<ll> pref = calculate_pref(L, positions, K);
reverse(positions.begin(), positions.end());
for (int i = 0; i < N; i++)
positions[i] = L - positions[i];
vector<ll> suff = calculate_pref(L, positions, K);
ll best = inf;
for (int cnt_a = 0; cnt_a <= N; cnt_a++)
{
int cnt_b = N - cnt_a;
best = min(best, pref[cnt_a] + suff[cnt_b]);
}
return best;
}
#ifdef _DEBUG
#include <stdio.h>
#include <stdlib.h>
static char buffer[1024];
static int currentChar = 0;
static int charsNumber = 0;
static inline int read()
{
if (charsNumber < 0)
{
exit(1);
}
if (!charsNumber || currentChar == charsNumber)
{
charsNumber = (int)fread(buffer, sizeof(buffer[0]), sizeof(buffer), stdin);
currentChar = 0;
}
if (charsNumber <= 0)
{
return -1;
}
return buffer[currentChar++];
}
static inline int readInt()
{
int x;
cin >> x;
return x;
}
int main()
{
int N, K, L, i;
N = readInt();
K = readInt();
L = readInt();
int *p = (int *)malloc(sizeof(int) * (unsigned int)N);
for (i = 0; i < N; i++)
{
p[i] = readInt();
}
fprintf(stdout, "%lld\n", delivery(N, K, L, p));
return 0;
}
#endif
컴파일 시 표준 에러 (stderr) 메시지
boxes.cpp: In function 'std::vector<long long int> calculate_pref(int, std::vector<int>, int)':
boxes.cpp:56:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
56 | int n = a.size() + 1;
| ~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |