제출 #126701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126701		eriksuenderhauf	Wall (CEOI14_wall)	C++11	100 / 100	411 ms	24012 KiB

wall

//#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;
}

컴파일 시 표준 에러 (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]);
     ^~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40