이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7+2;
int n,k,l;
int pos[N];
ll kje1(){
ll sol = 0;
for(int i = 0; i < n; i++){
ll dod = 2*min(pos[i],(int)l-pos[i]);
sol += dod;
}
return sol;
}
ll kjen(){
int sol = l;
sol = min(sol,2*(l-pos[0]));
for(int i = 0; i < n-1; i++){
int sta = 2*pos[i]+2*(l-pos[i+1]);
sol = min(sol,sta);
}
sol = min(sol,2*pos[n-1]);
return sol;
}
ll inace(){
ll sol1 = 0;
int a = l/2, b = (l+1)/2;
for(int i = 0; i < n; i += k){
int kraj = min(i+k-1,n-1);
/// sad gledas range pos-ova od i do kraj
if(pos[kraj] <= a) sol1 += (ll)2*pos[kraj];
else if(pos[i] >= b) sol1 += (ll)2*(l-pos[i]);
else sol1 += l;
}
ll sol2 = 0;
a = l/2, b = (l+1)/2;
for(int i = n-1; i >= 0; i -= k){
int poc = max(0,i-k+1);
/// sad gledas range pos-ova od poc do i
if(pos[i] <= a) sol2 += (ll)2*pos[i];
else if(pos[poc] >= b) sol2 += (ll)2*(l-pos[poc]);
else sol2 += l;
}
return min(sol1,sol2);
}
ll dp1[N],dp2[N];
ll nesto(){
int a = l/2,b = (l+1)/2;
for(int i = 0; i < n; i++){
//if(pos[i] > a) break;
dp1[i] = 1e18;
for(int j = 1; j <= k && j <= i+1; j++){
dp1[i] = min(dp1[i],2*pos[i]+dp1[i-j]);
}
}
for(int i = n-1; i >= 0; i--){
//if(pos[i] < b) break;
dp2[i] = 1e18;
for(int j = 1; j <= k && j <= n-i; j++){
dp2[i] = min(dp2[i],2*(l-pos[i])+dp2[i+j]);
}
}
ll sol1 = dp2[0];
for(int i = 0; i < n; i++) sol1 = min(sol1,dp1[i]+dp2[i+1]);
ll sol2 = 1e18;
for(int i = 0; i < n; i++){
int kraj = min(n-1,i+k-1);
if(pos[i] <= a && pos[kraj] >= b){
ll sta = l;
if(i > 0) sta += dp1[i-1];
if(i < n-1) sta += dp2[i+1];
sol2 = min(sta,sol2);
}
}
return min(sol1,sol2);
}
ll delivery(int br1,int br2,int br3,int *positions){
n = br1;
k = br2;
l = br3;
for(int i = 0; i < n; i++) pos[i] = positions[i];
/*int sta = 0;
while(sta < n && pos[sta] == 0) sta++;
if(sta == n) return 0;
for(int i = 0; i < n-sta; i++) pos[i] = pos[i+sta];
n -= sta;
if(k == 1) return kje1();
if(k >= n) return kjen();*/
return nesto();
}
# | 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... |