Submission #846133

#	Time	Username	Problem	Language	Result	Execution time	Memory
846133		vjudge1	ČVENK (COI15_cvenk)	C++17	22 / 100	76 ms	33360 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];
  }
  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