이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
ll delivery(int n, int k, int l, int p[]){
//comecar tudo r => O(N)
//transicao de x pra x+1 => O(1)
//comecar tudo l => O(N)
//complexidade total: O(3N)
ll cur = 0;
int y = 0;
for(int i=0;i<n;++i)if(p[i]!=0)++y;
for(int i=0;i<y;++i)p[i] = p[n-y+i];
n = y;
int fi = (n-1)%k;
for(int i=n-k;i>=0;i-=k){
cur += ll(l - p[i]);
cur += ll(min(l - p[i], p[i]));
}
if(n%k!=0)cur += ll(l - p[0]) + ll(min(l - p[0], p[0]));
ll resp = cur;
for(int i=0;i<n-1;++i){//esq até i, dir resto
//tratando r
cur -= ll(l - p[i]);
cur -= ll(min(l - p[i], p[i]));
if(i%k!=fi){//tenho que adicionar o proximo
cur += ll(l - p[i+1]);
cur += ll(min(l - p[i+1], p[i+1]));
}
//tratando l
if(i%k==0)cur += ll(p[i]) + ll(min(l - p[i], p[i]));
else{
cur -= ll(min(l - p[i-1],p[i-1]));
cur += ll(p[i]-p[i-1]) + ll(min(l-p[i],p[i]));
}
// cout<<cur<<" ";
ckmin(resp,cur);
}
cur = 0;
for(int i=k-1;i<n;i+=k){
cur += ll(p[i]);
cur += ll(min(l - p[i], p[i]));
}
if(n%k!=0)cur += ll(p[n-1]) + ll(min(l - p[n-1], p[n-1]));
ckmin(resp,cur);
// cout<<cur<<endl;
return resp;
}
// int positions[maxn];
// int main(){
// int n,k,l;cin>>n>>k>>l;
// for(int i=0;i<n;++i)cin>>positions[i];
// cout<<delivery(n,k,l,positions)<<endl;
// }
# | 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... |