oj.uz

Submission #102521

# Submission time Handle Problem Language Result Execution time Memory
102521 2019-03-25T16:00:36 Z Nnandi Simfonija (COCI19_simfonija) C++14
110 / 110
 129 ms 4984 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;
typedef long long ll;
ll a[maxn], b[maxn], d[maxn], pf[maxn];
int n, k;

ll get_on(int p1, int p2) {
    if(p2 < p1) return 0LL;
    return pf[p2] - (p1 == 0 ? 0LL : pf[p1-1]);
}

int main()
{
    cin>>n>>k;
    ll sol = 0LL;
    for(int i=0;i<n;i++) {
        cin>>a[i];
    }
    for(int i=0;i<n;i++) {
        cin>>b[i];
    }
    for(int i=0;i<n;i++) {
        d[i] = a[i] - b[i];
        sol += abs(d[i]);
    }
    sort(d,d+n);

    for(int i=0;i<n;i++) {
        pf[i] = (i==0 ? d[i] : pf[i-1] + d[i]);

    }


    for(int i=0;i<=k;i++) {
        ll med = (i + i+n-k-1) / 2;
        //cout<<med<<endl;
        ll elol = (med-i) * d[med] - get_on(i,med-1);
        //cout<<(med-i) * d[med] <<" "<< get_on(i,med-1) <<endl;
        ll utan = get_on(med+1, i+n-k-1)  - (i+n-k-1-med) * d[med];
        //cout<<get_on(med+1, i+n-k-1)  <<" "<< (i+n-k-1-med) * d[med]<<endl;
        //cout<<elol<<" "<<utan<<endl;
        sol = min(sol,elol+utan);
    }
    cout<<sol<<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 107 ms 4976 KB Output is correct
2 Correct 108 ms 4964 KB Output is correct
3 Correct 85 ms 4936 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4856 KB Output is correct
2 Correct 99 ms 4972 KB Output is correct
3 Correct 93 ms 4984 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 4824 KB Output is correct
2 Correct 77 ms 4900 KB Output is correct
3 Correct 91 ms 4856 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4216 KB Output is correct
2 Correct 92 ms 4984 KB Output is correct
3 Correct 94 ms 4920 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 4952 KB Output is correct
2 Correct 96 ms 4872 KB Output is correct
3 Correct 89 ms 4856 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4828 KB Output is correct
2 Correct 94 ms 4832 KB Output is correct
3 Correct 125 ms 4984 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4952 KB Output is correct
2 Correct 91 ms 4856 KB Output is correct
3 Correct 99 ms 4856 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 4868 KB Output is correct
2 Correct 89 ms 4856 KB Output is correct
3 Correct 85 ms 4856 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 4984 KB Output is correct
2 Correct 86 ms 4860 KB Output is correct
3 Correct 113 ms 4932 KB Output is correct