oj.uz

Submission #126022

# Submission time Handle Problem Language Result Execution time Memory
126022 2019-07-06T18:45:31 Z OptxPrime Simfonija (COCI19_simfonija) C++11
11 / 110
 40 ms 5012 KB 
#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long

    long long a[100010],b[100010],d[100010], pref[100010];

    /// usran kod previse  zeznuta implementacija

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

        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++ )cin>>a[i];
        for( int i=1;i<=n;i++ ) cin>>b[i];
        for( int i=1;i<=n;i++ )  d[i] = a[i]-b[i];
        sort( d+1,d+n+1 );
        int fplus=n+1;
        for( int i=1;i<=n;i++ ){
            if( d[i] > 0 )fplus = min( fplus, i );
            pref[i] = pref[i-1]+d[i];
        }
        long long res=1e15;
        int left=0,right = n-k+1;
        long long sum;
        for( int i=0;i<=k;i++ ){
                sum=0;
                /// ovo je ako je vise negativnih,valjda dobro radi ?!
            int l=i+1, r = n-k+i;
            /// sad u rangeu l,r radimo
            int mid = ( l+r )/2;
            if( fplus > mid ){  /// ako je vise negativnih
                ///prvi range je l, mid, drugi je mid,plus, i treci plus, r
            long long sum=0;
            int pomak = abs( d[mid] );
            sum += abs( pref[mid] - pref[l-1] ) - ( mid-l+1 )*pomak; /// prvi range je range skroz malih razlika, apsolutne razlike se onda smanje dodavanjem srednjeg, tj mid+1og
     //   if( i == 0  ) cout << sum << " ha " << mid << " "  << pref[mid ] << " " << pref[l-1 ] << abs( d[mid+1] ) <<endl;
     //     if( i==1 ) cout << sum << " eto " <<endl;
            if( fplus <= r ){
                sum += (fplus-mid-2)*pomak -  abs( pref[fplus-1] - pref[mid] ); /// srednji range je onaj koji predje iz negativnih u pozitivne
                sum += abs( pref[r] - pref[fplus-1] ) + (r-fplus+1)*pomak;
            }
            else{
                sum+= (r-mid)*pomak -  abs(pref[r] - pref[mid]);
            }
     //       if( i==1 ) cout << sum<< " keru " <<endl;
           // if( i==0 ) cout << sum << " rile  " <<endl;
           res=min( res, abs(sum) );
            }
            else{   ///ima vise pozitivnih, onda od srednjeg slicno ide
                  //  cout << " ne rise " <<endl;
                     sum=0;
                    int pomak = abs( d[mid] );
                sum += abs( pref[r] - pref[mid-1] ) - ( r-mid+1 )*pomak;   ///OVOG PUTA MID A NE MID+1, SKONTAT IMAL VEZE
                if( fplus >= l ){
                    sum+= (mid-fplus)*pomak - abs( pref[mid-1] - pref[fplus-1] );
                    sum += abs( pref[fplus-1] - pref[l-1] ) + ( fplus-l )*pomak;
                }
            else{
                sum += (mid-l)*pomak -  abs( pref[mid-1] - pref[l-1] );
            }
             res=min( res, abs(sum) );
            }
         //   cout << i << sum <<endl;
       //    res=min( res,abs(sum) );
        }
            cout<<res<<endl;
        return 0;
    }

Compilation message

simfonija.cpp: In function 'int main()':
simfonija.cpp:38:13: warning: unused variable 'left' [-Wunused-variable]
         int left=0,right = n-k+1;
             ^~~~
simfonija.cpp:38:20: warning: unused variable 'right' [-Wunused-variable]
         int left=0,right = n-k+1;
                    ^~~~~

Subtask #1
0 / 11.0

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3832 KB Output is correct
2 Incorrect 35 ms 3832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3964 KB Output is correct
2 Incorrect 36 ms 3960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3832 KB Output is correct
2 Correct 38 ms 5012 KB Output is correct
3 Correct 38 ms 4916 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3876 KB Output is correct
2 Incorrect 36 ms 3920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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