Submission #104595

# Submission time Handle Problem Language Result Execution time Memory
104595 2019-04-08T10:00:03 Z Hassoony Simfonija (COCI19_simfonija) C++17
66 / 110
53 ms 864 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod=(1e9+7);
const ll inf=(1ll<<61);
const int MX=1e5+9;
int n,k,a[MX],x,b[MX];
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<n;i++)scanf("%d",&x),a[i]-=x;
    sort(a,a+n);
    int p1=0,p2=n-1;
    ll ans=0;
    bool ok=0;
    while(k--){
        int mid=(p1+p2)/2;
        if(abs(a[mid]-a[p1]) > abs(a[p2]-a[mid]))p1++;
        else if(abs(a[mid]-a[p1]) < abs(a[p2]-a[mid]))p2--;
        else{
            if(k>=1){
                p1++;p2--;
                k--;
            }
            else ok=1;
        }
    }
    if(!ok){
        int x=a[(p1+p2)/2];
        for(int i=p1;i<=p2;i++){
            a[i]-=x;
            ans+=abs(a[i]);
        }
        cout<<ans<<endl;
    }
    else{
//        cout<<p1<<" "<<p2<<endl;
        ll ans1=0;
        b[p1]=a[p1];
        p1++;
        int x=a[(p1+p2)/2];
        for(int i=p1;i<=p2;i++){
            b[i]=a[i];
            a[i]-=x;
            ans1+=abs(a[i]);
        }
        p1--;p2--;
        x=b[(p1+p2)/2];
        for(int i=p1;i<=p2;i++){
            b[i]-=x;
            ans+=abs(b[i]);
        }
        cout<<min(ans,ans1)<<endl;
    }
}

Compilation message

simfonija.cpp: In function 'int main()':
simfonija.cpp:11:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;i++)scanf("%d",&a[i]);
                         ~~~~~^~~~~~~~~~~~
simfonija.cpp:12:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;i++)scanf("%d",&x),a[i]-=x;
                         ~~~~~~~~~~~~~~^~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 41 ms 640 KB Output is correct
2 Correct 40 ms 640 KB Output is correct
3 Correct 45 ms 768 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 53 ms 640 KB Output is correct
2 Correct 35 ms 768 KB Output is correct
3 Correct 33 ms 760 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 52 ms 752 KB Output is correct
2 Correct 43 ms 732 KB Output is correct
3 Correct 41 ms 760 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 41 ms 752 KB Output is correct
2 Correct 33 ms 640 KB Output is correct
3 Correct 35 ms 760 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 864 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 50 ms 752 KB Output is correct
2 Correct 48 ms 652 KB Output is correct
3 Incorrect 39 ms 640 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 35 ms 640 KB Output is correct
2 Incorrect 53 ms 752 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 34 ms 768 KB Output is correct
2 Correct 51 ms 640 KB Output is correct
3 Correct 44 ms 768 KB Output is correct