Submission #1311333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311333		ssseul	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	72 ms	9484 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
#define el '\n'
 
const int maxN = 2005;
const int maxM = 205;
const int base = 311;
const int MOD = 1e9+7;
const int INF = 1e18;
const int NEG_INF = -1e18;
const int MAX_DAYS = 1000;
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
 
int n, m, k, q, p, x, l;
// string S, T;
int S;
int dist[maxN][maxN], min_dist[maxN][maxN];
int par[maxN], deg[maxN], color[maxN];
bool visited[maxN];
int yard[maxN];
vector<pii> g[maxN], g_per[maxN];
string grid[maxN];

struct Citizen {
    int id;
    int st, ed;
};

bool cmpCitizen(Citizen a, Citizen b){
    return (a.st + a.ed) < (b.st + b.ed);
}

// Prefix sum : S[i]
// => sum = S[i] - S[j-1]; len = i - (j-1);
// a <= len <= b
// i - b <= j - 1 <= i - a

vector<Citizen> Citizens;

struct MedianTracker {
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    int sumL = 0;
    int sumR = 0;

    void add(int x){
        if(max_heap.empty() || x <= max_heap.top()){
            max_heap.push(x);
            sumL += x;
        } else {
            min_heap.push(x);
            sumR += x;
        }

        while(max_heap.size() > min_heap.size() + 1){
            int x = max_heap.top(); max_heap.pop();
            min_heap.push(x);
            sumR += x;
            sumL -= x;
        } 
        while(max_heap.size() < min_heap.size()) {
            int x = min_heap.top(); min_heap.pop();
            max_heap.push(x);
            sumL += x;
            sumR -= x;
        }
    }

    int getCost(){
        int median = max_heap.top();
        int costL = median * max_heap.size() - sumL;
        int costR = sumR - median * min_heap.size();
        return costL + costR;
    }
};

int solveK1(){
    vector<int> v;
    for(auto c : Citizens){
        v.push_back(c.st);
        v.push_back(c.ed);
    }
    sort(all(v));
    int median = v[v.size()/2];
    int ans = 0;
    for(int i = 0; i < v.size(); i++){
        ans += abs(v[i] - median);
    }
    return ans;
}

int solveK2(){
    int m = Citizens.size();
    if (m == 0) return 0;

    MedianTracker mtl;
    vector<int> costL(m+5, 0);
    for(int i = 0; i < m; i++){
        mtl.add(Citizens[i].st);
        mtl.add(Citizens[i].ed);
        costL[i] = mtl.getCost();
    }

    MedianTracker mtr;
    vector<int> costR(m+5, 0);
    for(int i = m - 1; i >= 0; i--){
        mtr.add(Citizens[i].st);
        mtr.add(Citizens[i].ed);
        costR[i] = mtr.getCost();
    }

    int ans = INF;

    for(int i = 0; i < m; i++){
        ans = min(ans, costL[i] + costR[i+1]);
    }

    return ans;
}

void run_test() {
    cin >> k >> n;


    int baseCost = 0;

    for(int i = 1; i <= n; i++){
        int st, ed;
        char P, Q;
        cin >> P >> st >> Q >> ed;
        if(P == Q) baseCost += abs(st-ed);
        else Citizens.push_back({i,st,ed});
    }
    baseCost += Citizens.size();
    sort(all(Citizens), cmpCitizen);

    int ans;

    if(k == 1)
        ans = solveK1();
    else   
        ans = solveK2();
    
    cout << ans + baseCost;
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("hayfeast.in", "r", stdin); 
    // freopen("hayfeast.out", "w", stdout);
    int test = 1;
    // cin >> test;
    while (test-- > 0)
    {
        run_test();
    }
}

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