oj.uz

Submission #71495

# Submission time Handle Problem Language Result Execution time Memory
71495 2018-08-24T23:12:48 Z RezwanArefin01 Miners (IOI07_miners) C++17
100 / 100
 95 ms 1100 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10; 
int n; char s[N]; 
int dp[2][13][13], mp[30];
int m[13] = {00, 01, 02, 03, 11, 12, 13, 21, 22, 23, 31, 32, 33}, rev[100];
int cost[13][4]; 

int get(int mask, int c) {
	set<int> st; 
	while(mask) {
		int x = mask % 10;
		if(x) st.insert(x);
		mask /= 10;
	} st.insert(c);
	return st.size();
}

int main(int argc, char const *argv[]) {
	mp['M' - 'A'] = 1; mp['B' - 'A'] = 2; mp['F' - 'A'] = 3; 

	for(int i = 0; i < 13; i++) {
		rev[m[i]] = i; 
		for(int j = 1; j <= 3; j++) {
			cost[i][j] = get(m[i], j); 
		}
	}

	scanf("%d", &n);
	scanf(" %s", s + 1); 

	for(int i = n; i >= 1; --i) {
		int now = i & 1, nxt = now ^ 1; 
		int c = mp[s[i] - 'A']; 
		for(int m1 = 0; m1 < 13; ++m1) {
			for(int m2 = 0; m2 < 13; ++m2) {
				int mask1 = m[m1]; 
				int mask2 = m[m2]; 
				int nmask1 = (mask1 % 10) * 10 + c; 
				int nmask2 = (mask2 % 10) * 10 + c;

				int opt1 = dp[nxt][rev[nmask1]][m2] + cost[m1][c];
				int opt2 = dp[nxt][m1][rev[nmask2]] + cost[m2][c];

				dp[now][m1][m2] = max(opt1, opt2);
			}
		}
	}
	printf("%d\n", dp[1][0][0]);
}

Compilation message

miners.cpp: In function 'int main(int, const char**)':
miners.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
miners.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", s + 1); 
  ~~~~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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