oj.uz

Submission #1020082

# Submission time Handle Problem Language Result Execution time Memory
1020082 2024-07-11T14:03:03 Z Tob Miners (IOI07_miners) C++14
100 / 100
 15 ms 12328 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7;

int n;
int dp[N][3][10], va[200], co[4][4][4];

int main () {
	FIO;
	va['M'] = 0;
	va['B'] = 1;
	va['F'] = 2;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				vector <int> v; v = {i, j, k};
				sort(all(v)); v.erase(unique(all(v)), v.end());
				co[i][j][k] = v.size();
			}
		}
	}
	cin >> n;
	string s; cin >> s;
	for (int i = n-2; i >= 0; i--) {
		for (int i1 = 0; i1 < 3; i1++) {
			for (int j1 = 0; j1 < 3; j1++) {
				for (int k1 = 0; k1 < 3; k1++) {
					dp[i][i1][3*j1+k1] = max(dp[i+1][va[s[i]]][3*j1+k1] + co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][j1][3*va[s[i]]+i1] + co[k1][j1][va[s[i+1]]]);
				}
			}
			dp[i][i1][9] = max(dp[i+1][va[s[i]]][9]+co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][va[s[i+1]]][3*va[s[i]]+i1]+1);
		}
	}
	cout << 1+dp[0][va[s[0]]][9];

	return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:39:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |      dp[i][i1][3*j1+k1] = max(dp[i+1][va[s[i]]][3*j1+k1] + co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][j1][3*va[s[i]]+i1] + co[k1][j1][va[s[i+1]]]);
      |                                              ^
miners.cpp:39:74: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |      dp[i][i1][3*j1+k1] = max(dp[i+1][va[s[i]]][3*j1+k1] + co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][j1][3*va[s[i]]+i1] + co[k1][j1][va[s[i+1]]]);
      |                                                                          ^
miners.cpp:39:86: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |      dp[i][i1][3*j1+k1] = max(dp[i+1][va[s[i]]][3*j1+k1] + co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][j1][3*va[s[i]]+i1] + co[k1][j1][va[s[i+1]]]);
      |                                                                                      ^
miners.cpp:39:111: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |      dp[i][i1][3*j1+k1] = max(dp[i+1][va[s[i]]][3*j1+k1] + co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][j1][3*va[s[i]]+i1] + co[k1][j1][va[s[i+1]]]);
      |                                                                                                               ^
miners.cpp:39:139: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |      dp[i][i1][3*j1+k1] = max(dp[i+1][va[s[i]]][3*j1+k1] + co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][j1][3*va[s[i]]+i1] + co[k1][j1][va[s[i+1]]]);
      |                                                                                                                                           ^
miners.cpp:42:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |    dp[i][i1][9] = max(dp[i+1][va[s[i]]][9]+co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][va[s[i+1]]][3*va[s[i]]+i1]+1);
      |                                      ^
miners.cpp:42:58: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |    dp[i][i1][9] = max(dp[i+1][va[s[i]]][9]+co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][va[s[i+1]]][3*va[s[i]]+i1]+1);
      |                                                          ^
miners.cpp:42:70: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |    dp[i][i1][9] = max(dp[i+1][va[s[i]]][9]+co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][va[s[i+1]]][3*va[s[i]]+i1]+1);
      |                                                                      ^
miners.cpp:42:91: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |    dp[i][i1][9] = max(dp[i+1][va[s[i]]][9]+co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][va[s[i+1]]][3*va[s[i]]+i1]+1);
      |                                                                                           ^
miners.cpp:42:103: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |    dp[i][i1][9] = max(dp[i+1][va[s[i]]][9]+co[i1][va[s[i]]][va[s[i+1]]], dp[i+1][va[s[i+1]]][3*va[s[i]]+i1]+1);
      |                                                                                                       ^
miners.cpp:45:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |  cout << 1+dp[0][va[s[0]]][9];
      |                         ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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