oj.uz

Submission #676425

# Submission time Handle Problem Language Result Execution time Memory
676425 2022-12-30T21:38:36 Z Essa2006 Simfonija (COCI19_simfonija) C++14
55 / 110
 34 ms 3408 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (int)(1000000007)
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, k;
    cin>>n>>k;
    vector<int>A(n);
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0, a;i<n;i++){
        cin>>a;
        A[i]-=a;
    }
    sort(all(A));
    vector<int>Pre(n);
    Pre[0]=A[0];
    int ans=1e18;
    for(int i=1;i<n;i++)
        Pre[i]=Pre[i-1]+A[i];
    int md=(n-k)/2;
    for(int i=0;i<n;i++){
        int sum=0;
        if(i+k-1<n){    
           int ind=(md>=i? k+md:md), val=A[ind];
           if(ind<i){
               sum=(val*(ind+1))-Pre[ind];
               int len=(i-1)-(ind+1)+1+(n-1)-(i+k)+1;
               sum+=Pre[n-1]-(i+k?Pre[i+k-1]:0)+(i?Pre[i-1]:0)-Pre[ind]-val*len;
           }
           else{
               sum=Pre[n-1]-Pre[ind]-val*((n-1)-(ind+1)+1);
               int len=i+(ind)-(i+k)+1;
               sum+=val*len-(Pre[ind]-Pre[i+k-1]+(i?Pre[i-1]:0));
           }
        }
        else{
            int l=k-((n-1)-i+1)-1, ind=md+l, val=A[ind];
            sum=(ind-(l)+1)*val-(Pre[ind]-(l?Pre[l-1]:0))+Pre[i-1]-Pre[ind]-val*(i-ind-1);
        }
        ans=min(ans, sum);
    }
    cout<<ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3276 KB Output is correct
2 Correct 25 ms 3408 KB Output is correct
3 Correct 20 ms 3276 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3280 KB Output is correct
2 Correct 22 ms 3280 KB Output is correct
3 Correct 21 ms 3280 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3268 KB Output is correct
2 Correct 23 ms 3320 KB Output is correct
3 Correct 20 ms 3268 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3280 KB Output is correct
2 Correct 24 ms 3316 KB Output is correct
3 Incorrect 25 ms 3272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3260 KB Output is correct
2 Incorrect 21 ms 3256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3296 KB Output is correct
2 Incorrect 25 ms 3276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3304 KB Output is correct
2 Correct 24 ms 3272 KB Output is correct
3 Correct 30 ms 3260 KB Output is correct