oj.uz

Submission #20221

# Submission time Handle Problem Language Result Execution time Memory
20221 2016-04-16T13:24:30 Z erdemkiraz Palembang Bridges (APIO15_bridge) C++14
0 / 100
 0 ms 3588 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Runtime error 0 ms 3588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Runtime error 0 ms 3588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Runtime error 0 ms 3588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Runtime error 0 ms 3588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3588 KB Output is correct
2 Correct 0 ms 3588 KB Output is correct
3 Correct 0 ms 3588 KB Output is correct
4 Runtime error 0 ms 3588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -