#include <bits/stdc++.h>
using namespace std;
using ll =long long;
using pi=pair<int,int>;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first + a.second < b.first + b.second;
}
int k,n;
multiset<int> low,high;
vector<char> zone1(n), zone2(n);
vector<int> home(n), office(n);
ll lsum=0, rsum=0;
void insert(int x)
{
int median=*low.rbegin();
if(x<=median)
{
low.insert(x);
lsum+=x;
if(low.size()>high.size()+1)
{
int tomove=*low.rbegin();
low.erase(low.find(*low.rbegin()));
high.insert(tomove);
lsum-=tomove;
rsum+=tomove;
}
}
else
{
high.insert(x);
rsum+=x;
if(high.size()>low.size())
{
int tomove=*high.begin();
low.insert(*high.begin());
high.erase(high.find(*high.begin()));
lsum+=tomove;
rsum-=tomove;
}
}
}
ll pref[100001];
int main()
{
//freopen("hayfeast.in", "r", stdin);
// the following line creates/overwrites the output file
//freopen("hayfeast.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
ll same_side = 0;
vector<pair<int, int>> v = {{0, 0}};
cin>>k>>n;
/*
* k=bridges
* n=people
*/
/*
If home and office are in the same zone, the distance is simply abs(office[i]-home[i])
* Otherwise, try to split the prefix of people that will use the first bridge. In both segments the bridge should be in median
* Use sliding median to update the median
* Keep a sum of elements in low and high in order to calculate the answer efficently
*/
for(int i=0; i<n; i++)
{
cin>>zone1[i]>>home[i]>>zone2[i]>>office[i];
if(zone1[i]==zone2[i]) same_side+=abs(home[i]-office[i]);
else v.push_back({home[i], office[i]});
}
sort(v.begin(), v.end(), cmp);
n=v.size()-1;
same_side+=n;
lsum=rsum=0;
for(int i=1; i<=n; i++)
{
insert(v[i].first);
insert(v[i].second);
pref[i]=rsum-lsum;
}
ll ans=pref[n];
if(k==2)
{
while(low.size()) low.erase(low.begin());
while(high.size()) high.erase(high.begin());
lsum = rsum = 0;
for (int i = n; i; i--) {
insert(v[i].first);
insert(v[i].second);
ans = min(ans, rsum - lsum + pref[i - 1]);
}
}
cout << same_side + ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
