QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358467 | #3181. Burglary | PetroTarnavskyi# | AC ✓ | 76ms | 15420kb | C++20 | 3.0kb | 2024-03-19 20:01:40 | 2024-03-19 20:01:41 |
Judging History
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'