Submission #110567

# Submission time Handle Problem Language Result Execution time Memory
110567 2019-05-11T07:53:48 Z ckodser Wall (CEOI14_wall) C++14
0 / 100
2000 ms 28280 KB
#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 < ll , int , int , int > > Pq;
inline void Relax(int a, int b, int mask, ll 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]);
}

Compilation message

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 time Memory Grader output
1 Correct 240 ms 16128 KB Output is correct
2 Execution timed out 2048 ms 15872 KB Time limit exceeded
3 Execution timed out 2057 ms 16000 KB Time limit exceeded
4 Execution timed out 2056 ms 15972 KB Time limit exceeded
5 Execution timed out 2048 ms 15872 KB Time limit exceeded
6 Execution timed out 2059 ms 16120 KB Time limit exceeded
7 Execution timed out 2064 ms 22292 KB Time limit exceeded
8 Execution timed out 2067 ms 16512 KB Time limit exceeded
9 Execution timed out 2043 ms 15872 KB Time limit exceeded
10 Execution timed out 2068 ms 15928 KB Time limit exceeded
11 Execution timed out 2048 ms 22320 KB Time limit exceeded
12 Execution timed out 2036 ms 16920 KB Time limit exceeded
13 Execution timed out 2052 ms 16476 KB Time limit exceeded
14 Execution timed out 2048 ms 22116 KB Time limit exceeded
15 Execution timed out 2059 ms 15956 KB Time limit exceeded
# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Execution timed out 2055 ms 16040 KB Time limit exceeded
5 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Execution timed out 2058 ms 19176 KB Time limit exceeded
10 Execution timed out 2037 ms 16440 KB Time limit exceeded
11 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Execution timed out 2033 ms 28280 KB Time limit exceeded
15 Execution timed out 2045 ms 16884 KB Time limit exceeded
16 Execution timed out 2045 ms 16288 KB Time limit exceeded
17 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Execution timed out 9 ms 376 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 384 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 384 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 284 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 768 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 384 KB Time limit exceeded (wall clock)
7 Runtime error 13 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Execution timed out 10 ms 356 KB Time limit exceeded (wall clock)
10 Execution timed out 14 ms 256 KB Time limit exceeded (wall clock)
11 Execution timed out 20 ms 384 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 384 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 512 KB Time limit exceeded (wall clock)
14 Execution timed out 21 ms 384 KB Time limit exceeded (wall clock)
15 Runtime error 20 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Execution timed out 14 ms 384 KB Time limit exceeded (wall clock)
17 Execution timed out 16 ms 256 KB Time limit exceeded (wall clock)
18 Execution timed out 18 ms 256 KB Time limit exceeded (wall clock)
19 Execution timed out 18 ms 384 KB Time limit exceeded (wall clock)
20 Execution timed out 16 ms 384 KB Time limit exceeded (wall clock)