oj.uz

Submission #875377

# Submission time Handle Problem Language Result Execution time Memory
875377 2023-11-19T11:58:29 Z vjudge1 Simfonija (COCI19_simfonija) C++17
110 / 110
 27 ms 4380 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    deque<int>a(n),b(n);
    for(auto &i:a)cin>>i;
    for(auto &i:b)cin>>i;
    for(int i=0;i<n;i++)a[i]=b[i]-a[i];
    b.clear();
    sort(a.begin(),a.end());
    deque<pair<int,int>>dq1,dq2;
    for(auto &i:a)dq1.push_front({i,(dq1.empty()?i:dq1.front().second+i)});
    int K=k,KK=0;
    int ans=LONG_LONG_MAX;
    for(int i=0;i<n-1;i++){
        dq2.push_front({dq1.front().first,(dq2.empty()?dq1.front().first:dq2.front().second+dq1.front().first)});
        dq1.pop_front();
        K=min(K,(int)dq1.size());
        KK=k-K;
        while(K>0&&KK<dq2.size()&&abs(dq1[dq1.size()-K].first-dq2.front().first)<abs(dq2[dq2.size()-KK-1].first-dq2.front().first)){
            K--;
            KK++;
        }
        ans=min(ans,abs(dq2.front().second-dq2.front().first*(int)dq2.size())+abs(dq1.front().second-dq2.front().first*(int)dq1.size())
        -(K?llabs(dq1[dq1.size()-K].second-dq2[0].first*K):0ll)-(KK?llabs(dq2[dq2.size()-KK].second-dq2[0].first*KK):0ll));
    }
    cout<<ans;
}

Compilation message

simfonija.cpp: In function 'int main()':
simfonija.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         while(K>0&&KK<dq2.size()&&abs(dq1[dq1.size()-K].first-dq2.front().first)<abs(dq2[dq2.size()-KK-1].first-dq2.front().first)){
      |                    ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3004 KB Output is correct
2 Correct 22 ms 2964 KB Output is correct
3 Correct 20 ms 3000 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2748 KB Output is correct
2 Correct 24 ms 2740 KB Output is correct
3 Correct 20 ms 3004 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2956 KB Output is correct
2 Correct 24 ms 2748 KB Output is correct
3 Correct 20 ms 3004 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3004 KB Output is correct
2 Correct 20 ms 3004 KB Output is correct
3 Correct 21 ms 2740 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3004 KB Output is correct
2 Correct 25 ms 3004 KB Output is correct
3 Correct 26 ms 4336 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2736 KB Output is correct
2 Correct 23 ms 3044 KB Output is correct
3 Correct 25 ms 2748 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2748 KB Output is correct
2 Correct 22 ms 4276 KB Output is correct
3 Correct 26 ms 4272 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3000 KB Output is correct
2 Correct 27 ms 4380 KB Output is correct
3 Correct 27 ms 4276 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2744 KB Output is correct
2 Correct 21 ms 3004 KB Output is correct
3 Correct 25 ms 2948 KB Output is correct