Submission #682519

#	Time	Username	Problem	Language	Result	Execution time	Memory
682519		79brue	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	62 ms	6316 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
ll base, ans;
ll a[100002], b[100002];

int main(){
    scanf("%d %d", &k, &n);
    for(int i=1; i<=n; i++){
        char C1, C2;
        int X1, X2;
        scanf(" %c %d %c %d", &C1, &X1, &C2, &X2);
        if(C1==C2) base += abs(X1-X2), n--, i--;
        else a[i] = X1, b[i] = X2;
    }
    if(n==0){
        printf("%lld", base);
        return 0;
    }
    if(k==1){
        vector<ll> vec;
        for(int i=1; i<=n; i++) vec.push_back(a[i]), vec.push_back(b[i]);
        sort(vec.begin(), vec.end());
        ans = 1e18;

        ll lsum = 0, lcnt = 0, rsum = accumulate(vec.begin(), vec.end(), 0LL), rcnt = (int)vec.size();
        for(int i=0; i<n*2; i++){
            rsum -= vec[i], rcnt--;
            ans = min(ans, (lcnt * vec[i] - lsum) + (rsum - rcnt * vec[i]) + n);
            lsum += vec[i], lcnt++;
        }
        printf("%lld", ans+base);
        return 0;
    }


}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d", &k, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf(" %c %d %c %d", &C1, &X1, &C2, &X2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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