Submission #54634686

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
  #include "settings/debug.cpp"
  #define _GLIBCXX_DEBUG
#else
  #define Debug(...) void(0)
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;
int main() {
  Debug("aaa");
  constexpr int n = 20;
  int _n;
  cin >> _n;
  Debug("bbb");
  assert(_n == n);
  array<array<int, n>, n> Grid;
  rep(i, n) rep(j, n) cin >> Grid[i][j];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
  #include "settings/debug.cpp"
  #define _GLIBCXX_DEBUG
#else
  #define Debug(...) void(0)
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

int main() {
  Debug("aaa");
  constexpr int n = 20;
  int _n;
  cin >> _n;
  Debug("bbb");
  assert(_n == n);
  array<array<int, n>, n> Grid;
  rep(i, n) rep(j, n) cin >> Grid[i][j];
  Debug("ccc");
  using bs = bitset<n * n>;
  constexpr ll INF = 1e18;
  array<array<tuple<ll, ll, ll, bs>, n * n>, n * n + 1> dp;
  Debug("ddd");
  rep(i, n * n + 1) rep(j, n * n) dp[i][j] = { INF, 0, -1, 0 };
  Debug("foo");
  dp[0][0] = { 0, 0, -1, 0 };
  auto id = [&](int i, int j) {
    return i * n + j;
  };
  rep(t, n * n) {
    rep(pi, n) rep(pj, n) {
      auto [cost, tank, prv, done] = dp[t][id(pi, pj)];
      if (cost == INF) continue;
      rep(i, n) rep(j, n) {
        if (done.test(id(i, j))) continue;
        if (Grid[i][j] < 0 && tank < -Grid[i][j]) continue;
        auto [ncost, ntank, _, ndone] = dp[t + 1][id(i, j)];
        ll ccost = cost + (abs(pi - i) + abs(pj - j)) * (100 + tank) + abs(Grid[i][j]);
        if (ccost < ncost) {
          done.set(id(i, j));
          dp[t + 1][id(i, j)] = { ccost, tank + Grid[i][j], id(pi, pj), done };
          done.reset(id(i, j));
        }
      }
    }
  }
  Debug("bar");
  pair<ll, int> best = { INF, -1 };
  for (int t = n * n; t >= 0; t--) {
    bool ok = false;
    rep(i, n * n) {
      auto [cost, tank, prv, done] = dp[t][i];
      if (cost == INF) continue;
      assert(done.count() == t);
      if (cost < best.first) {
        best = { cost, i };
        ok = true;
      }
    }
    if (ok) break;
  }
  Debug(best);
  vector<string> ans;
  for (int t = n * n; t > 0; --t) {
    auto [cost, tank, prv, done] = dp[t][best.second];
    assert(prv != -1);
    int ni = best.second / n, nj = best.second % n;
    int i = prv / n, j = prv % n;
    if (Grid[ni][nj] != 0) ans.push_back((Grid[ni][nj] < 0 ? "-" : "+") + to_string(abs(Grid[ni][nj])));
    while (ni != i || nj != j) {
      if (i < ni) ans.push_back("D"), ++i;
      if (i > ni) ans.push_back("U"), --i;
      if (j < nj) ans.push_back("R"), ++j;
      if (j > nj) ans.push_back("L"), --j;
    }
    best.second = prv;
  }
  Debug(ans.size());
  reverse(ans.begin(), ans.end());
  for (auto s : ans) cout << s << endl;
  return 0;
}

Submission Info

Compile Error

In file included from /usr/include/c++/12/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function ‘int main()’:
Main.cpp:57:27: warning: comparison of integer expressions of different signedness: ‘std::size_t’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   57 |       assert(done.count() == t);
      |              ~~~~~~~~~~~~~^~~~

Judge Result