Submission #1304908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304908		wjankowski	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	32 ms	2788 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;

#define ll long long
constexpr int maxn = 1e5+2;
int x[2*maxn],y[2*maxn],cnt[2][maxn];
ll ret;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n; cin >> n;
  for(int i=1; i<=2*n; i++)
  {
    cin >> x[i] >> y[i];

    int r,c;
    if(x[i] <= 1) c=1;
    else if(x[i] >= n) c=n;
    else c=x[i];

    if(y[i] >= 2) r=2;
    else r=1;

    ret += abs(x[i]-c)+abs(y[i]-r);
    cnt[r-1][c]++;
  }
  int a=0,b=0;
  for(int i=1; i<=n; i++)
  {
    a += cnt[0][i]-1; b += cnt[1][i]-1;
    if(a > 0 && b < 0)
    {
      int c = min(a,-b);
      ret+=c, a-=c, b+=c;
    }
    else if(b > 0 && a < 0)
    {
      int c = min(-a,b);
      ret+=c, a+=c, b-=c;
    }
    ret += abs(a)+abs(b);
  }
  cout << ret << '\n';
}

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