Submission #54636749

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 }) {
    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 7974393661
Code Size 3480 Byte
Status AC
Exec Time 1473 ms
Memory 31340 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 7974393661 / 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 1325 ms 31332 KiB
test_0001.txt AC 1373 ms 31200 KiB
test_0002.txt AC 1198 ms 31120 KiB
test_0003.txt AC 1310 ms 31152 KiB
test_0004.txt AC 1248 ms 31200 KiB
test_0005.txt AC 1327 ms 31148 KiB
test_0006.txt AC 1213 ms 31216 KiB
test_0007.txt AC 1293 ms 31144 KiB
test_0008.txt AC 1193 ms 31152 KiB
test_0009.txt AC 1344 ms 31200 KiB
test_0010.txt AC 1231 ms 31152 KiB
test_0011.txt AC 1250 ms 31080 KiB
test_0012.txt AC 1193 ms 31080 KiB
test_0013.txt AC 1378 ms 31212 KiB
test_0014.txt AC 1227 ms 31160 KiB
test_0015.txt AC 1242 ms 31200 KiB
test_0016.txt AC 1155 ms 31280 KiB
test_0017.txt AC 1402 ms 31156 KiB
test_0018.txt AC 1339 ms 31080 KiB
test_0019.txt AC 1315 ms 31148 KiB
test_0020.txt AC 1333 ms 31080 KiB
test_0021.txt AC 1215 ms 31160 KiB
test_0022.txt AC 1125 ms 31164 KiB
test_0023.txt AC 1227 ms 31116 KiB
test_0024.txt AC 1255 ms 31332 KiB
test_0025.txt AC 1348 ms 31148 KiB
test_0026.txt AC 1253 ms 31332 KiB
test_0027.txt AC 1360 ms 31120 KiB
test_0028.txt AC 1389 ms 31044 KiB
test_0029.txt AC 1163 ms 31164 KiB
test_0030.txt AC 1211 ms 31152 KiB
test_0031.txt AC 1219 ms 31148 KiB
test_0032.txt AC 1229 ms 31116 KiB
test_0033.txt AC 1300 ms 31148 KiB
test_0034.txt AC 1314 ms 31152 KiB
test_0035.txt AC 1153 ms 31220 KiB
test_0036.txt AC 1328 ms 31132 KiB
test_0037.txt AC 1359 ms 31148 KiB
test_0038.txt AC 1367 ms 31092 KiB
test_0039.txt AC 1222 ms 31340 KiB
test_0040.txt AC 1284 ms 31144 KiB
test_0041.txt AC 1359 ms 31216 KiB
test_0042.txt AC 1241 ms 31160 KiB
test_0043.txt AC 1300 ms 31208 KiB
test_0044.txt AC 1287 ms 31208 KiB
test_0045.txt AC 1291 ms 31160 KiB
test_0046.txt AC 1380 ms 31172 KiB
test_0047.txt AC 1289 ms 31164 KiB
test_0048.txt AC 1282 ms 31304 KiB
test_0049.txt AC 1252 ms 31144 KiB
test_0050.txt AC 1270 ms 31332 KiB
test_0051.txt AC 1365 ms 31212 KiB
test_0052.txt AC 1450 ms 31276 KiB
test_0053.txt AC 1358 ms 31204 KiB
test_0054.txt AC 1318 ms 31272 KiB
test_0055.txt AC 1345 ms 31160 KiB
test_0056.txt AC 1169 ms 31120 KiB
test_0057.txt AC 1291 ms 31148 KiB
test_0058.txt AC 1300 ms 31152 KiB
test_0059.txt AC 1264 ms 31152 KiB
test_0060.txt AC 1191 ms 31080 KiB
test_0061.txt AC 1216 ms 31152 KiB
test_0062.txt AC 1218 ms 31152 KiB
test_0063.txt AC 1305 ms 31204 KiB
test_0064.txt AC 1275 ms 31336 KiB
test_0065.txt AC 1225 ms 31208 KiB
test_0066.txt AC 1296 ms 31208 KiB
test_0067.txt AC 1238 ms 31124 KiB
test_0068.txt AC 1323 ms 31224 KiB
test_0069.txt AC 1244 ms 31204 KiB
test_0070.txt AC 1294 ms 31200 KiB
test_0071.txt AC 1277 ms 31156 KiB
test_0072.txt AC 1367 ms 31148 KiB
test_0073.txt AC 1336 ms 31148 KiB
test_0074.txt AC 1158 ms 31276 KiB
test_0075.txt AC 1230 ms 31332 KiB
test_0076.txt AC 1276 ms 31196 KiB
test_0077.txt AC 1262 ms 31276 KiB
test_0078.txt AC 1354 ms 31292 KiB
test_0079.txt AC 1238 ms 31208 KiB
test_0080.txt AC 1473 ms 31108 KiB
test_0081.txt AC 1341 ms 31148 KiB
test_0082.txt AC 1244 ms 31216 KiB
test_0083.txt AC 1211 ms 31116 KiB
test_0084.txt AC 1256 ms 31144 KiB
test_0085.txt AC 1188 ms 31144 KiB
test_0086.txt AC 1222 ms 31200 KiB
test_0087.txt AC 1308 ms 31200 KiB
test_0088.txt AC 1242 ms 31292 KiB
test_0089.txt AC 1362 ms 31200 KiB
test_0090.txt AC 1178 ms 31164 KiB
test_0091.txt AC 1316 ms 31152 KiB
test_0092.txt AC 1261 ms 31144 KiB
test_0093.txt AC 1233 ms 31208 KiB
test_0094.txt AC 1324 ms 31208 KiB
test_0095.txt AC 1446 ms 31168 KiB
test_0096.txt AC 1161 ms 31144 KiB
test_0097.txt AC 1258 ms 31336 KiB
test_0098.txt AC 1241 ms 31152 KiB
test_0099.txt AC 1275 ms 31148 KiB
test_0100.txt AC 1322 ms 31276 KiB
test_0101.txt AC 1208 ms 31148 KiB
test_0102.txt AC 1301 ms 31164 KiB
test_0103.txt AC 1379 ms 31340 KiB
test_0104.txt AC 1266 ms 31108 KiB
test_0105.txt AC 1257 ms 31156 KiB
test_0106.txt AC 1375 ms 31156 KiB
test_0107.txt AC 1297 ms 31212 KiB
test_0108.txt AC 1351 ms 31208 KiB
test_0109.txt AC 1250 ms 31076 KiB
test_0110.txt AC 1196 ms 31216 KiB
test_0111.txt AC 1295 ms 31144 KiB
test_0112.txt AC 1302 ms 31156 KiB
test_0113.txt AC 1215 ms 31304 KiB
test_0114.txt AC 1326 ms 31328 KiB
test_0115.txt AC 1317 ms 31148 KiB
test_0116.txt AC 1337 ms 31200 KiB
test_0117.txt AC 1299 ms 31080 KiB
test_0118.txt AC 1263 ms 31084 KiB
test_0119.txt AC 1402 ms 31204 KiB
test_0120.txt AC 1167 ms 31296 KiB
test_0121.txt AC 1315 ms 31336 KiB
test_0122.txt AC 1186 ms 31332 KiB
test_0123.txt AC 1231 ms 31148 KiB
test_0124.txt AC 1212 ms 31116 KiB
test_0125.txt AC 1302 ms 31120 KiB
test_0126.txt AC 1201 ms 31116 KiB
test_0127.txt AC 1236 ms 31216 KiB
test_0128.txt AC 1207 ms 31152 KiB
test_0129.txt AC 1328 ms 31080 KiB
test_0130.txt AC 1297 ms 31148 KiB
test_0131.txt AC 1310 ms 31152 KiB
test_0132.txt AC 1208 ms 31212 KiB
test_0133.txt AC 1227 ms 31208 KiB
test_0134.txt AC 1256 ms 31148 KiB
test_0135.txt AC 1325 ms 31200 KiB
test_0136.txt AC 1214 ms 31196 KiB
test_0137.txt AC 1380 ms 31200 KiB
test_0138.txt AC 1250 ms 31152 KiB
test_0139.txt AC 1201 ms 31204 KiB
test_0140.txt AC 1338 ms 31336 KiB
test_0141.txt AC 1158 ms 31152 KiB
test_0142.txt AC 1233 ms 31300 KiB
test_0143.txt AC 1337 ms 31140 KiB
test_0144.txt AC 1219 ms 31152 KiB
test_0145.txt AC 1245 ms 31160 KiB
test_0146.txt AC 1348 ms 31108 KiB
test_0147.txt AC 1209 ms 31116 KiB
test_0148.txt AC 1274 ms 31216 KiB
test_0149.txt AC 1143 ms 31340 KiB