oj.uz

Submission #778090

# Submission time Handle Problem Language Result Execution time Memory
778090 2023-07-10T06:09:39 Z 박상훈(#9995) Wall (CEOI14_wall) C++17
30 / 100
 2000 ms 38028 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
int a[404][404], cst1[404][404], cst2[404][404];
ll dist[44][44][1024];

ll naive(int n, int m){
	vector<pair<int, int>> P;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (a[i][j]==1) P.emplace_back(i, j);
		}
	}

	int k = P.size();
	for (int i=0;i<=n;i++){
		for (int j=0;j<=m;j++){
			for (int z=0;z<(1<<k);z++){
				dist[i][j][z] = INF;
			}
		}
	}

	priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
	dist[0][0][0] = 0;
	pq.push({dist[0][0][0], 0, 0, 0});

	while(!pq.empty()){
		auto [d, x, y, z] = pq.top(); pq.pop();
		if (d > dist[x][y][z]) continue;

		if (y<m){ // go right
			int c = cst2[x][y+1];
			if (dist[x][y+1][z] > d + c){
				dist[x][y+1][z] = d + c;
				pq.push({dist[x][y+1][z], x, y+1, z});
			}
		}

		if (y>0){ // go left
			int c = cst2[x][y];
			if (dist[x][y-1][z] > d + c){
				dist[x][y-1][z] = d + c;
				pq.push({dist[x][y-1][z], x, y-1, z});
			}
		}

		if (x<n){ // go down
			int c = cst1[x+1][y];
			int nz = z;
			for (int i=0;i<k;i++) if (P[i].first==x+1 && P[i].second <= y) nz ^= (1<<i);

			if (dist[x+1][y][nz] > d + c){
				dist[x+1][y][nz] = d + c;
				pq.push({dist[x+1][y][nz], x+1, y, nz});
			}
		}

		if (x>0){ // go up
			int c = cst1[x][y];
			int nz = z;
			for (int i=0;i<k;i++) if (P[i].first==x && P[i].second <= y) nz ^= (1<<i);

			if (dist[x-1][y][nz] > d + c){
				dist[x-1][y][nz] = d + c;
				pq.push({dist[x-1][y][nz], x-1, y, nz});
			}
		}
	}

	return dist[0][0][(1<<k)-1];
}

int main(){
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			scanf("%d", a[i]+j);
		}
	}

	for (int i=1;i<=n;i++){
		for (int j=0;j<=m;j++){
			scanf("%d", cst1[i]+j);
		}
	}

	for (int i=0;i<=n;i++){
		for (int j=1;j<=m;j++){
			scanf("%d", cst2[i]+j);
		}
	}

	ll ans = naive(n, m);
	printf("%lld\n", ans);
}

Compilation message

wall.cpp: In function 'int main()':
wall.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:82:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |    scanf("%d", a[i]+j);
      |    ~~~~~^~~~~~~~~~~~~~
wall.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |    scanf("%d", cst1[i]+j);
      |    ~~~~~^~~~~~~~~~~~~~~~~
wall.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |    scanf("%d", cst2[i]+j);
      |    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 948 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 338 ms 11240 KB Output is correct
8 Correct 11 ms 4612 KB Output is correct
9 Correct 2 ms 2972 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 520 ms 17848 KB Output is correct
12 Correct 24 ms 6656 KB Output is correct
13 Correct 186 ms 18236 KB Output is correct
14 Correct 642 ms 21180 KB Output is correct
15 Correct 3 ms 5568 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 13524 KB Execution killed with signal 11
2 Incorrect 626 ms 16596 KB Output isn't correct
3 Incorrect 458 ms 30580 KB Output isn't correct
4 Correct 5 ms 6996 KB Output is correct
5 Runtime error 22 ms 35680 KB Execution killed with signal 11
6 Runtime error 18 ms 13908 KB Execution killed with signal 11
7 Runtime error 21 ms 14560 KB Execution killed with signal 11
8 Incorrect 540 ms 15932 KB Output isn't correct
9 Correct 82 ms 8896 KB Output is correct
10 Correct 7 ms 7636 KB Output is correct
11 Runtime error 17 ms 26836 KB Execution killed with signal 11
12 Runtime error 21 ms 13780 KB Execution killed with signal 11
13 Runtime error 288 ms 35644 KB Execution killed with signal 11
14 Correct 674 ms 16308 KB Output is correct
15 Correct 92 ms 11076 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Runtime error 17 ms 13780 KB Execution killed with signal 11
18 Runtime error 18 ms 13780 KB Execution killed with signal 11

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 19472 KB Execution killed with signal 11
2 Runtime error 35 ms 35984 KB Execution killed with signal 11
3 Runtime error 30 ms 19480 KB Execution killed with signal 11
4 Runtime error 123 ms 36192 KB Execution killed with signal 11
5 Runtime error 178 ms 37408 KB Execution killed with signal 11
6 Runtime error 34 ms 19452 KB Execution killed with signal 11
7 Runtime error 46 ms 36664 KB Execution killed with signal 11
8 Runtime error 56 ms 36416 KB Execution killed with signal 11
9 Runtime error 39 ms 20812 KB Execution killed with signal 11
10 Runtime error 43 ms 37064 KB Execution killed with signal 11
11 Execution timed out 2065 ms 18964 KB Time limit exceeded
12 Runtime error 30 ms 36300 KB Execution killed with signal 11
13 Runtime error 40 ms 20580 KB Execution killed with signal 11
14 Runtime error 52 ms 21452 KB Execution killed with signal 11
15 Runtime error 70 ms 36880 KB Execution killed with signal 11
16 Runtime error 54 ms 37928 KB Execution killed with signal 11
17 Runtime error 64 ms 38028 KB Execution killed with signal 11
18 Runtime error 60 ms 22396 KB Execution killed with signal 11
19 Runtime error 54 ms 37420 KB Execution killed with signal 11
20 Runtime error 57 ms 21936 KB Execution killed with signal 11