Submission #875377

#	Time	Username	Problem	Language	Result	Execution time	Memory
875377		vjudge1	Simfonija (COCI19_simfonija)	C++17	110 / 110	27 ms	4380 KiB

simfonija

#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 (stderr)

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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11