oj.uz

Submission #846166

# Submission time Handle Problem Language Result Execution time Memory
846166 2023-09-07T12:04:22 Z vjudge1 ČVENK (COI15_cvenk) C++17
22 / 100
 74 ms 31568 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 28240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 15696 KB Output is correct
2 Correct 62 ms 15696 KB Output is correct
3 Correct 45 ms 15696 KB Output is correct
4 Correct 45 ms 15572 KB Output is correct
5 Correct 57 ms 15696 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 31568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -