oj.uz

답안 #971366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971366 2024-04-28T12:05:07 Z HuyAT Palembang Bridges (APIO15_bridge) C++14
22 / 100
 118 ms 12200 KB 
#include<bits/stdc++.h>
#define newl '\n'

const int MaxN = 1e5 + 10;
const int MaxV = 1e7 + 10;
const long long Inf = 1e18;
const long long Mod = 1e9 + 7;

struct MedianCost{
    std::multiset<int> s,s1;
    int cnt;
    long long t,t1;
    MedianCost() : cnt(0),t(0),t1(0){

    }
    void balance(){
        while((int)s.size() > (cnt + 1) / 2){
            auto it = prev(s.end());
            t -= *it;
            t1 += *it;
            s1.insert(*it);
            s.erase(it);
        }
        while((int)s.size() < (cnt + 1) / 2){
            auto it = s1.begin();
            t += *it;
            t1 -= *it;
            s.insert(*it);
            s1.erase(it);
        }
    }
    void add(int x){
        if(cnt <= 2){
            s.insert(x);
            t += x;
        }else{
            if(x <= *prev(s.end())){
                s.insert(x);
                t += x;
            }else{
                s1.insert(x);
                t1 += x;
            }
        }
        ++cnt;
        balance();
    }
    long long cost(){
        long long mid = *prev(s.end());
        return mid * (long long)s.size() - t + t1 - mid * (long long)s1.size();
    }
};
std::vector<std::pair<int,int>> a{{0,0}};
int k,n;
long long total = 0;

void readData(){
    std::cin >> k >> n;
    for(int i = 1;i <= n;++i){
        char p,q;
        int s,t;
        std::cin >> p >> s >> q >> t;
        if(s > t){
            std::swap(s,t);
        }
        if(p == q){
            total += llabs(s - t);
        }else{
            a.emplace_back(s,t);
        }
    }
    std::sort(a.begin(),a.end());
    n = (int)a.size() - 1;
}
long long first(){
    MedianCost s;
    for(int i = 1;i <= n;++i){
        s.add(a[i].first);
        s.add(a[i].second);
    }
    return s.cost() + total + n;
}
long long solve(){
    if(n == 0){
        return total;
    }
    std::vector<long long> pref(n + 1,0),suff(n + 1,0);
    MedianCost s;
    long long ans = Inf;
    for(int i = 1;i <= n;++i){
        s.add(a[i].first);
        s.add(a[i].second);
        pref[i] = s.cost();
    }
    s = MedianCost();
    for(int i = n;i >= 1;--i){
        s.add(a[i].first);
        s.add(a[i].second);
        suff[i] = s.cost();
    }
    for(int i = 1;i <= n;++i){
        if(i < n && k > 1){
            ans = std::min(ans,pref[i] + suff[i + 1]);
        }
        if(i == n){
            ans = std::min(ans,pref[i]);
        }
    }
    return ans + total + n;
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    std::cout << solve();

    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 488 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 99 ms 12200 KB Output is correct
13 Correct 118 ms 11976 KB Output is correct
14 Correct 107 ms 10956 KB Output is correct
15 Correct 65 ms 7380 KB Output is correct
16 Correct 81 ms 11980 KB Output is correct
17 Correct 99 ms 12172 KB Output is correct
18 Correct 88 ms 12056 KB Output is correct
19 Correct 105 ms 12008 KB Output is correct
20 Correct 102 ms 12188 KB Output is correct
21 Correct 101 ms 11976 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -