oj.uz

Submission #260167

# Submission time Handle Problem Language Result Execution time Memory
260167 2020-08-09T12:46:40 Z tomsyd Colouring a rectangle (eJOI19_colouring) C++17
20 / 100
 132 ms 6776 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3532 KB Output is correct
2 Correct 65 ms 4600 KB Output is correct
3 Correct 69 ms 4600 KB Output is correct
4 Correct 66 ms 4856 KB Output is correct
5 Correct 67 ms 4728 KB Output is correct
6 Correct 64 ms 4096 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -