oj.uz

Submission #100579

# Submission time Handle Problem Language Result Execution time Memory
100579 2019-03-12T13:14:42 Z fbosnjak Simfonija (COCI19_simfonija) C++14
99 / 110
 53 ms 4596 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll N, K;
ll a[100100], b[100100];
vector <ll> v;

ll sol = 1e18;
ll low, high, curr, sum, lok, bris_sum;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }

    for (int i = 0; i < N; i++)
    {
        cin >> b[i];
    }

    if (K == N) {cout << 0; return 0;}

    for (int i = 0; i < N; i++)
    {
        v.push_back(a[i] - b[i]);
    }

    sort(v.begin(), v.end());

    /*for (int i = 0; i < N; i++)
    {
        cout << v[i] << ' ';
    }
    cout << endl;*/

    low = 0;
    high = N - K;
    curr = v[0];

    for (int i = 0; i < N; i++)
    {
        sum += abs(curr - v[i]);
    }

    int sz = (int)v.size();

    while (lok < sz && v[lok] <= curr) lok++;

    //cout << lok << endl;

    for (int i = N - K; i < N; i++)
    {
        bris_sum += (v[i] - curr);
    }

    //cout << sum << ' ' << bris_sum << endl;

    sol = sum - bris_sum;

    //cout << "high " << high << endl;

    for (int i = curr + 1; i <= v[sz - 1]; i++)
    {
        sum += lok;
        sum -= (N - lok);

        //cout << "sum " << sum << endl;

        while (lok < sz && v[lok] <= i) lok++;

        bris_sum += low;
        bris_sum -= (N - high);

        if (K > 0)
        {
            //cout << "uso sam " << endl;
            //cout << high << ' ' << N << endl;
            //cout << abs(v[low] - i) << ' '  << abs(v[high] - i) << endl;
            while (high < N && abs(v[low] - i) >= abs(v[high] - i))
            {
                bris_sum -= abs(v[high] - i);
                bris_sum += abs(v[low] - i);

                low++;
                high++;
            }
        }

        //cout << "bris_sum " << bris_sum << endl;

        sol = min(sol, sum - bris_sum);
    }

    cout << sol;
}

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 2 ms 384 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4596 KB Output is correct
2 Correct 38 ms 4468 KB Output is correct
3 Correct 35 ms 4468 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4444 KB Output is correct
2 Correct 36 ms 4500 KB Output is correct
3 Correct 35 ms 4468 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4496 KB Output is correct
2 Correct 38 ms 4468 KB Output is correct
3 Correct 35 ms 4468 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3828 KB Output is correct
2 Correct 30 ms 4468 KB Output is correct
3 Correct 39 ms 4476 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4468 KB Output is correct
2 Correct 37 ms 4492 KB Output is correct
3 Correct 45 ms 4468 KB Output is correct

Subtask #7
0 / 11.0

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

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 4448 KB Output is correct
2 Correct 38 ms 4568 KB Output is correct
3 Correct 42 ms 4596 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4476 KB Output is correct
2 Correct 40 ms 4468 KB Output is correct
3 Correct 36 ms 4476 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4468 KB Output is correct
2 Correct 37 ms 4468 KB Output is correct
3 Correct 42 ms 4468 KB Output is correct