Submission #260167

#	Time	Username	Problem	Language	Result	Execution time	Memory
260167		tomsyd	Colouring a rectangle (eJOI19_colouring)	C++17	20 / 100	132 ms	6776 KiB

colouring

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
vector<int> v1,v2;

bool check(vector<vector<bool>>& grid){
	for (int i=0; i<m; ++i){
		for (int j=0; j<n; ++j){
			if (!grid[i][j]) return false;
		}
	}
	return true;
}

int ok(){
	int ans = LLONG_MAX;
	for (int i=0; i<(1ll<<(n+m-1)); ++i){
		vector<vector<bool>> grid(m,vector<bool>(n));
		int sum1 = 0;
		int row = 0, col = n-1;
		for (int j=0; j<(n+m-1); ++j){
			if (i&(1ll<<j)){
				int r = row, c = col;
				while (r < m and c < n){
					grid[r][c] = true;
					r++;
					c++;
				}
				sum1 += v1[j];
			}
			if (col == 0) row++;
			else col--;
		}
		vector<vector<bool>> init = grid;
		for (int j=0; j<(1ll<<(n+m-1)); ++j){
			int sum2 = 0;
			for (int k=0; k<(n+m-1); ++k){
				if (j&(1ll<<k)){
					for (int a=0; a<n; ++a){
						if (a <= k and k-a < m and k-a >= 0){
							grid[k-a][a] = true;
						}
					}
					sum2 += v2[k];
					
				}
			}
			if (check(grid)) ans = min(ans,sum1+sum2);
//			cout << sum1 << ' ' << sum2 << ' ' << ans << endl;
//			cout << i << ' ' << j  << endl;
			grid = init;
		}
	}
	return ans;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> m >> n;
	v1 = vector<int>(n+m-1);
	v2 = vector<int>(n+m-1);
	for (int i=0; i<m+n-1; ++i){
		cin >> v1[i];
	}
	for (int i=0; i<m+n-1; ++i){
		cin >> v2[i];
	}
	if (m <= 4 and n <= 4){
		cout << ok();
		return 0;
	}
	reverse(v2.begin(),v2.end());
	int sum = 0;
	for (int i=0; i<n+m-1; ++i){
		sum += min(v1[i],v2[i]);
	}
	cout << sum;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 10 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20