oj.uz

Submission #105449

# Submission time Handle Problem Language Result Execution time Memory
105449 2019-04-12T11:52:13 Z igzi Simfonija (COCI19_simfonija) C++17
110 / 110
 67 ms 4732 KB 
#include <bits/stdc++.h>

using namespace::std;

long long a[100005],b[100005],s[100005],n,k,i,ans=LLONG_MAX;
vector <int> v;

long long resi(int l,int d,int x){
long long p=lower_bound(v.begin(),v.end(),x)-v.begin();
p--;
long long res=0;
if(p>=l){res+=(p-l+1)*x;
res-=s[p+1]-s[l];}
p=upper_bound(v.begin(),v.end(),x)-v.begin();
if(p<=d){res+=s[d+1]-s[p];
res-=x*(d-p+1);
}
return res;
}

int main(){
std::ios_base::sync_with_stdio(0);
cin>>n>>k;
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n;i++) {cin>>b[i]; v.push_back(2*(a[i]-b[i]));}
sort(v.begin(),v.end());
s[0]=0;
for(i=1;i<=n;i++) s[i]=s[i-1]+v[i-1];
for(i=0;i<k+1;i++){
    int x,m,d;
    d=n-k+i-1;
    if(i>0){
        x=(v[i-1]+v[d])/2;
        ans=min(ans,resi(i,d,x));
    }
    if(d<n-1){
        x=(v[d+1]+v[i])/2;
        ans=min(ans,resi(i,d,x));
    }
    m=(i+d)/2;
    ans=min(ans,resi(i,d,v[m]));
}
cout<<ans/2<<endl;
return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3316 KB Output is correct
2 Correct 41 ms 3188 KB Output is correct
3 Correct 34 ms 3188 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3260 KB Output is correct
2 Correct 32 ms 3188 KB Output is correct
3 Correct 32 ms 3248 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3188 KB Output is correct
2 Correct 31 ms 3188 KB Output is correct
3 Correct 30 ms 3192 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3268 KB Output is correct
2 Correct 46 ms 3196 KB Output is correct
3 Correct 60 ms 4696 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3340 KB Output is correct
2 Correct 63 ms 4596 KB Output is correct
3 Correct 51 ms 4596 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3196 KB Output is correct
2 Correct 54 ms 4568 KB Output is correct
3 Correct 67 ms 4596 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3316 KB Output is correct
2 Correct 58 ms 4732 KB Output is correct
3 Correct 63 ms 4620 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3160 KB Output is correct
2 Correct 63 ms 4692 KB Output is correct
3 Correct 40 ms 4596 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3328 KB Output is correct
2 Correct 31 ms 4728 KB Output is correct
3 Correct 46 ms 4596 KB Output is correct