Submission #512689

#	Time	Username	Problem	Language	Result	Execution time	Memory
512689		LptN21	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	97 ms	5684 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> ii;
/* CODE BELOW */
const int N = 1e5 + 7, M = 1e9 + 7;
const int oo = 1e9 + 7;
const int MOD = 1e9 + 7;

int n, m, k, t;

ll p[N];

priority_queue<int> pqLeft;
priority_queue<int, vector<int>, greater<int> > pqRight;
ll leftSum = 0, rightSum = 0;

void add(int p) {
    int med = (sz(pqLeft)?pqLeft.top():oo);
    if(p <= med) {
        pqLeft.push(p);
        leftSum+=p;
    } else {
        pqRight.push(p);
        rightSum+=p;
    }

    if(sz(pqRight)+1 < sz(pqLeft)) {
        int trans = pqLeft.top();
        pqLeft.pop(), pqRight.push(trans);

        leftSum-=trans;
        rightSum+=trans;
    } else if(sz(pqRight) > sz(pqLeft)) {
        int trans = pqRight.top();
        pqLeft.push(trans), pqRight.pop();

        leftSum+=trans;
        rightSum-=trans;
    }
}
ll calc() {return rightSum - leftSum;}

bool cmp(ii a, ii b) {
    return a.FF+a.SS<b.FF+b.SS;
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d\n", &k, &n);
    char chA[3], chB[3];
    ll sameSide = 0;
    vector<ii> a;
    int x, y;
    for(int i=1;i<=n;i++) {
        scanf("%s%d%s%d\n", &chA, &x, &chB, &y);
        if(chA[0]!=chB[0]) a.pb(ii(x, y));
        else sameSide+=abs(x - y);
    }
    sort(all(a), cmp); n = sz(a);
    sameSide+=n;

    for(int i=1;i<=n;i++) {
        add(a[i-1].FF);
        add(a[i-1].SS);
        p[i] = calc();
    }

    ll ans = p[n];

    if(k==2) {
        while(sz(pqLeft)) pqLeft.pop();
        while(sz(pqRight)) pqRight.pop();
        leftSum = rightSum = 0;

        for(int i=n;i>0;i--) {
            add(a[i-1].FF);
            add(a[i-1].SS);
            ans = min(ans, p[i-1] + calc());
        }
    }
    printf("%lld", ans + sameSide);

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:80:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[3]' [-Wformat=]
   80 |         scanf("%s%d%s%d\n", &chA, &x, &chB, &y);
      |                ~^           ~~~~
      |                 |           |
      |                 char*       char (*)[3]
bridge.cpp:80:21: warning: format '%s' expects argument of type 'char*', but argument 4 has type 'char (*)[3]' [-Wformat=]
   80 |         scanf("%s%d%s%d\n", &chA, &x, &chB, &y);
      |                    ~^                 ~~~~
      |                     |                 |
      |                     char*             char (*)[3]
bridge.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d%d\n", &k, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
bridge.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%s%d%s%d\n", &chA, &x, &chB, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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