제출 #690060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
690060		maks007	Red-blue table (IZhO19_stones)	C++14	17 / 100	2050 ms	262144 KiB

stones

#include "bits/stdc++.h"

using namespace std;

//#define int long long

struct st{
	int str;
	vector <int> col;	
};

st merge(st a, st b, vector <char> v) {
	a.str = b.str;
	if(count(v.begin(), v.end(), '+') > count(v.begin(), v.end(), '-')) a.str ++;
	a.col = b.col;
	for(int i = 0; i < v.size(); i ++) {
		if(v[i] == '+') a.col[i] ++;
		else a.col[i] --;
	}
	return a;
}

int get(st val) {
	int cnt = val.str;
	for(auto i : val.col) {
		cnt += (i < 0);
	}
	return cnt;
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T --) {
		int n, m;
		cin >> n >> m;
//		if(m <= 5) {
			st dp[n][(1 << m)];
			pair <int,int> path[n][(1 << m)];
			for(int i = 0; i < n; i ++) {
				for(int j = 0; j < (1 << m); j ++) {
					dp[i][j].str = 0;
					dp[i][j].col.resize(m,0);
					path[i][j] = {-1,-1};
				}
			}
			for(int i = 0; i < n; i ++) {
				for(int mask = 0; mask < (1 << m); mask ++) {
					vector <char> v;
					for(int j = 0; j < m; j ++) {
						if(mask & (1 << j)) v.push_back('+');
						else v.push_back('-');
					}
					reverse(v.begin(), v.end());
					if(i) {
						for(int mask2 = 0; mask2 < (1 << m); mask2 ++) {
							if(get(dp[i][mask]) <= get(merge(dp[i][mask], dp[i-1][mask2], v)) ) {
								dp[i][mask]=merge(dp[i][mask], dp[i-1][mask2], v);
								path[i][mask] = {i-1,mask2};
							}
						}
					}else {
						for(int j = 0; j < m; j ++) {
							if(v[j] == '+') dp[i][mask].col[j] ++;
							else dp[i][mask].col[j]--;
						}
						if(count(v.begin(), v.end(), '+') > count(v.begin(), v.end(), '-')) dp[i][mask].str = 1;
						path[i][mask]={-1,-1};
					}
				}
			}
			int ans = 0;
			pair <int,int> add;
			for(int i= 0; i < (1 << m); i++) {
				int cnt = dp[n-1][i].str;
				for(int j = 0; j < dp[n-1][i].col.size(); j ++) {
					if(dp[n-1][i].col[j] < 0) cnt ++;
				}
				if(cnt >= ans) {
					ans = cnt;
					add = {n-1,i};
				}
			}
			cout << ans << "\n";
			vector <int> v;
			v.push_back(add.second);
			while(add.first != -1) {
				add = path[add.first][add.second];
				if(add.first == -1) break;
				v.push_back(add.second);
			}
			reverse(v.begin(), v.end());
			for(int i = 0; i < v.size(); i ++) {
				for(int j = m-1; j >=0; j --) {
					if(v[i] & (1 << j)) cout << '+';
					else cout << '-';
				}
				cout << "\n";
			}
//		}else {
//			
//		}
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

stones.cpp: In function 'st merge(st, st, std::vector<char>)':
stones.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < v.size(); i ++) {
      |                 ~~^~~~~~~~~~
stones.cpp: In function 'int main()':
stones.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int j = 0; j < dp[n-1][i].col.size(); j ++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~
stones.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for(int i = 0; i < v.size(); i ++) {
      |                   ~~^~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 10
• Subtask 3: 0 / 16
• Subtask 4: 0 / 11
• Subtask 5: 0 / 15
• Subtask 6: 0 / 31