oj.uz

Submission #875376

# Submission time Handle Problem Language Result Execution time Memory
875376 2023-11-19T11:54:49 Z vjudge1 Simfonija (COCI19_simfonija) C++17
66 / 110
 31 ms 4472 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].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].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 0 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 4380 KB Output is correct
2 Correct 23 ms 4384 KB Output is correct
3 Correct 22 ms 4272 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4272 KB Output is correct
2 Correct 23 ms 4264 KB Output is correct
3 Correct 21 ms 4276 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4284 KB Output is correct
2 Correct 25 ms 4276 KB Output is correct
3 Correct 21 ms 4284 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3772 KB Output is correct
2 Correct 21 ms 4444 KB Output is correct
3 Correct 22 ms 4384 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4408 KB Output is correct
2 Incorrect 31 ms 4348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4356 KB Output is correct
2 Correct 22 ms 4284 KB Output is correct
3 Incorrect 25 ms 4272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4344 KB Output is correct
2 Correct 21 ms 4280 KB Output is correct
3 Correct 26 ms 4276 KB Output is correct