oj.uz

Submission #105446

# Submission time Handle Problem Language Result Execution time Memory
105446 2019-04-12T11:37:06 Z igzi Simfonija (COCI19_simfonija) C++17
44 / 110
 55 ms 4724 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){
int p=lower_bound(v.begin(),v.end(),x)-v.begin();
p--;
long long res;
res+=(p-l+1)*x;
res-=s[p+1]-s[l];
p=upper_bound(v.begin(),v.end(),x)-v.begin();
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;
}

Compilation message

simfonija.cpp: In function 'long long int resi(int, int, int)':
simfonija.cpp:12:4: warning: 'res' is used uninitialized in this function [-Wuninitialized]
 res+=(p-l+1)*x;
 ~~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 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 32 ms 3160 KB Output is correct
2 Correct 37 ms 3208 KB Output is correct
3 Correct 38 ms 3212 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3324 KB Output is correct
2 Correct 31 ms 3172 KB Output is correct
3 Correct 36 ms 3272 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3188 KB Output is correct
2 Correct 42 ms 3180 KB Output is correct
3 Correct 31 ms 3272 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3300 KB Output is correct
2 Incorrect 46 ms 4724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 3188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 3196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 3272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 3204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 3188 KB Output isn't correct
2 Halted 0 ms 0 KB -