Submission #126701

#TimeUsernameProblemLanguageResultExecution timeMemory
126701eriksuenderhaufWall (CEOI14_wall)C++11
100 / 100
411 ms24012 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 4e2 + 5; const double eps = 1e-9; int nx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int ny[4][2] = {{1, 3}, {2, 3}, {0, 2}, {0, 1}}; int a[MAXN][MAXN], w[MAXN][MAXN][2], b[MAXN][MAXN][2]; int n, m, par[MAXN][MAXN]; ll dp[MAXN][MAXN][4]; ll dijkstra(bool fl) { mem(dp, 0x3f); dp[0][0][1] = 0; priority_queue<pair<pll,pll>,vector<pair<pll,pll>>,greater<pair<pll,pll>>> pq; pq.push({{0,0},{0,1}}); while (!pq.empty()) { pair<pll,pll> u = pq.top(); pq.pop(); ll cur = u.fi.fi; int i = u.fi.se, j, k; tie(j, k) = u.se; if (dp[i][j][k] != cur) continue; if (fl && !(i == 0 && j == 0)) { if ((1 - i > (k&1) || !b[i-1+(k&1)][j][0]) && dp[i][j][k^2] > cur) { dp[i][j][k^2] = cur; pq.push({{cur, i}, {j, k^2}}); } if ((1 - j > (k/2) || !b[i][j-1+(k/2)][1]) && dp[i][j][k^1] > cur) { dp[i][j][k^1] = cur; pq.push({{cur, i}, {j, k^1}}); } } for (int l = 0; l < 4; l++) { int ni = i + nx[l][0], nj = j + nx[l][1]; if (fl && ny[l][0] != k && ny[l][1] != k || ni < 0 || ni > n || nj < 0 || nj > m) continue; int nk = k ^ (fl ? (l & 1) + 1 : 0), nw = w[i - (l == 2)][j - (l == 3)][l & 1]; if (dp[ni][nj][nk] > cur + nw) { dp[ni][nj][nk] = cur + nw; pq.push({{cur+nw,ni},{nj,nk}}); par[ni][nj] = l; } } } return dp[0][0][2]; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ni(a[i][j]); for (int i = 0; i < 2; i++) for (int j = 0; j < n + i; j++) for (int k = 0; k < m + (1 - i); k++) ni(w[j][k][i]); dijkstra(0); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!a[i][j]) continue; int u = i, v = j; while (!(u == 0 && v == 0)) { int p = par[u][v]; if (b[u - (p == 0)][v - (p == 1)][p & 1] != 0) break; b[u - (p == 0)][v - (p == 1)][p & 1] = 1; u -= nx[p][0]; v -= nx[p][1]; } b[i][j][0] = b[i][j][1] = b[i][j+1][0] = b[i+1][j][1] = 1; } } prl(dijkstra(1)); return 0; }

Compilation message (stderr)

wall.cpp: In function 'll dijkstra(bool)':
wall.cpp:67:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if (fl && ny[l][0] != k && ny[l][1] != k || ni < 0 || ni > n || nj < 0 || nj > m)
        ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp: In function 'int main()':
wall.cpp:81: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:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
wall.cpp:84:4: note: in expansion of macro 'ni'
    ni(a[i][j]);
    ^~
wall.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
wall.cpp:88:5: note: in expansion of macro 'ni'
     ni(w[j][k][i]);
     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...