Submission #1008019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008019		vjudge1	Miners (IOI07_miners)	C++17	100 / 100	935 ms	245116 KiB

miners

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

const int N = 2e5+1;

int localchecker = 0;

int n;
string s;

int dp[N][5][5][5][5];

int dis(int x, int y, int z) {
	set<int> cc = {x,y,z};
	return cc.size();
}

#define chmax(x, y) x = max(x, y);

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> s;
	if (n <= 20) {
		int sol = 0;
		for (int msk = 0; msk < (1 << n); msk++) {
			int coal = 0;
			vector<int> fr, sc;
			for (int i = 0; i < n; i++) {
				if (msk>>i&1) swap(fr, sc);
			
				fr.push_back(s[i]);
				if (fr.size() == 1)	coal += 1;
				else if (fr.size() == 2) coal += 1+(fr[1] != fr[0]);
				else {
					set<int> cc;
					cc.insert(fr[fr.size()-1]);
					cc.insert(fr[fr.size()-2]);
					cc.insert(fr[fr.size()-3]);
					coal += cc.size();
				}
				
				
				if (msk>>i&1) swap(fr, sc);
			}
			
			sol = max(sol, coal);
		}
		cerr << "Checker: " << sol << endl;
		localchecker = sol;
	}
	
	for (int i = 1; i <= n; i++) {
		for (int p1 = 0; p1 < 3; p1++) {
			for (int p2 = 0; p2 < 3; p2++) {
				for (int p3 = 0; p3 < 3; p3++) {
					for (int p4 = 0; p4 < 3; p4++) {
						dp[i][p1][p2][p3][p4] = -10000;
					}
				}
			}
		}
	}

	
	s = '#' + s;
	for (char &c : s) c = (c == 'M' ? 0 : (c == 'B' ? 1 : 2));
	for (int i = 1; i <= n; i++) {
		for (int p1 = 0; p1 < 3; p1++) {
			for (int p2 = 0; p2 < 3; p2++) {
				for (int p3 = 0; p3 < 3; p3++) {
					for (int p4 = 0; p4 < 3; p4++) {
						chmax(dp[i][s[i]][p1][p3][p4],
								dp[i-1][p1][p2][p3][p4] + dis(s[i], p1, p2));
						chmax(dp[i][p1][p2][s[i]][p3],
								dp[i-1][p1][p2][p3][p4] + dis(s[i], p3, p4));
					}
				}
			}
		}
	}
	int sol = 0;
	for (int p1 = 0; p1 < 3; p1++) {
		for (int p2 = 0; p2 < 3; p2++) {
			for (int p3 = 0; p3 < 3; p3++) {
				for (int p4 = 0; p4 < 3; p4++) {
					chmax(sol, dp[n][p1][p2][p3][p4]);
				}
			}
		}
	}
	cout << sol-6;
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:75:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |       chmax(dp[i][s[i]][p1][p3][p4],
      |                       ^
miners.cpp:20:21: note: in definition of macro 'chmax'
   20 | #define chmax(x, y) x = max(x, y);
      |                     ^
miners.cpp:75:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |       chmax(dp[i][s[i]][p1][p3][p4],
      |                       ^
miners.cpp:20:29: note: in definition of macro 'chmax'
   20 | #define chmax(x, y) x = max(x, y);
      |                             ^
miners.cpp:77:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   77 |       chmax(dp[i][p1][p2][s[i]][p3],
      |                               ^
miners.cpp:20:21: note: in definition of macro 'chmax'
   20 | #define chmax(x, y) x = max(x, y);
      |                     ^
miners.cpp:77:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   77 |       chmax(dp[i][p1][p2][s[i]][p3],
      |                               ^
miners.cpp:20:29: note: in definition of macro 'chmax'
   20 | #define chmax(x, y) x = max(x, y);
      |                             ^

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8