QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#423509 | #3181. Burglary | juancs | AC ✓ | 611ms | 47076kb | C++20 | 3.1kb | 2024-05-28 06:35:18 | 2024-05-28 06:35:18 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r)for(int i = l; i <= (int)r; ++i)
#define fored(i, l, r)for(int i = r; i >= (int)l; --i)
#define all(a) a.begin(), a.end()
#define d(x) cerr<<#x<<" "<<x<<el
#define sz(x) x.size()
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
const int nax = 1010;
int n, m;
int dp[nax][10][10];
vi ladd[nax], jar[nax];
vector<vi> pref;
int calc_pref(int lvl, int l, int r){
return pref[lvl][r] - (l > 0 ? pref[lvl][l - 1] : 0);
}
bool valid(int l1, int r1, int l2, int r2, int lvl){
int l = max(l1, l2);
int r = min(r1, r2);
return l > r || calc_pref(lvl, l, r) == 0;
}
a4 intervals(int lvlp, int lvl1, int lvl2, int ind1, int ind2){
int pos1 = ladd[lvl1][ind1], pos2 = ladd[lvl2][ind2];
int l = min(pos1, pos2), r = max(pos1, pos2);
int oil = upper_bound(all(jar[lvlp]), l) - jar[lvlp].begin() - 1;
int oir = lower_bound(all(jar[lvlp]), r) - jar[lvlp].begin();
int ovl = oil >= 0 ? jar[lvlp][oil] : l;
int ovr = oir < sz(jar[lvlp]) ? jar[lvlp][oir] : r;
return a4{l, r, ovl, ovr};
}
int go(int lvl, int d1, int u2){
if(lvl == n)return 0;
int &v = dp[lvl][d1][u2];
if(v != -1)return v;
// cerr << lvl << ' ' << d1 << ' ' << u2 << el;
int nfl = sz(ladd[lvl]);
auto [cl, cr, col, cor] = intervals(lvl, lvl - 1, lvl - 1, d1, u2);
v = calc_pref(lvl, col, cor);
forn(d2,nfl){
forn(u1,nfl){
auto [l1, r1, lo1, ro1] = intervals(lvl, lvl - 1, lvl, d1, d2);
auto [l2, r2, lo2, ro2] = intervals(lvl, lvl, lvl - 1, u1, u2);
if(!valid(l1, r1, l2, r2, lvl))continue;
int sm = calc_pref(lvl, lo1, ro1) + calc_pref(lvl, lo2, ro2);
int l = max(lo1, lo2), r = min(ro1, ro2);
if(l <= r)sm -= calc_pref(lvl, l, r);
v = max(v, sm + go(lvl + 1, d2, u1));
}
}
return v;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.precision(21);
cin >> n >> m;
pref = vector<vi>(n, vi(m));
forn(i,2*n){
string lvl;
cin>>lvl;
if(!(i & 1)){
forn(j,m){
char c = lvl[j];
if(c != '-'){
pref[i / 2][j] = c - '0';
jar[i / 2].pb(j);
}
pref[i / 2][j] += j != 0 ? pref[i / 2][j - 1] : 0;
// cout << pref[i / 2][j] << ' ';
}
// cout << el;
}else{
forn(j,m){
char c = lvl[j];
if(c == '|') ladd[i / 2].pb(j);
}
}
}
memset(dp, -1, sizeof(dp));
int nfl = sz(ladd[0]);
int ans = 0;
forn(i,nfl){
forn(j,nfl){
ans = max(ans, go(1, i, j));
}
}
cout << ans << el;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4212kb
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: 1ms
memory: 4228kb
input:
2 11 ----------- ...|...|... 2-2-2-2-2-2 |.........|
output:
12
result:
ok single line: '12'
Test #3:
score: 0
Accepted
time: 294ms
memory: 8292kb
input:
1000 1000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
48794
result:
ok single line: '48794'
Test #4:
score: 0
Accepted
time: 8ms
memory: 11740kb
input:
1000 1000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
58959
result:
ok single line: '58959'
Test #5:
score: 0
Accepted
time: 611ms
memory: 47076kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
22478205
result:
ok single line: '22478205'
Test #6:
score: 0
Accepted
time: 142ms
memory: 23796kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 512ms
memory: 24124kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
224305
result:
ok single line: '224305'
Test #8:
score: 0
Accepted
time: 131ms
memory: 23840kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 2ms
memory: 4172kb
input:
100 500 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
976
result:
ok single line: '976'
Test #10:
score: 0
Accepted
time: 463ms
memory: 8132kb
input:
500 1000 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
1874166
result:
ok single line: '1874166'
Test #11:
score: 0
Accepted
time: 316ms
memory: 5876kb
input:
500 500 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
364856
result:
ok single line: '364856'
Test #12:
score: 0
Accepted
time: 114ms
memory: 5092kb
input:
500 500 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
12208
result:
ok single line: '12208'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
2 6 ------ |..|.. 1-4-32 |....|
output:
10
result:
ok single line: '10'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
5 20 -------------------- .......|......|..... -------------2------ ....|.........|..... -------------------- ....|............... -------------------- ....|............... -------------------- ....|...............
output:
2
result:
ok single line: '2'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
1 1 - |
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
1 1 - .
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
2 3 --- .|. 919 |.|
output:
1
result:
ok single line: '1'