Submission #868147

#TimeUsernameProblemLanguageResultExecution timeMemory
868147Nuraly_SerikbayCoin Collecting (JOI19_ho_t4)C++17
100 / 100
138 ms14016 KiB
//çalışan kazanır// #include "bits/stdc++.h" using namespace std; #define int long long #define pb push_back #define S second #define F first #define all(x) x.begin(),x.end() #define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0) int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}} const int N = 4e5 + 15; const int INF = 1e18; const int MOD = 1e9 + 7; const int MODD = 1070234587ll; const double eps = 0.0001; const int p = 87; int n, x[N], y[N]; int cnt[N][3], dp[2001][2001]; void solution () { cin >> n; for (int i = 1; i <= n * 2; ++ i) cin >> x[i] >> y[i]; int res = 0; for (int i = 1; i <= n * 2; ++ i) { if (1 <= x[i] && x[i] <= n) { if (1 <= y[i] && y[i] <= 2) cnt[x[i]][y[i]] ++; if (y[i] < 1) cnt[x[i]][1] ++, res += (1 - y[i]), y[i] = 1; if (2 < y[i]) cnt[x[i]][2] ++, res += (y[i] - 2), y[i] = 2; } if (x[i] < 1) { res += 1 - x[i]; if (1 <= y[i] && y[i] <= 2) cnt[1][y[i]] ++; if (y[i] < 1) cnt[1][1] ++, res += (1 - y[i]), y[i] = 1; if (2 < y[i]) cnt[1][2] ++, res += (y[i] - 2), y[i] = 2; x[i] = 1; } if (n < x[i]) { res += x[i] - n; if (1 <= y[i] && y[i] <= 2) cnt[n][y[i]] ++; if (y[i] < 1) cnt[n][1] ++, res += (1 - y[i]), y[i] = 1; if (2 < y[i]) cnt[n][2] ++, res += (y[i] - 2), y[i] = 2; x[i] = n; } } int a = 0, b = 0; for (int i = 1; i <= n; ++ i) { a += (cnt[i][1] - 1), b += (cnt[i][2] - 1); if ((a > 0 && b < 0) || (a < 0 && b > 0)) { int mn = min (abs(a), abs(b)); res += mn; if (b < 0) b += mn; else b -= mn; if (a < 0) a += mn; else a -= mn; } res += abs(a) + abs(b); } cout << res; return; } signed main() { // YOSIK(); // srand (time(0)); // freopen ("E.in", "r", stdin); // freopen ("E.out", "w", stdout); int TT = 1;// cin >> TT; for (int i = 1; i <= TT; ++ i) { // cout << "Case " << i << ": "; solution (); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...