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][2];
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;
}
/*
*/
Compilation message (stderr)
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:44:20: warning: iteration 1 invokes undefined behavior [-Waggressive-loop-optimizations]
44 | dp[i][j]++;
| ~~~~~~~^
joi2019_ho_t4.cpp:7:40: note: within this loop
7 | #define loop(i,a,b) for(int i = (a); i < (b); i ++)
| ^
joi2019_ho_t4.cpp:43:9: note: in expansion of macro 'loop'
43 | loop(j,1,3){
| ^~~~
joi2019_ho_t4.cpp:97:24: warning: iteration 1 invokes undefined behavior [-Waggressive-loop-optimizations]
97 | dp[i+1][j] += dp[i][j];
| ~~~~~~~~~~~^~~~~~~~~~~
joi2019_ho_t4.cpp:7:40: note: within this loop
7 | #define loop(i,a,b) for(int i = (a); i < (b); i ++)
| ^
joi2019_ho_t4.cpp:96:9: note: in expansion of macro 'loop'
96 | loop(j,1,3){
| ^~~~
joi2019_ho_t4.cpp:44:20: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
44 | dp[i][j]++;
| ~~~~~~~^
joi2019_ho_t4.cpp:44:20: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
joi2019_ho_t4.cpp:61:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
61 | dp[x][2]--;
| ~~~~~~~^
joi2019_ho_t4.cpp:61:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
joi2019_ho_t4.cpp:58:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
58 | dp[n][2]--;
| ~~~~~~~^
joi2019_ho_t4.cpp:58:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
joi2019_ho_t4.cpp:54:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
54 | dp[1][2]--;
| ~~~~~~~^
joi2019_ho_t4.cpp:54:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
joi2019_ho_t4.cpp:83:35: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
83 | if(dp[i][1] > 0 && dp[i][2] < 0){
| ~~~~~~~^
joi2019_ho_t4.cpp:87:22: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
87 | dp[i][2] += trans;
| ~~~~~~~~~^~~~~~~~
joi2019_ho_t4.cpp:89:40: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
89 | else if(dp[i][1] < 0 && dp[i][2] > 0){
| ~~~~~~~^
joi2019_ho_t4.cpp:93:22: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
93 | dp[i][2] -= trans;
| ~~~~~~~~~^~~~~~~~
joi2019_ho_t4.cpp:97:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
97 | dp[i+1][j] += dp[i][j];
| ~~~~~~~~~~~^~~~~~~~~~~
joi2019_ho_t4.cpp:97:34: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
97 | dp[i+1][j] += dp[i][j];
| ~~~~~~~^
joi2019_ho_t4.cpp:97:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
97 | dp[i+1][j] += dp[i][j];
| ~~~~~~~~~~~^~~~~~~~~~~
joi2019_ho_t4.cpp:98:31: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
98 | ans += abs(dp[i][j]);
| ~~~~~~~^
joi2019_ho_t4.cpp:99:22: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
99 | dp[i][j] -= dp[i][j];
| ~~~~~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |