# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
512689 | LptN21 | Palembang Bridges (APIO15_bridge) | C++14 | 97 ms | 5684 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define PI acos(-1.0)
#define eps 1e-9
#define FF first
#define SS second
// VECTOR (6)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() );
// BIT (6)
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SUBSET(big, small) (((big)&(small))==(small))
#define MINBIT(x) (x)&(-x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> ii;
/* CODE BELOW */
const int N = 1e5 + 7, M = 1e9 + 7;
const int oo = 1e9 + 7;
const int MOD = 1e9 + 7;
int n, m, k, t;
ll p[N];
priority_queue<int> pqLeft;
priority_queue<int, vector<int>, greater<int> > pqRight;
ll leftSum = 0, rightSum = 0;
void add(int p) {
int med = (sz(pqLeft)?pqLeft.top():oo);
if(p <= med) {
pqLeft.push(p);
leftSum+=p;
} else {
pqRight.push(p);
rightSum+=p;
}
if(sz(pqRight)+1 < sz(pqLeft)) {
int trans = pqLeft.top();
pqLeft.pop(), pqRight.push(trans);
leftSum-=trans;
rightSum+=trans;
} else if(sz(pqRight) > sz(pqLeft)) {
int trans = pqRight.top();
pqLeft.push(trans), pqRight.pop();
leftSum+=trans;
rightSum-=trans;
}
}
ll calc() {return rightSum - leftSum;}
bool cmp(ii a, ii b) {
return a.FF+a.SS<b.FF+b.SS;
}
signed main() {
//freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
//fastIO;
scanf("%d%d\n", &k, &n);
char chA[3], chB[3];
ll sameSide = 0;
vector<ii> a;
int x, y;
for(int i=1;i<=n;i++) {
scanf("%s%d%s%d\n", &chA, &x, &chB, &y);
if(chA[0]!=chB[0]) a.pb(ii(x, y));
else sameSide+=abs(x - y);
}
sort(all(a), cmp); n = sz(a);
sameSide+=n;
for(int i=1;i<=n;i++) {
add(a[i-1].FF);
add(a[i-1].SS);
p[i] = calc();
}
ll ans = p[n];
if(k==2) {
while(sz(pqLeft)) pqLeft.pop();
while(sz(pqRight)) pqRight.pop();
leftSum = rightSum = 0;
for(int i=n;i>0;i--) {
add(a[i-1].FF);
add(a[i-1].SS);
ans = min(ans, p[i-1] + calc());
}
}
printf("%lld", ans + sameSide);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |