#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[200005][3];
int main()
{
int n;
cin>>n;
ll ans = 0;
vector<array<int,2>>a(2*n);
for(int i=0;i<2*n;i++){
int x,y;
cin>>x>>y;
a[i][0] = x;
if(y>=2)ans+=y-2;
else ans+=1-y;
a[i][1] = y>=2;
}
sort(a.begin(),a.end());
int m = 2*n;
for(int i=0;i<m;i++)ans+=abs(a[i][0] - (i/2 + 1));
//cout<<ans<<'\n';
//obs that matching in increasing order of x is optimal
//problem reduced to how to optimize for y
//0 match with 1 = + 1 cost
vector<int>c0,c1;
for(int i=0;i<m;i++){
int j = i;
while(j+1<m && a[j+1][0] == a[i][0])j++;
vector<int>b(2,0);
for(int k=i;k<=j;k++)b[a[k][1]]++;
c0.push_back(b[0]);
c1.push_back(b[1]);
i=j;
}
/*
for(int x:c0)cout<<x<<" ";
cout<<'\n';
for(int x:c1)cout<<x<<" ";
cout<<'\n';
*/
n = c0.size();
for(int i=0;i<=n;i++)dp[i][0] = dp[i][1] = 1e18;
dp[0][0] = 0;
int cur = 0;
for(int i=0;i<n;i++){
//cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<'\n';
vector<int>b(2,0);
int ncur = cur+c0[i]+c1[i];
for(int j=cur;j<ncur;j++)b[j%2]++;
if(c0[i]+c1[i] == 1){ //corner case
ll cc0 = cur%2?dp[i][1] : dp[i][0];
ll cc1 = cur%2?dp[i][0] : dp[i][1];
dp[i+1][0] = min(dp[i+1][0], min(1-c0[i]+cc0,1-c1[i]+cc1));
if(ncur%2){//swap in a zero
//x0
//x = 0 does nothing
dp[i+1][1] = min(dp[i+1][1],1-c0[i] + cc1);
}
}else{
dp[i+1][0] = min(dp[i+1][0],dp[i][0] + max(c0[i] - b[0],c1[i] - b[1]));
b[0]--;b[1]++;
dp[i+1][0] = min(dp[i+1][0],dp[i][1] + max(c0[i] - b[0],c1[i] - b[1]));
b[0]++;b[1]--;
if(ncur%2){
b[0]++;
b[1]--;
dp[i+1][1] = min(dp[i+1][1],dp[i][0] + max(c0[i] - b[0],c1[i] - b[1]));
b[0]--;b[1]++;
dp[i+1][1] = min(dp[i+1][1],dp[i][1] + max(c0[i] - b[0],c1[i] - b[1]));
b[0]++;b[1]--;
}
}
cur = ncur;
}
cout<<ans + min(dp[n][0],dp[n][1]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
