oj.uz

답안 #972158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972158 2024-04-30T07:55:18 Z Halym2007 Palembang Bridges (APIO15_bridge) C++17
0 / 100
 15 ms 13448 KB 
#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()

const int N = 2e5 + 1;

using namespace std;

ll n, k, x[N], y[N], ans, p[N], q[N], mn = 1e15, cnt, cnt1, sum, sum1;

char s[N], d[N];

vector <pii> v;
vector <int> v1;

multiset <int> l, r;

bool cmp(pii a, pii b){
	if(a.ff + a.ss <= b.ff + b.ss) return 1;
	else return 0;
}

void med(int a){
	if(l.empty()) {
		l.insert(a);
		sum += a;
		return;
	}
	if((int)l.sz <= (int)r.sz){
		auto t = r.begin();
		ll aa = *t;
		if(a > aa) {
			sum += aa;
			l.insert(aa);
			sum1 += a;
			sum1 -= aa;
			r.erase(aa);
			r.insert(a);
		}
		else{
			l.insert(a);
			sum += a;
		}
	}
	else{
		auto t = l.end();
		t--;
		ll aa = *t;
		if(a < aa){
			sum -= (ll)aa;
			sum += a;
			l.erase(aa);
			l.insert(a);
			r.insert(aa);
			sum1 += aa;
		}
		else{
			r.insert(a);
			sum1 += a;
		}
	}
}

int main() {
//	freopen ("input.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> k >> n;
    for(int i = 1; i <= n; i++){
    	cin >> s[i] >> x[i] >> d[i] >> y[i];
    	if(s[i] != d[i]){
    		ans++;
    		v.pb({x[i],y[i]});
    	}
    	else ans += abs(x[i]-y[i]);
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < (int)v.sz; i++){
    	med(v[i].ff);
		med(v[i].ss);
		auto t = l.end();
    	t--;
    	int med1 = *t;
    	p[i] = (cnt*med1 - sum) + (sum1 - cnt1*med1);
    }
    cnt = sum = cnt1 = sum1 = 0;
    l.clear();r.clear();
    for(int i = (int)v.sz-1; i >= 0; i--){
		med(v[i].ff);
		med(v[i].ss);
		auto t = l.end();
    	t--;
    	int med1 = *t;
    	q[i] = (cnt*med1 - sum) + (sum1 - cnt1*med1);
    }
    for(int i = 0; i < (int)v.sz; i++){
    	mn = min(mn, p[i] + q[i+1]);
    }
    mn = min(mn,q[0]);
//    cout << sum << " " << sum1;
//    return 0;a
    if(k == 1) mn = q[0];
    assert (q[0] == p[(int)v.sz - 1]);
    cout << mn + ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Runtime error 14 ms 13120 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Runtime error 15 ms 13148 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Runtime error 11 ms 13448 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6608 KB Output is correct
3 Runtime error 8 ms 13404 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Runtime error 8 ms 13404 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -