Submission #51396

#	Time	Username	Problem	Language	Result	Execution time	Memory
51396		KieranHorgan	OBELISK (NOI14_obelisk)	C++17	5 / 25	84 ms	1440 KiB

obelisk

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())

int K, M;
vector<pair<int, int>> holes[505];
int ans[505][105];

int calc(int a, int b, int p, int q) {
  if(a==p && b==q) return 0;
  if(M==1)
    return abs(a-p)+abs(b-q);

//  cerr << a << "," << b << " " << p << "," << q << endl;
  p -= a;
  a = 0;

  q -= b;
  b = 0;
  
  p = abs(p);
  q = abs(q);

  int res = 0;
  int x;
  
  int aRolls = p/(M+1);
  res += aRolls*2;
  p -= aRolls*(M+1);

  int bRolls = q/(M+1);
  res += bRolls*2;
  q -= bRolls*(M+1);
//  cerr << p << "," << q << ": " << res << endl;

  if(p==0) aRolls = 1;
  if(q==0) bRolls = 1;

  int bst = 1ll<<60;
  int cur;

  cur = 0;
  if(aRolls != 0) {
    cur += q;
  } else {
    cur += q+2;
  }
  if(bRolls != 0) {
    cur += p;
  } else {
    cur += p+2;
  }
//  cerr << cur << endl;
  bst = min(bst, cur);


  cur = 0;
  p = (M+1)-p; aRolls+=2; cur += 2;
  if(aRolls != 0) {
    cur += q;
  } else {
    cur += q+2;
  }
  if(bRolls != 0) {
    cur += p;
  } else {
    cur += p+2;
  }
  p = (M+1)-p;
//  cerr << cur << endl;
  bst = min(bst, cur);


  cur = 0;
  q = (M+1)-q; aRolls+=2; cur += 2;
  if(aRolls != 0) {
    cur += q;
  } else {
    cur += q+2;
  }
  if(bRolls != 0) {
    cur += p;
  } else {
    cur += p+2;
  }
  q = (M+1)-q;
//  cerr << cur << endl;
  bst = min(bst, cur);


  cur = 0;
  p = (M+1)-p; aRolls+=2; cur += 2;
  q = (M+1)-q; aRolls+=2; cur += 2;
  if(aRolls != 0) {
    cur += q;
  } else {
    cur += q+2;
  }
  if(bRolls != 0) {
    cur += p;
  } else {
    cur += p+2;
  }
  p = (M+1)-p;
  q = (M+1)-q;
//  cerr << cur << endl;
  bst = min(bst, cur);

  res += bst;
//  cerr << p << "," << q << ": " << res << endl;

//  cerr << endl;
  return res;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);

  cin >> K >> M;
  int a, b;
  cin >> a >> b;
  holes[0].push_back({a, b});
  cin >> a >> b;
  holes[K].push_back({a, b});

  memset(ans, 127, sizeof(ans));
  ans[0][0] = 0;
  for(int f = 1; f < K; f++) {
    int h;
    cin >> h;
    for(int i = 0; i < h; i++) {
      cin >> a >> b;
      holes[f].push_back({a, b});
    }
  }

  for(int f = 0; f < K; f++) {
    int j = 0;
    for(auto h: holes[f]) {
      int i = 0;
      for(auto nxt: holes[f+1]) {
        ans[f+1][i] = min(ans[f+1][i], ans[f][j] + calc(h.first, h.second, nxt.first, nxt.second));
        i++;
      }
      j++;
    }
  }
  cout << ans[K][0] << endl;
}

Compilation message (stderr)

obelisk.cpp: In function 'long long int calc(long long int, long long int, long long int, long long int)':
obelisk.cpp:33:7: warning: unused variable 'x' [-Wunused-variable]
   int x;
       ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7