Submission #869710

#	Time	Username	Problem	Language	Result	Execution time	Memory
869710		phamducminh	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	428 KiB

bridge

//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */







#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>

using namespace std;

#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
// #define push_back emplace_back
#define endl "\n"
#define all1(a) a+1,a+n+1

// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e9;
const long long MOD = (long long)1e9+7;

const long long MODD = 998244353;
const long long maxN = 2e6;
// const unsigned unsigned long long du=1000000007;
// unsigned unsigned long long w[20],v[20];
// map<unsigned unsigned long long,unsigned unsigned long long> q;
// unsigned unsigned long long n,ans=INF;
// unsigned unsigned unsigned long long a[200009],pre[200009],x=0,sum=0;
// unsigned unsigned long long n,h[1000009],j[1000009],b[1000009];


// unsigned unsigned long long t,n,x,a[1000009];


// unsigned long long t,a[10000009],max1i[10000009],maxin[10000009],maxx=-INF;




///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    

    
    long long t;


    // cin >> t;
    
    t=1;



    while (t--){
       



        solve();
       

    }

    

    

    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///


multiset<long long> ss;
long long sum=0,sum1=0,ans=INF,sum2=0;
void solve(){
 
    
    long long k,n;

    cin >> k >> n;

    for (long long i=1; i<=n; i++){

        char ch1,ch2;
        long long x,y;

        cin >> ch1 >> x >> ch2 >> y;


        if (ch1!=ch2)  {
            ss.insert(x); ss.insert(y); 
            sum+=x+y;
        }
        else sum1+=2,sum2+=abs(y-x);
    }

    if (k==1){
        auto it=ss.begin();

        if (ss.size()==0) return cout << sum2, void();

        advance(it, ss.size()/2);

        long long tam=*it;
        
        for (long long x: ss){
     
            ans+=abs(tam-x);
        }
     
        ans+=(ss.size()/2);
        ans+=sum2;
     
        cout << ans;
    }
    else{



        if (ss.size()==0) return cout << sum2, void();

        auto it=ss.begin();
        advance(it, ss.size()/2/2);
        long long tam1=*it;

        it=ss.begin();
        advance(it, ss.size()/2/2+1);
        long long tam2=*it;

        it=ss.begin();
        advance(it, ss.size()/2+(ss.size()/2/2));
        long long tam3=*it;

        it=ss.begin();
        advance(it, ss.size()/2+(ss.size()/2/2)+1);
        long long tam4=*it;


        long long ans1=0, ans2=0;

        long long d=0;
        for (long long x: ss){
            d++;

            if (d<=ss.size()/2) ans1+=abs(tam1-x);
            else ans2+=abs(tam3-x);
        }

        ans=min(ans,ans1+ans2);

        d=0; ans1=0, ans2=0;
        for (long long x: ss){
            d++;

            if (d<=ss.size()/2) ans1+=abs(tam1-x);
            else ans2+=abs(tam4-x);
        }

        ans=min(ans,ans1+ans2);

        d=0; ans1=0, ans2=0;
        for (long long x: ss){
            d++;

            if (d<=ss.size()/2) ans1+=abs(tam2-x);
            else ans2+=abs(tam3-x);
        }

        ans=min(ans,ans1+ans2);

        d=0; ans1=0, ans2=0;
        for (long long x: ss){
            d++;

            if (d<=ss.size()/2) ans1+=abs(tam2-x);
            else ans2+=abs(tam4-x);
        }

        ans=min(ans,ans1+ans2);
     
        ans+=(ss.size()/2);
        ans+=sum2;
     
        cout << ans;

    }


    
}

Compilation message (stderr)

bridge.cpp: In function 'void solve()':
bridge.cpp:184:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |             if (d<=ss.size()/2) ans1+=abs(tam1-x);
      |                 ~^~~~~~~~~~~~~
bridge.cpp:194:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |             if (d<=ss.size()/2) ans1+=abs(tam1-x);
      |                 ~^~~~~~~~~~~~~
bridge.cpp:204:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |             if (d<=ss.size()/2) ans1+=abs(tam2-x);
      |                 ~^~~~~~~~~~~~~
bridge.cpp:214:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |             if (d<=ss.size()/2) ans1+=abs(tam2-x);
      |                 ~^~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37