제출 #776643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776643		vjudge1	Sajam (COCI18_sajam)	C++17	45 / 90	47 ms	4308 KiB

sajam

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 1005

bitset<N> arr[N];
int dist[N][N];
const int INF = 2e9 + 7;

int32_t main(){
	#ifndef ONLINE_JUDGE
	//fileio();
	#endif
	fastio();

	int n, k;
	cin>>n>>k;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			char c;
			cin>>c;
			arr[i][j] = c == 'x';
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = i + 1; j <= n; j++){
			bitset<N> tmp = arr[i] ^ arr[j];
			dist[i][j] = dist[j][i] = tmp.count();
		}
	}

	int ans = INF;
	for (int i = 1; i <= n; i++){
		int curr = 0;
		for (int j = 1; j <= n; j++){
			curr += min(dist[i][j], n - dist[i][j]);
		}
		ans = min(ans, curr);
	}

	for (int i = 1; i <= n; i++){
		int curr = 1;
		for (int j = 2; j <= n; j++){
			if (arr[j][i] == arr[1][i]) dist[1][j]++;
			else dist[1][j]--;
			curr += min(dist[1][j], n - dist[1][j]);
			if (arr[j][i] == arr[1][i]) dist[1][j]--;
			else dist[1][j]++;
		}
	}
	if (ans <= k) cout<<"DA\n";
	else cout<<"NE\n";
	//cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15