Submission #890254

#	Time	Username	Problem	Language	Result	Execution time	Memory
890254		bleahbleah	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	37 ms	5468 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e6 + 5;

int v[nmax][2];

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n;
  cin >> n;
  
  ll cost = 0;
  
  for(int i = 1, x, y; i <= 2 * n; i++) {
    cin >> x >> y;
    cost += min(abs(y - 1), abs(y - 2));
    if(x <= 1) cost += 1 - x, x = 1;
    else if(x >= n) cost += x - n, x = n; 
    
    if(y <= 1) v[x][0]++;
    else v[x][1]++;
  }
  
  int cnt[2] = {0, 0};
  
  for(int i = 1; i <= n; i++) {
    cnt[0] += v[i][0];
    cnt[1] += v[i][1];
    
    cnt[0]--;
    cnt[1]--;
    
    while(cnt[0] > 0 && cnt[1] < 0) cnt[0]--, cnt[1]++, cost++;
    while(cnt[1] > 0 && cnt[0] < 0) cnt[1]--, cnt[0]++, cost++;
    
    cost += abs(cnt[0]) + abs(cnt[1]);
  }
  
  cout << cost << '\n';
  
  
}

/**
      nu mancati chipsuri
-- gen, pe bune, sa nu mancati chipsuri
-- surse foarte verificate
-- eu unul nu mai bag chipsuri inainte de concurs
*/

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63