제출 #110566

#제출 시각아이디문제언어결과실행 시간메모리
110566ckodserWall (CEOI14_wall)C++14
0 / 100
2080 ms24436 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 44, K = 10; int n, m, vert[N][N], horz[N][N]; ll dp[N][N][1 << K]; priority_queue < tuple < int , int , int , int > > Pq; inline void Relax(int a, int b, int mask, int d) { if (dp[a][b][mask] > d) { dp[a][b][mask] = d; Pq.push(make_tuple(d, a, b, mask)); } } int main() { scanf("%d%d", &n, &m); vector < pair < int , int > > vec; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { int b; scanf("%d", &b); if (b) vec.push_back({i, j}); } for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) scanf("%d", &vert[i][j]); for (int i = 0; i <= n; i++) for (int j = 0; j < m; j++) scanf("%d", &horz[i][j]); assert((int)vec.size() <= 10); memset(dp, 63, sizeof(dp)); dp[0][0][0] = 0; Pq.push({0, 0, 0, 0}); while (Pq.size()) { int d, a, b, mask; tie(d, a, b, mask) = Pq.top(); Pq.pop(); if (d > dp[a][b][mask]) continue; // Up : if (a > 0) Relax(a - 1, b, mask, d + vert[a - 1][b]); // Down : if (a < n) Relax(a + 1, b, mask, d + vert[a][b]); // Left : if (b > 0) { int _mask = mask; for (int i = 0; i < (int)vec.size(); i++) if (vec[i].first >= a && vec[i].second == b - 1) _mask ^= (1 << i); Relax(a, b - 1, _mask, d + horz[a][b - 1]); } // Right : if (b < m) { int _mask = mask; for (int i = 0; i < (int)vec.size(); i++) if (vec[i].first >= a && vec[i].second == b) _mask ^= (1 << i); Relax(a, b + 1, _mask, d + horz[a][b]); } } return !printf("%lld\n", dp[0][0][(1 << (int)vec.size()) - 1]); }

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In function 'int main()':
wall.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
wall.cpp:24:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~
wall.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &vert[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~
wall.cpp:33:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &horz[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...