제출 #42422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42422		TAMREF	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	95 ms	45632 KiB

bridge

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;

typedef long long ll;
const int mx = 100005;

int k, n, m;
ll D[mx], E[mx];

struct People{
    int a, b;
    bool operator < (People z){
        return a + b < z.a + z.b;
    }
} P[mx];

void subpr(ll *V){
    if(!n) return;
    ll dval = abs(P[0].a - P[0].b);
    priority_queue<int> lft;
    priority_queue<int,vector<int>,greater<int>> rgt;

    int brp = P[0].a;
    (P[0].b < brp ? lft.push(P[0].b) : rgt.push(P[0].b));
    V[0] = dval;
    //printf("%lld\n",V[0]);
    for(int i = 1; i < n; i++){
        //cout << "i = " << i << endl;
        dval += abs(brp - P[i].a) + abs(brp - P[i].b);
        P[i].a < brp ? lft.push(P[i].a) : rgt.push(P[i].a);
        P[i].b < brp ? lft.push(P[i].b) : rgt.push(P[i].b);
        while(sz(lft) < sz(rgt)){
            int nbr = rgt.top(); rgt.pop();
            //cout << brp << " -> " << nbr << endl;
            lft.push(brp);
            dval += (ll)(nbr - brp) * (sz(lft) - sz(rgt) - 1);
            brp = nbr;
        }
        while(sz(lft) > sz(rgt) + 1){
            int nbr = lft.top(); lft.pop();
            //cout << brp << " -> " << nbr << endl;
            rgt.push(brp);
            dval += (ll)(brp - nbr) * (sz(rgt) - sz(lft) - 1);
            brp = nbr;
        }
        V[i] = dval;
        //printf("%d %lld\n",brp,V[i]);
    }
}

ll off;
void input(){
    scanf("%d %d",&k,&m);
    while(m--){
        char p,q;
        int a,b;
        scanf("%*c%c %d %c %d",&p,&a,&q,&b);
        //printf("m = %d, %c %d %c %d\n",m,p,a,q,b);
        if(p == q) off += abs(a - b);
        else P[n++] = {a, b};
    }
}

int main(){
    input();
    sort(P,P+n);
    //for(int i = 0; i < n; i++) printf("%d %d\n",P[i].a,P[i].b);
    subpr(D);
    if(k == 1) return !printf("%lld\n",D[n-1] + off + n);
    reverse(P,P+n);
    subpr(E);
    ll ans = min(D[n-1], E[n-1]);
    for(int i = 0; i < n - 1; i++){
        ans = min(ans, D[i] + E[n - 2 - i]);
    }
    printf("%lld\n",ans + off + n);
}

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

bridge.cpp: In function 'void input()':
bridge.cpp:54:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&k,&m);
                         ^
bridge.cpp:58:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%*c%c %d %c %d",&p,&a,&q,&b);
                                            ^

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