QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463624 | #3181. Burglary | UNos_maricones | WA | 49ms | 62720kb | C++14 | 2.6kb | 2024-07-05 08:00:30 | 2024-07-05 08:00:30 |
Judging History
answer
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
const int INF = (int) 1e9;
int main() {
cin.tie( NULL );
ios_base::sync_with_stdio( 0 );
int n, m;
cin >> n >> m;
vector< vector< int > > ladders ( n );
vector< vector< int > > acum ( n, vector< int > ( m ));
vector< vector < int > > prv( n, vector< int > ( m ) ), nxt( n, vector< int > ( m ) );
for( int i = 0; i < n; ++ i )
{
string s, l;
cin >> s >> l;
for( int j = 0; j < m; ++ j )
{
if( s[j] != '-' )
acum[i][j] += ( s[j] - '0' );
prv[i][j] = j;
if( j != 0 )
{
acum[i][j] += acum[i][j-1];
if( s[j] == '-' ) prv[i][j] = prv[i][j-1];
}
}
for( int j = m - 1; j >= 0; --j )
{
nxt[i][j] = j;
if( j != m - 1 && s[j] == '-' )
nxt[i][j] = nxt[i][j+1];
}
for( int j = 0; j < m; ++ j )
if( l[j] == '|' )
ladders[i].push_back( j );
}
auto get_sum = [&]( int i, int l, int r ) {
return acum[i][r] - ( l == 0 ? 0 : acum[i][l-1] );
};
int ans = 0;
vector< vector< int > > dp ( ladders[0].size(), vector< int > ( ladders[0].size() ));
for( int i = 0; i < n - 1; ++ i )
{
const int sz = (int) ladders[i].size();
for( int l = 0; l < sz; ++ l )
for( int r = l; r < sz; ++ r )
if( dp[l][r] >= 0 ) //finish on this level
{
if( l == r && get_sum( i + 1, ladders[i][l], ladders[i][r] ) ) continue;
ans = max( ans, dp[l][r] + get_sum(i+1, prv[i+1][ladders[i][l]], nxt[i+1][ladders[i][r]] ) );
}
const int n_sz = (int) ladders[i+1].size();
vector< vector< int > > n_dp( n_sz, vector< int > ( n_sz, -INF ));
for( int l = 0; l < sz; ++ l )
{
for( int r = l; r < sz; ++ r )
{
if( dp[l][r] >= 0 )
{
for( int l2 = 0; l2 < n_sz; ++ l2 )
{
for( int r2 = l2; r2 < n_sz; ++ r2 )
{
const int l_l = prv[i+1][min( ladders[i][l], ladders[i+1][l2] )];
int l_r = max( ladders[i][l], ladders[i+1][l2] );
int r_l = min( ladders[i][r], ladders[i+1][r2] );
const int r_r = nxt[i+1][max( ladders[i][r], ladders[i+1][r2] )];
if( nxt[i+1][l_r] < r_l ) l_r = nxt[i+1][l_r];
if( prv[i+1][r_l] > l_r ) r_l = prv[i+1][r_l];
if( r_l <= l_r && get_sum( i + 1, r_l, l_r ) ) continue;//non empty intersection
n_dp[l2][r2] = max( n_dp[l2][r2], dp[l][r] + get_sum ( i+1, l_l, l_r ) + get_sum ( i+1, r_l, r_r ) );
ans = max( ans, n_dp[l2][r2] );
}
}
}
}
}
swap( dp, n_dp );
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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: 3620kb
input:
2 11 ----------- ...|...|... 2-2-2-2-2-2 |.........|
output:
12
result:
ok single line: '12'
Test #3:
score: 0
Accepted
time: 22ms
memory: 15540kb
input:
1000 1000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
48794
result:
ok single line: '48794'
Test #4:
score: 0
Accepted
time: 3ms
memory: 15772kb
input:
1000 1000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
58959
result:
ok single line: '58959'
Test #5:
score: 0
Accepted
time: 33ms
memory: 62492kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
22478205
result:
ok single line: '22478205'
Test #6:
score: 0
Accepted
time: 39ms
memory: 62440kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 49ms
memory: 62720kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
224305
result:
ok single line: '224305'
Test #8:
score: 0
Accepted
time: 45ms
memory: 62428kb
input:
1000 5000 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4240kb
input:
100 500 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
976
result:
ok single line: '976'
Test #10:
score: 0
Accepted
time: 6ms
memory: 9564kb
input:
500 1000 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
1874166
result:
ok single line: '1874166'
Test #11:
score: 0
Accepted
time: 10ms
memory: 6696kb
input:
500 500 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
364856
result:
ok single line: '364856'
Test #12:
score: 0
Accepted
time: 10ms
memory: 6888kb
input:
500 500 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...
output:
12208
result:
ok single line: '12208'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 6 ------ |..|.. 1-4-32 |....|
output:
10
result:
ok single line: '10'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
5 20 -------------------- .......|......|..... -------------2------ ....|.........|..... -------------------- ....|............... -------------------- ....|............... -------------------- ....|...............
output:
2
result:
ok single line: '2'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 1 - |
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 1 - .
output:
0
result:
ok single line: '0'
Test #17:
score: -100
Wrong Answer
time: 0ms
memory: 3560kb
input:
2 3 --- .|. 919 |.|
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'