Submission #249648

#	Time	Username	Problem	Language	Result	Execution time	Memory
249648		rdd6584	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	86 ms	2708 KiB

bridge

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

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = (ll)1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

ll fac[1] = {1}, inv[1] = {1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mp(ll a,ll b){ll ret=1;while(b){if(b&1)ret=ret*a%MOD;a=a*a%MOD;b>>=1;}return ret;}
ll cmb(ll r, ll c) {return fac[r] * inv[c] % MOD * inv[r - c] % MOD;}

vector<pll> v;
ll cal(int mid) {
    ll ret= 0;
    for (pll i : v) {
        if (i.first <= mid && mid <= i.second) continue;
        ret += min(abs(i.first-mid), abs(i.second-mid));
    }
    return ret*2;
}

int main() {
    int k, n;
    scanf("%d %d", &k, &n);

    // 그냥 두 점이 어디있다?
    // 정도만 알아도 되잖아?

    ll sum = 0;
    for (int i = 0; i < n; i++) {
        char a,c;
        int b,d;
        scanf(" %c %d %c %d", &a, &b ,&c, &d);
        sum += abs(b-d);
        if (a!=c) {
            if (b>d) swap(b,d);
            sum++;
            v.push_back({b, d});
        }
    }

    int le = 0, ri = 999999999, mid;
    while (le <= ri) {
        mid = (le+ri)/2;
        ll ss = cal(mid);
        ll st = cal(mid+1);
        if (ss > st) le = mid + 1;
        else ri = mid - 1;
    }
    printf("%lld", cal(le)+sum);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d", &a, &b ,&c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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