제출 #347098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347098		ali_tavakoli	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	84 ms	8672 KiB

bridge

//In the name of Allah
#include<bits/stdc++.h>
using namespace std;
    
typedef long long ll;
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("O2")
    
const int N = 1e5 + 5;
    
int n, k, med[N][2], med2[N][2], p, q;
char ch1, ch2;
ll base, ans1[N], ans2[N];
    
vector<pair<ll, pair<int, int> > > ve;
    
priority_queue<int> q1, q3;
priority_queue<int, vector<int>, greater<int> > q2, q4;
    
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    ve.reserve(N);
    cin >> k >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> ch1 >> p >> ch2 >> q;
        //scanf("%c%d%c%d", &ch1, &p, &ch2, &q);
        if(ch1 != ch2)
            ve.pb({p + q, {min(p, q), max(p, q)}});
        else
            base += abs(p - q);
    }
    base += ve.size();
    sort(all(ve));
    
    ll s1 = 0, s2 = 0;
    for(int i = 0; i < ve.size(); i++)
    {
        auto x = ve[i];
    
        q1.push(x.S.F);
        s1 += x.S.F;
        q2.push(x.S.S);
        s2 += x.S.S;
        while(q1.top() > q2.top())
        {
            ll to1 = q1.top(), to2 = q2.top();
            q1.pop();q2.pop();
            q1.push(to2);
            s1 -= to1, s1 += to2;
            q2.push(to1);
            s2 -= to2, s2 += to1;
        }
        ans1[i] = q1.top() * q1.size() - s1 + s2 - q1.top() * q2.size();
        med[i][0] = q1.top();
        med[i][1] = q2.top();
    }
    
    //cout << med[ve.size() - 1][0] << " " << med[ve.size() - 1][1] << endl;
    
    //if(!n)
        //cout << base << endl;
    
    if(!ve.size())
    {
        cout << base << endl;
        return 0;
    }
    
    if(k == 1|| ve.size() == 1)
    {
        ll ans1, ans2;
        ans1 = ans2 = 0;
        for(int i = 0; i < ve.size(); i++)
        {
            ans1 += abs(ve[i].S.F - med[ve.size() - 1][0]);
            ans1 += abs(ve[i].S.S - med[ve.size() - 1][0]);
            ans2 += abs(ve[i].S.F - med[ve.size() - 1][1]);
            ans2 += abs(ve[i].S.S - med[ve.size() - 1][1]);
        }
        cout << min(ans1, ans2) + base << endl;
    }
    else
    {
        //cout << "BOOOM\n";
        ll ans = 1e15 + 5;
        ll s3 = 0, s4 = 0;
        
        for(int i = ve.size() - 1; i >= 0; i--)
        {
            auto x = ve[i];
    
            q3.push(x.S.F);
            s3 += x.S.F;
            q4.push(x.S.S);
            s4 += x.S.S;
            while(q3.top() > q4.top())
            {
                ll to1 = q3.top(), to2 = q4.top();
                q3.pop();q4.pop();
                q3.push(to2);
                s3 -= to1, s3 += to2;
                q4.push(to1);
                s4 -= to2, s4 += to1;
            }
            //cout << q3.top() * q3.size() << " " << s3 << '\n';
            ans2[i] = q3.top() * q3.size() - s3 + s4 - q3.top() * q4.size();
            //if(ans2[i] == 0)
               // cout << q3.top() << " " << q3.size() << " " << s3 << " " << s4 << " " << q4.top() << " " << q4.size() << '\n';
            //med2[i][0] = q3.top();
            //med2[i][1] = q4.top();
            if(i == 0)
                ans = min(ans, ans2[i]);
            else
                {
                    //cout << ans << " ";
                    ans = min(ans, ans2[i] + ans1[i - 1]);
                    //cout << ans << " " << ans2[i] + ans1[i - 1] << '\n';
                    //cout << i << " " << ans2[i] << " " << ans1[i - 1] << '\n';
                }
        }
        ans = min(ans, ans1[ve.size() - 1]);
    
        /*for(int i = 0; i < ve.size() - 1; i++)
        {
            ll ans1, ans2, ans3, ans4;
            ans1 = ans2 = ans3 = ans4 = 0;
            for(int j = 0; j <= i; j++)
            {
                ans1 += abs(ve[j].S.F - med[i][0]);
                ans1 += abs(ve[j].S.S - med[i][0]);
                ans2 += abs(ve[j].S.F - med[i][1]);
                ans2 += abs(ve[j].S.S - med[i][1]);
            }
            for(int j = i + 1; j < ve.size(); j++)
            {
                ans3 += abs(ve[j].S.F - med2[i + 1][0]);
                ans3 += abs(ve[j].S.S - med2[i + 1][0]);
                ans4 += abs(ve[j].S.F - med2[i + 1][1]);
                ans4 += abs(ve[j].S.S - med2[i + 1][1]);
            }
            
            ans = min(ans, min(ans1, ans2) + min(ans3, ans4));
        }
    
        ll ans1, ans2;
        ans1 = ans2 = 0;
        for(int i = 0; i < ve.size(); i++)
        {
            ans1 += abs(ve[i].S.F - med[ve.size() - 1][0]);
            ans1 += abs(ve[i].S.S - med[ve.size() - 1][0]);
            ans2 += abs(ve[i].S.F - med[ve.size() - 1][1]);
            ans2 += abs(ve[i].S.S - med[ve.size() - 1][1]);
        }
        ans = min(ans, min(ans1, ans2));*/
        //cout << base << '\n';
        //cout << ans << '\n';
        cout << ans + base << endl;
    }
}

/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0; i < ve.size(); i++)
      |                    ~~^~~~~~~~~~~
bridge.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i = 0; i < ve.size(); i++)
      |                        ~~^~~~~~~~~~~

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