oj.uz

Submission #1008019

# Submission time Handle Problem Language Result Execution time Memory
1008019 2024-06-26T06:06:24 Z vjudge1 Miners (IOI07_miners) C++17
100 / 100
 935 ms 245116 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 436 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 344 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 452 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4700 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12888 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 25256 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 61532 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 184004 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 245116 KB Output is correct