Submission #869699

#	Time	Username	Problem	Language	Result	Execution time	Memory
869699		phamducminh	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	348 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>

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(){

    
    

    
    long long t;


    // cin >> t;
    
    t=1;



    while (t--){
       



        solve();
       

    }

    

    

    
}



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


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

    cin >> k >> n;

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

        char ch1,ch2;
        int x,y;

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


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

    int diff=1.0*sum/ss.size();



    auto it=ss.lower_bound(diff);

    int tam=*it; 
    it--;

    int tam1=*it; 


    if (abs(tam-diff)<abs(tam1-diff)) tam1=tam;
    else tam=tam1;    

    // cout << tam << "\n";

    for (int x: ss){

        ans+=abs(tam-x);
    }

    ans+=(ss.size()/2);
    ans+=sum1;

    cout << ans;


    
}

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