Submission #43544

#	Time	Username	Problem	Language	Result	Execution time	Memory
43544		nonocut	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	74 ms	2584 KiB

bridge

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
#define ll long long
const int maxn = 2e5 + 5;
int n,m,k;
pii p[maxn];
int pos[maxn];
ll solve1(int st, int ft) {
    if(st>ft) return 0;
    int sz = 0;
    ll res = 0;
    for(int i=st;i<=ft;i++) pos[sz++] = p[i].X, pos[sz++] = p[i].Y;
    sort(&pos[0],&pos[sz]);
    int opt = pos[sz/2];
    for(int i=0;i<sz;i++) res += abs(opt-pos[i]);
    return res;
}
ll solve2() {
    ll res = 2e16;
    for(int i=1;i<=n;i++) res = min(res, solve1(1,i-1) + solve1(i,n));
    return res;
}
int main() {
    ll extra = 0;
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++) {
        int x, y; char t1, t2;
        scanf(" %c%d %c%d",&t1,&x,&t2,&y);
        if(t1==t2) extra += abs(x-y);
        else {
            p[++m] = {x,y};
            extra++;
        }
    }
    n = m;
    sort(&p[1],&p[n+1]);
    if(k==1) printf("%lld", solve1(1,n) + extra);
    else printf("%lld", solve2() + extra);
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:28:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&k,&n);
                        ^
bridge.cpp:31:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%d %c%d",&t1,&x,&t2,&y);
                                          ^

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