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>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
#define bye exit(0);
using namespace std;
typedef long long ll;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
//ostream& operator<<(ostream &os, pair<int, char> x){
// os << "[" << x.ff << ", " << x.ss << "]";
//}
const int mxn = (int)(1e5) + 10;
int dp[mxn][3];
void show(int n){
loop(j,1,3){
loop(i,1,n+1){
cout << dp[i][3-j] << ' ';
}
cout << endl;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.txt", "r", stdin);
int n, m;
cin >> n;
m = n << 1;
ll ans = 0;
loop(i,1,n+1){
loop(j,1,3){
dp[i][j]++;
}
}
loop(i,0,m){
int x, y;
cin >> x >> y;
if(y >= 2){
ans += y - 2;
if(x <= 1){
ans += 1 - x;
dp[1][2]--;
}
else if(x >= n){
ans += x - n;
dp[n][2]--;
}
else{
dp[x][2]--;
}
}
else{
ans += 1 - y;
if(x <= 1){
ans += 1 - x;
dp[1][1]--;
}
else if(x >= n){
ans += x - n;
dp[n][1]--;
}
else{
dp[x][1]--;
}
}
}
// op(ans)
// show(n);
loop(i,1,n+1){
// don't lend / borrow too much
if(dp[i][1] > 0 && dp[i][2] < 0){
int trans = min(abs(dp[i][1]), abs(dp[i][2]));
ans += trans;
dp[i][1] -= trans;
dp[i][2] += trans;
}
else if(dp[i][1] < 0 && dp[i][2] > 0){
int trans = min(abs(dp[i][1]), abs(dp[i][2]));
ans += trans;
dp[i][1] += trans;
dp[i][2] -= trans;
}
// lend from next row
loop(j,1,3){
dp[i+1][j] += dp[i][j];
ans += abs(dp[i][j]);
dp[i][j] -= dp[i][j];
}
// op(ans)
// show(n);
}
cout << ans;
}
/*
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |