Submission #846166

#	Time	Username	Problem	Language	Result	Execution time	Memory
846166		vjudge1	ČVENK (COI15_cvenk)	C++17	22 / 100	74 ms	31568 KiB

cvenk

#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define int long long
using namespace std;

const int inf = 2e18 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int32_t main(){
  //freopen("in.txt","r", stdin);
  int n;
  cin>>n;
  vector<array<int, 2> > a(n);
  for(int i = 0; i < n; i++){
    cin>>a[i][0]>>a[i][1];
  }

  if(n == 2){
    array<int, 2> f = a[0];
    array<int, 2> s = a[1];
    int mnbt = 0;
    int ans = 0;

    while(f != s && mnbt < 30){
      if(f[0]&(1 << mnbt) && f[0] > (1 << mnbt)){
         ans += (1 << mnbt);
         f[0] -= (1 << mnbt);
      }
      if(f[1]&(1 << mnbt) && f[1] > (1 << mnbt)){
         ans += (1 << mnbt);
         f[1] -= (1 << mnbt);
      }
      if(s[0]&(1 << mnbt) && s[0] > (1 << mnbt)){
         ans += (1 << mnbt);
         s[0] -= (1 << mnbt);
      }
      if(s[1]&(1 << mnbt) && s[1] > (1 << mnbt)){
         ans += (1 << mnbt);
         s[1] -= (1 << mnbt);
      }

      mnbt++;
    }
    if(f == s) cout<<ans<<endl;
    else{
        if(f[0] < f[1]){
            ans += f[0];
            f[0] = 0;
        }
        else{
            ans += f[1];
            f[1] = 0;
        }

        if(s[0] < s[1]){
            ans += s[0];
            s[0] = 0;
        }
        else{
            ans += s[1];
            s[1] = 0;
        }

        cout<<abs(f[0] - s[0]) + abs(f[1] - s[1]) + ans<<endl;
    }
    return 0;
  }

  vector<vector<vector<int> > > go(500, vector<vector<int> >(500, vector<int>(2)));
  int sum = 0, mxx = 0, mxy = 0;
  for(int i = 0; i < n; i++){
    int x = a[i][0], y = a[i][1];
    sum = (sum + x + y);
    mxx = max(mxx, x);
    mxy = max(mxy, y);

    while(x > 0 || y > 0){
        if(x == 0){
            go[x][y-1][1]++;
            y--;
        }
        else if(y == 0){
            go[x-1][y][0]++;
            x--;
        }
        else if((x-1)&y){
            go[x][y-1][1]++;
            y--;
        }
        else{
            go[x-1][y][0]++;
            x--;
        }
    }
  }

  int ans = sum;
  queue<array<int, 3> > q;
  q.push({0, 0, sum});
  while(!q.empty()){
    int x = q.front()[0], y = q.front()[1], val = q.front()[2];
    q.pop();
    ans = min(ans, val);

    if(!((x+1)&y) && x < mxx){
        q.push({x+1, y, val - go[x][y][0] + (n - go[x][y][0])});
    }
    if(!(x&(y+1)) && y < mxy){
        q.push({x, y+1, val - go[x][y][1] + (n - go[x][y][1])});
    }
  }

  cout<<ans<<endl;
  return 0;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40