제출 #1174000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174000		nuutsnoynton	Domino (COCI15_domino)	C++20	60 / 160	4096 ms	31768 KiB

domino

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
using pal =  pair < pll ,pll > ;
ll a[2002][2002];
int main() {
	ll n, m, r, k, can, p, x, s, y, i, j, ans =0, t, sum;

	cin >> n >> k;
	if ( k > 5) {
		while(1);
	}
	sum = 0;
	priority_queue < pal ,vector < pal>, greater < pal > > pq;
	for ( i = 1; i <= n; i ++) {
		for (j = 1; j <= n; j ++){
			cin >> a[i][j];
			sum += a[i][j];
		}
	}
	for (i = 1; i <= n; i ++) {
		for (j = 1; j < n; j ++) {
			r = a[i][j] + a[i][j + 1];
			pq.push(make_pair(make_pair(r, 1), make_pair(i, j)));
			if ( pq.size() > 7 * k) pq.pop();
		}
	}
	
	for (i = 1; i < n; i ++) {
		for (j = 1; j <= n; j ++) {
			r = a[i][j] + a[i + 1][j];
			pq.push(make_pair(make_pair(r, 0), make_pair(i, j)));
			if ( pq.size() > 7 * k) pq.pop();
		}
	}
	vector < pair < pll, pll > > v;
	
	while(!pq.empty()) {
		auto R = pq.top();
		pq.pop();
		v.push_back(R);
	}
	ll R= v.size();
	ll S = (1<<R);
	for (i = 0; i < S; i ++) {
		vector < pair < pll, pll >  > q;
		if (__builtin_popcount(i) != k) {
			continue;
		}
		for (j = 0; j < R; j ++) {
			p = i & (1<< j);
			if ( p != 0) {
				q.push_back(v[j]);
			} 
		}
		can = 1;
		s = 0;
		pll N_1, N_2, N_3, N_4;
		for (j = 0; j < q.size(); j ++) {
			N_1 = q[j].second;
			N_2 = N_1;
			if ( q[j].first.second == 0) N_2.first ++;
			else N_2.second ++;
			s += a[N_1.first][N_1.second];
			s += a[N_2.first][N_2.second];
			for ( r = j + 1; r < q.size(); r ++) {
				N_3 = q[r].second;
				N_4 = N_3;
				if ( q[r].first.second == 0) N_4.first ++;
				else N_4.second ++;
				if ( N_1 == N_2 || N_1 == N_3 || N_1 == N_4 || N_2 == N_3 || N_2 == N_4 || N_3 == N_4) {
					can =0;
					break;
				}
			}
		}
		if ( can == 1) {
			ans = max(ans, s);
		}
	}
	cout<< sum - ans << endl;
	
	
	
	
	
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10