Submission #1196271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196271		mmaiti	Text editor (CEOI24_editor)	C++20	45 / 100	4102 ms	290632 KiB

Main

#include <bits/stdc++.h>
#include <queue>
#include <tuple>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define sll set<ll>
#define usll unordered_set<ll>
#define vb vector<bool>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>
#define lll tuple<ll, ll, ll>

/*const ll INF = 1e13;*/
ll N;
pll s, f;
vll L(N);
ll DK() {
  map<pll, ll> m;
  m[{s.first, s.second}] = 0;
  priority_queue<lll, vector<lll>, greater<lll>> pq;
  pq.push(make_tuple(0, s.first, s.second));
  while (!pq.empty()) {
    auto [c, x, y] = pq.top();
    pq.pop();
    if (m.find({x, y}) != m.end() && m[{x, y}] < c)
      continue;
    if (x == f.first && y == f.second) {
      break;
    }
    vector<lll> moves;
    // left special
    if (y == 0 && x - 1 >= 0) {
      moves.push_back(make_tuple(1, x - 1, L[x - 1]));
    }
    // right special
    if (y == L[x] && x + 1 < N) {
      moves.push_back(make_tuple(1, x + 1, 0));
    }
    // move along the same line
    sll tp = {0, s.second, f.second, L[x]};
    for (int i : tp) {
      moves.push_back(make_tuple(abs(y - i), x, i));
    }

    // move up or down
    for (int dx : {-1, 1}) {
      if (x + dx >= 0 && x + dx < N) {
        sll chk = {0, s.second, f.second, L[x + dx]};
        if (y > L[x + dx]) {
          moves.push_back(make_tuple(1, x + dx, L[x + dx]));
        }
        /*else if (chk.find(y) == chk.end()) {*/
        /*  for (int i : chk) {*/
        /*    moves.push_back(make_tuple(1 + abs(y - i), x + dx, i));*/
        /*  }*/
        /*} */
        else {
          moves.push_back(make_tuple(1, x + dx, y));
        }
      }
    }

    for (auto i : moves) {
      int ct, nx, ny;
      tie(ct, nx, ny) = i;
      if (m.find({nx, ny}) == m.end() || m[{x, y}] + ct < m[{nx, ny}]) {
        m[{nx, ny}] = m[{x, y}] + ct;
        pq.push(make_tuple(m[{nx, ny}], nx, ny));
      }
    }
  }
  return m[{f.first, f.second}];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  cin >> N;
  L.resize(N);
  cin >> s.first >> s.second >> f.first >> f.second;
  --s.first;
  --s.second;
  --f.first;
  --f.second;
  for (int i = 0; i < N; i++) {
    cin >> L[i];
  }
  cout << DK() << "\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44