QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#463623#3181. BurglaryUNos_mariconesWA 0ms3572kbC++142.5kb2024-07-05 07:56:332024-07-05 07:56:34

Judging History

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

  • [2024-07-05 07:56:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3572kb
  • [2024-07-05 07:56:33]
  • 提交

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 ) );
						}
					}
				}
			}
		}
		swap( dp, n_dp );
	}

	cout << ans << '\n';
	return 0;
}

詳細信息

Test #1:

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

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: -100
Wrong Answer
time: 0ms
memory: 3568kb

input:

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

output:

8

result:

wrong answer 1st lines differ - expected: '12', found: '8'