Submission #20221

#	Time	Username	Problem	Language	Result	Execution time	Memory
20221		erdemkiraz	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	0 ms	3588 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;
const int M = 100;

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

void up(int l, int r, int x) {
    for(int i = l; i <= r; i++)
        cnt[i] += x;
}

void upIt(int l, int r, int x) {
    for(int i = l; i <= r; i++)
        cnt[i] += i * x;
}

ll get() {
    ll ans = 1e18;
    for(int i = 0; i < M; i++)
        ans = min(ans, cnt[i]);
    return ans;
}

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;
        up(0, x, +x);
        up(x + 1, M - 1, -x);
        up(0, y, +y);
        up(y + 1, M - 1, -y);
        upIt(0, x, -2);
        upIt(y + 1, M - 1, +2);
        pre[i] = get();
    }
    
    memset(cnt, 0, sizeof(cnt));
    
    for(int i = n; i >= 1; i--) {
        int x = v[i - 1].first, y = v[i - 1].second;
        up(0, x, +x);
        up(x + 1, M - 1, -x);
        up(0, y, +y);
        up(y + 1, M - 1, -y);
        upIt(0, x, -2);
        upIt(y + 1, M - 1, +2);
        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++)
            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:47: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:56: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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37