Submission #20222

#	Time	Username	Problem	Language	Result	Execution time	Memory
20222		erdemkiraz	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	449 ms	14064 KiB

bridge

#include "iostream"
#include "algorithm"
#include "vector"
#include "set"
#include "map"
#include "cstring"
#include "string"
#include "vector"
#include "cassert"
#include "queue"
#include "cstdio"
#include "cstdlib"
#include "ctime"
#include "cmath"
#include "bitset"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 1e5 + 5;

int n, k;
ll pre[N], suf[N];

class node{ public:
    int size;
    ll sum;
    multiset < int > s;
    void init() {
        size = 0;
        sum = 0;
        s.clear();
    }
    int first() {
        return *s.begin();
    }
    int second() {
        return *--s.end();
    }
    int del(int x) {
        s.erase(s.find(x));
        size--;
        sum -= x;
        return x;
    }
    void add(int x) {
        size++;
        sum += x;
        s.insert(x);
    }
    bool fit(int x) {
        return s.size() and x >= *s.begin();
    }
}s[2];

void update(int x) {
    //printf("x = %d\n", x);
    if(s[1].fit(x))
        s[1].add(x);
    else
        s[0].add(x);
    if(s[0].size > s[1].size + 1)
        s[1].add(s[0].del(s[0].second()));
    if(s[1].size > s[0].size)
        s[0].add(s[1].del(s[1].first()));
}

ll get() {
    int p = s[0].second();
    //printf("p = %d\n", p);
    return -s[0].sum + s[1].sum + (ll) (s[0].size - s[1].size) * p;
}

int main () {
    
    scanf("%d %d", &k, &n);
    
    ll add = 0;
    
    vector < ii > v;
    
    for(int i = 1; i <= n; i++) {
        char c1, c2;
        int x, y;
        scanf(" %c %d %c %d", &c1, &x, &c2, &y);
        if(c1 == c2) {
            add += abs(x - y);
        }
        else {
            if(x > y)
                swap(x, y);
            v.push_back({x, y});
        }
    }
    
    sort(v.begin(), v.end(), [&](ii x, ii y){
        return x.first + x.second < y.first + y.second;
    });
    
    n = v.size();
    
    add += n;
    
    for(int i = 1; i <= n; i++) {
        int x = v[i - 1].first, y = v[i - 1].second;
        update(x);
        update(y);
        pre[i] = get();
    }
    
    s[0].init();
    s[1].init();
    
    for(int i = n; i >= 1; i--) {
        int x = v[i - 1].first, y = v[i - 1].second;
        update(x);
        update(y);
        suf[i] = get();
    }
    
//    printf("pre[n] = %d add = %d\n", pre[n], add);
    
    if(k == 1)
        printf("%lld\n", pre[n] + add);
    else {
        ll ans = pre[n];
        for(int i = 1; i < n; i++) {
            //printf("pre[%d] = %d suf[%d] = %d\n", i, pre[i], i + 1, suf[i + 1]);
            ans = min(ans, pre[i] + suf[i + 1]);
        }
        printf("%lld\n", ans + add);
    }
    
    return 0;
    
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:78:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &k, &n);
                           ^
bridge.cpp:87:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d", &c1, &x, &c2, &y);
                                                ^

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