QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358467#3181. BurglaryPetroTarnavskyi#AC ✓76ms15420kbC++203.0kb2024-03-19 20:01:402024-03-19 20:01:41

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 20:01:41]
  • 评测
  • 测评结果:AC
  • 用时:76ms
  • 内存:15420kb
  • [2024-03-19 20:01:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int INF = 1e9;
const int N = 1 << 10;
const int M = 1 << 13;

template<typename T>
void updMax(T& a, T b)
{
	a = max(a, b);
}

int dp[N][10][10];
int pref[M], prv[M], nxt[M];
int poses[4];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<string> s(2 * n);
	for (string& si : s)
		cin >> si;
	vector<VI> ladders(n);
	FOR(i, 0, n)
	{
		FOR(j, 0, m)
			if (s[2 * i + 1][j] == '|')
				ladders[i].PB(j);
		assert(SZ(ladders[i]) <= 10);
	}
	RFOR(k, n, 1)
	{
		FOR(i, 0, SZ(ladders[k - 1]))
			FOR(j, 0, SZ(ladders[k - 1]))
				dp[k][i][j] = -INF;
		int row = 2 * k;
		FOR(i, 0, m + 1)
			pref[i] = 0;
		FOR(i, 0, m)
		{
			int cur = s[row][i] == '-' ? 0 : s[row][i] - '0';
			pref[i + 1] = pref[i] + cur;
		}
		int pos = -1;
		FOR(i, 0, m)
		{
			prv[i] = pos;
			if (s[row][i] != '-')
				pos = i;
		}
		pos = -1;
		RFOR(i, m, 0)
		{
			nxt[i] = pos;
			if (s[row][i] != '-')
				pos = i;
		}
		FOR(iu, 0, SZ(ladders[k - 1]))
		{
			FOR(ju, 0, SZ(ladders[k - 1]))
			{
				int l = ladders[k - 1][iu], r = ladders[k - 1][ju];
				if (l > r)
					swap(l, r);
				int ssum = pref[r + 1] - pref[l];
				if (s[row][l] == '-' && prv[l] != -1)
					ssum += s[row][prv[l]] - '0';
				if (s[row][r] == '-' && nxt[r] != -1)
					ssum += s[row][nxt[r]] - '0';
				updMax(dp[k][iu][ju], ssum);
				FOR(id, 0, SZ(ladders[k]))
				{
					FOR(jd, 0, SZ(ladders[k]))
					{
						int l1 = ladders[k - 1][iu];
						int r1 = ladders[k][id];
						int l2 = ladders[k - 1][ju];
						int r2 = ladders[k][jd];
						if (l1 > r1)
							swap(l1, r1);
						if (l2 > r2)
							swap(l2, r2);
						int lInter = max(l1, l2), rInter = min(r1, r2);
						if (lInter <= rInter && pref[rInter + 1] - pref[lInter] > 0)
						{
							continue;
						}
						int sum = pref[r1 + 1] - pref[l1] + pref[r2 + 1] - pref[l2];
						poses[0] = s[row][l1] != '-' ? -1 : prv[l1];
						poses[1] = s[row][r1] != '-' ? -1 : nxt[r1];
						poses[2] = s[row][l2] != '-' ? -1 : prv[l2];
						poses[3] = s[row][r2] != '-' ? -1 : nxt[r2];
						FOR(i, 0, 4)
						{
							if (poses[i] == -1 || (l1 <= poses[i] && poses[i] <= r1) || (l2 <= poses[i] && poses[i] <= r2))
								continue;
							bool ok = true;
							FOR(j, 0, i)
								ok &= poses[j] != poses[i];
							if (ok)
								sum += s[row][poses[i]] - '0';
						}
						updMax(dp[k][iu][ju], dp[k + 1][id][jd] + sum);
					}
				}
			}
		}
	}
	int ans = 0;
	FOR(i, 0, SZ(ladders[0]))
		FOR(j, 0, SZ(ladders[0]))
			updMax(ans, dp[1][i][j]);
	cout << ans << "\n";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3536kb

input:

5 20
--------------------
.|.....|...|......|.
1-1--1115-3-1-1--1-1
....|.........|.....
---1-11-1-11---1--3-
.......|.........|..
-7----9-4-----------
..|.................
--------9-----------
.|.................|

output:

38

result:

ok single line: '38'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

2 11
-----------
...|...|...
2-2-2-2-2-2
|.........|

output:

12

result:

ok single line: '12'

Test #3:

score: 0
Accepted
time: 76ms
memory: 6172kb

input:

1000 1000
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

48794

result:

ok single line: '48794'

Test #4:

score: 0
Accepted
time: 11ms
memory: 6268kb

input:

1000 1000
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

58959

result:

ok single line: '58959'

Test #5:

score: 0
Accepted
time: 37ms
memory: 15244kb

input:

1000 5000
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

22478205

result:

ok single line: '22478205'

Test #6:

score: 0
Accepted
time: 66ms
memory: 15200kb

input:

1000 5000
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 70ms
memory: 15420kb

input:

1000 5000
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

224305

result:

ok single line: '224305'

Test #8:

score: 0
Accepted
time: 70ms
memory: 15220kb

input:

1000 5000
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 2ms
memory: 4024kb

input:

100 500
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

976

result:

ok single line: '976'

Test #10:

score: 0
Accepted
time: 18ms
memory: 5184kb

input:

500 1000
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

1874166

result:

ok single line: '1874166'

Test #11:

score: 0
Accepted
time: 32ms
memory: 4376kb

input:

500 500
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

364856

result:

ok single line: '364856'

Test #12:

score: 0
Accepted
time: 39ms
memory: 4656kb

input:

500 500
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

12208

result:

ok single line: '12208'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

2 6
------
|..|..
1-4-32
|....|

output:

10

result:

ok single line: '10'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

5 20
--------------------
.......|......|.....
-------------2------
....|.........|.....
--------------------
....|...............
--------------------
....|...............
--------------------
....|...............

output:

2

result:

ok single line: '2'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

1 1
-
|

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

1 1
-
.

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

2 3
---
.|.
919
|.|

output:

1

result:

ok single line: '1'