oj.uz

Submission #51401

# Submission time Handle Problem Language Result Execution time Memory
51401 2018-06-17T23:29:39 Z KieranHorgan OBELISK (NOI14_obelisk) C++17
25 / 25
 72 ms 1660 KB 
#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) bRolls = 1;
  if(q==0) aRolls = 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; aRolls-=2;
//  cerr << cur << endl;
  bst = min(bst, cur);


  cur = 0;
  q = (M+1)-q; bRolls+=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; bRolls-=2;
//  cerr << cur << endl;
  bst = min(bst, cur);


  cur = 0;
  p = (M+1)-p; aRolls+=2; cur += 2;
  q = (M+1)-q; bRolls+=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; aRolls-=2;
  q = (M+1)-q; bRolls-=2;
//  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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 3 ms 944 KB Output is correct
4 Correct 2 ms 944 KB Output is correct
5 Correct 2 ms 944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 952 KB Output is correct
2 Correct 4 ms 1072 KB Output is correct
3 Correct 3 ms 1072 KB Output is correct
4 Correct 4 ms 1072 KB Output is correct
5 Correct 3 ms 1072 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1532 KB Output is correct
2 Correct 62 ms 1660 KB Output is correct
3 Correct 62 ms 1660 KB Output is correct
4 Correct 60 ms 1660 KB Output is correct
5 Correct 72 ms 1660 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1660 KB Output is correct
2 Correct 65 ms 1660 KB Output is correct
3 Correct 58 ms 1660 KB Output is correct
4 Correct 63 ms 1660 KB Output is correct
5 Correct 59 ms 1660 KB Output is correct