Submission #54639166

Source Code Expand

#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;
  ll bestscore = INF;
  array<array<tuple<ll, ll, ll, ll, bs>, n * n>, n * n + 1> bestdp;
  for (int weight_d : { 1, 2, 3, 4, 5 }) {
    for (int weight_c : { 1, 3, 5 }) {
      array<array<tuple<ll, 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, INF, 0 };
      Debug("foo");
      dp[0][0] = { 0, 0, -1, 0, 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, rawcost, 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) * weight_d + abs(Grid[i][j]) * weight_c;
            ll rccost = rawcost + (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), rccost, done };
              done.reset(id(i, j));
            }
          }
        }
      }
      pair<ll, int> best = { INF, -1 };
      for (int t = n * n; t >= 0; t--) {
        bool ok = false;
        rep(i, n * n) {
          auto [_, tank, prv, cost, done] = dp[t][i];
          if (cost == INF) continue;
          assert(done.count() == t);
          if (cost < best.first) {
            best = { cost, i };
            ok = true;
          }
        }
        if (ok) break;
      }
      if (bestscore > best.first) {
        bestscore = best.first;
        swap(dp, bestdp);
      }
    }
  }
  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] = bestdp[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] = bestdp[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

Submission Time
Task A - Leveling with a Dump Truck
User a01sa01to
Language C++ 23 (gcc 12.2)
Score 7988936621
Code Size 3483 Byte
Status AC
Exec Time 1817 ms
Memory 31356 KiB

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:61:31: warning: comparison of integer expressions of different signedness: ‘std::size_t’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   61 |           assert(done.count() == t);
      |                  ~~~~~~~~~~~~~^~~~
Main.cpp:82:27: warning: comparison of integer expressions of different signedness: ‘std::size_t’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   82 |       assert(done.count() == t);
      |              ~~~~~~~~~~~~~^~~~

Judge Result

Set Name test_ALL
Score / Max Score 7988936621 / 150000000000
Status
AC × 150
Set Name Test Cases
test_ALL test_0000.txt, test_0001.txt, test_0002.txt, test_0003.txt, test_0004.txt, test_0005.txt, test_0006.txt, test_0007.txt, test_0008.txt, test_0009.txt, test_0010.txt, test_0011.txt, test_0012.txt, test_0013.txt, test_0014.txt, test_0015.txt, test_0016.txt, test_0017.txt, test_0018.txt, test_0019.txt, test_0020.txt, test_0021.txt, test_0022.txt, test_0023.txt, test_0024.txt, test_0025.txt, test_0026.txt, test_0027.txt, test_0028.txt, test_0029.txt, test_0030.txt, test_0031.txt, test_0032.txt, test_0033.txt, test_0034.txt, test_0035.txt, test_0036.txt, test_0037.txt, test_0038.txt, test_0039.txt, test_0040.txt, test_0041.txt, test_0042.txt, test_0043.txt, test_0044.txt, test_0045.txt, test_0046.txt, test_0047.txt, test_0048.txt, test_0049.txt, test_0050.txt, test_0051.txt, test_0052.txt, test_0053.txt, test_0054.txt, test_0055.txt, test_0056.txt, test_0057.txt, test_0058.txt, test_0059.txt, test_0060.txt, test_0061.txt, test_0062.txt, test_0063.txt, test_0064.txt, test_0065.txt, test_0066.txt, test_0067.txt, test_0068.txt, test_0069.txt, test_0070.txt, test_0071.txt, test_0072.txt, test_0073.txt, test_0074.txt, test_0075.txt, test_0076.txt, test_0077.txt, test_0078.txt, test_0079.txt, test_0080.txt, test_0081.txt, test_0082.txt, test_0083.txt, test_0084.txt, test_0085.txt, test_0086.txt, test_0087.txt, test_0088.txt, test_0089.txt, test_0090.txt, test_0091.txt, test_0092.txt, test_0093.txt, test_0094.txt, test_0095.txt, test_0096.txt, test_0097.txt, test_0098.txt, test_0099.txt, test_0100.txt, test_0101.txt, test_0102.txt, test_0103.txt, test_0104.txt, test_0105.txt, test_0106.txt, test_0107.txt, test_0108.txt, test_0109.txt, test_0110.txt, test_0111.txt, test_0112.txt, test_0113.txt, test_0114.txt, test_0115.txt, test_0116.txt, test_0117.txt, test_0118.txt, test_0119.txt, test_0120.txt, test_0121.txt, test_0122.txt, test_0123.txt, test_0124.txt, test_0125.txt, test_0126.txt, test_0127.txt, test_0128.txt, test_0129.txt, test_0130.txt, test_0131.txt, test_0132.txt, test_0133.txt, test_0134.txt, test_0135.txt, test_0136.txt, test_0137.txt, test_0138.txt, test_0139.txt, test_0140.txt, test_0141.txt, test_0142.txt, test_0143.txt, test_0144.txt, test_0145.txt, test_0146.txt, test_0147.txt, test_0148.txt, test_0149.txt
Case Name Status Exec Time Memory
test_0000.txt AC 1649 ms 31196 KiB
test_0001.txt AC 1712 ms 31280 KiB
test_0002.txt AC 1469 ms 31204 KiB
test_0003.txt AC 1610 ms 31168 KiB
test_0004.txt AC 1534 ms 31076 KiB
test_0005.txt AC 1648 ms 31152 KiB
test_0006.txt AC 1493 ms 31216 KiB
test_0007.txt AC 1603 ms 31200 KiB
test_0008.txt AC 1468 ms 31356 KiB
test_0009.txt AC 1661 ms 31284 KiB
test_0010.txt AC 1521 ms 31284 KiB
test_0011.txt AC 1541 ms 31212 KiB
test_0012.txt AC 1461 ms 31168 KiB
test_0013.txt AC 1706 ms 31280 KiB
test_0014.txt AC 1522 ms 31168 KiB
test_0015.txt AC 1548 ms 31216 KiB
test_0016.txt AC 1438 ms 31216 KiB
test_0017.txt AC 1743 ms 31172 KiB
test_0018.txt AC 1647 ms 31172 KiB
test_0019.txt AC 1639 ms 31208 KiB
test_0020.txt AC 1650 ms 31160 KiB
test_0021.txt AC 1486 ms 31212 KiB
test_0022.txt AC 1382 ms 31212 KiB
test_0023.txt AC 1527 ms 31156 KiB
test_0024.txt AC 1551 ms 31212 KiB
test_0025.txt AC 1677 ms 31220 KiB
test_0026.txt AC 1553 ms 31208 KiB
test_0027.txt AC 1681 ms 31168 KiB
test_0028.txt AC 1724 ms 31176 KiB
test_0029.txt AC 1412 ms 31120 KiB
test_0030.txt AC 1502 ms 31124 KiB
test_0031.txt AC 1507 ms 31280 KiB
test_0032.txt AC 1523 ms 31088 KiB
test_0033.txt AC 1609 ms 31084 KiB
test_0034.txt AC 1618 ms 31352 KiB
test_0035.txt AC 1419 ms 31216 KiB
test_0036.txt AC 1633 ms 31204 KiB
test_0037.txt AC 1680 ms 31284 KiB
test_0038.txt AC 1678 ms 31120 KiB
test_0039.txt AC 1510 ms 31200 KiB
test_0040.txt AC 1612 ms 31168 KiB
test_0041.txt AC 1684 ms 31200 KiB
test_0042.txt AC 1541 ms 31208 KiB
test_0043.txt AC 1600 ms 31084 KiB
test_0044.txt AC 1598 ms 31168 KiB
test_0045.txt AC 1587 ms 31356 KiB
test_0046.txt AC 1716 ms 31128 KiB
test_0047.txt AC 1603 ms 31352 KiB
test_0048.txt AC 1582 ms 31164 KiB
test_0049.txt AC 1541 ms 31208 KiB
test_0050.txt AC 1567 ms 31216 KiB
test_0051.txt AC 1688 ms 31204 KiB
test_0052.txt AC 1791 ms 31352 KiB
test_0053.txt AC 1681 ms 31152 KiB
test_0054.txt AC 1626 ms 31196 KiB
test_0055.txt AC 1668 ms 31128 KiB
test_0056.txt AC 1452 ms 31200 KiB
test_0057.txt AC 1618 ms 31280 KiB
test_0058.txt AC 1627 ms 31080 KiB
test_0059.txt AC 1558 ms 31076 KiB
test_0060.txt AC 1463 ms 31276 KiB
test_0061.txt AC 1489 ms 31084 KiB
test_0062.txt AC 1503 ms 31164 KiB
test_0063.txt AC 1622 ms 31124 KiB
test_0064.txt AC 1567 ms 31156 KiB
test_0065.txt AC 1515 ms 31208 KiB
test_0066.txt AC 1601 ms 31200 KiB
test_0067.txt AC 1533 ms 31176 KiB
test_0068.txt AC 1635 ms 31164 KiB
test_0069.txt AC 1538 ms 31128 KiB
test_0070.txt AC 1608 ms 31284 KiB
test_0071.txt AC 1578 ms 31280 KiB
test_0072.txt AC 1696 ms 31148 KiB
test_0073.txt AC 1657 ms 31156 KiB
test_0074.txt AC 1432 ms 31152 KiB
test_0075.txt AC 1513 ms 31216 KiB
test_0076.txt AC 1571 ms 31216 KiB
test_0077.txt AC 1563 ms 31280 KiB
test_0078.txt AC 1659 ms 31172 KiB
test_0079.txt AC 1526 ms 31148 KiB
test_0080.txt AC 1817 ms 31180 KiB
test_0081.txt AC 1653 ms 31208 KiB
test_0082.txt AC 1538 ms 31156 KiB
test_0083.txt AC 1487 ms 31144 KiB
test_0084.txt AC 1551 ms 31356 KiB
test_0085.txt AC 1460 ms 31084 KiB
test_0086.txt AC 1507 ms 31216 KiB
test_0087.txt AC 1627 ms 31276 KiB
test_0088.txt AC 1526 ms 31148 KiB
test_0089.txt AC 1681 ms 31148 KiB
test_0090.txt AC 1451 ms 31192 KiB
test_0091.txt AC 1634 ms 31204 KiB
test_0092.txt AC 1563 ms 31212 KiB
test_0093.txt AC 1518 ms 31148 KiB
test_0094.txt AC 1643 ms 31220 KiB
test_0095.txt AC 1805 ms 31180 KiB
test_0096.txt AC 1433 ms 31216 KiB
test_0097.txt AC 1556 ms 31208 KiB
test_0098.txt AC 1535 ms 31076 KiB
test_0099.txt AC 1588 ms 31160 KiB
test_0100.txt AC 1627 ms 31280 KiB
test_0101.txt AC 1503 ms 31156 KiB
test_0102.txt AC 1604 ms 31216 KiB
test_0103.txt AC 1710 ms 31216 KiB
test_0104.txt AC 1568 ms 31244 KiB
test_0105.txt AC 1556 ms 31212 KiB
test_0106.txt AC 1718 ms 31236 KiB
test_0107.txt AC 1615 ms 31148 KiB
test_0108.txt AC 1671 ms 31164 KiB
test_0109.txt AC 1544 ms 31124 KiB
test_0110.txt AC 1496 ms 31172 KiB
test_0111.txt AC 1600 ms 31284 KiB
test_0112.txt AC 1612 ms 31212 KiB
test_0113.txt AC 1512 ms 31088 KiB
test_0114.txt AC 1646 ms 31140 KiB
test_0115.txt AC 1622 ms 31212 KiB
test_0116.txt AC 1657 ms 31152 KiB
test_0117.txt AC 1613 ms 31148 KiB
test_0118.txt AC 1565 ms 31164 KiB
test_0119.txt AC 1737 ms 31144 KiB
test_0120.txt AC 1440 ms 31216 KiB
test_0121.txt AC 1631 ms 31220 KiB
test_0122.txt AC 1478 ms 31160 KiB
test_0123.txt AC 1527 ms 31152 KiB
test_0124.txt AC 1494 ms 31284 KiB
test_0125.txt AC 1598 ms 31116 KiB
test_0126.txt AC 1477 ms 31152 KiB
test_0127.txt AC 1532 ms 31120 KiB
test_0128.txt AC 1488 ms 31352 KiB
test_0129.txt AC 1638 ms 31280 KiB
test_0130.txt AC 1600 ms 31112 KiB
test_0131.txt AC 1601 ms 31152 KiB
test_0132.txt AC 1488 ms 31080 KiB
test_0133.txt AC 1514 ms 31216 KiB
test_0134.txt AC 1539 ms 31164 KiB
test_0135.txt AC 1643 ms 31208 KiB
test_0136.txt AC 1493 ms 31216 KiB
test_0137.txt AC 1702 ms 31216 KiB
test_0138.txt AC 1545 ms 31284 KiB
test_0139.txt AC 1481 ms 31216 KiB
test_0140.txt AC 1654 ms 31216 KiB
test_0141.txt AC 1430 ms 31148 KiB
test_0142.txt AC 1527 ms 31208 KiB
test_0143.txt AC 1648 ms 31352 KiB
test_0144.txt AC 1496 ms 31152 KiB
test_0145.txt AC 1546 ms 31212 KiB
test_0146.txt AC 1675 ms 31312 KiB
test_0147.txt AC 1490 ms 31216 KiB
test_0148.txt AC 1584 ms 31284 KiB
test_0149.txt AC 1409 ms 31224 KiB