oj.uz

Submission #54545

# Submission time Handle Problem Language Result Execution time Memory
54545 2018-07-04T04:18:15 Z 김세빈(#1491) Miners (IOI07_miners) C++11
100 / 100
 338 ms 676 KB 
#include <bits/stdc++.h>

using namespace std;

char str[101010];
int D[2][256];
int n, ans;

int shift(int p, int t, int x)
{
	if(x == 0) return ((p & 48) << 2) + (t << 4) + (p & 15);
	else return (p & 240) + ((p & 3) << 2) + t;
}

int cost(int p, int t, int x)
{
	int a, b, c;
	
	if(x == 0) a = (p & 192) >> 6, b = (p & 48) >> 4, c = t;
	else a = (p & 12) >> 2, b = p & 3, c = t;
	
	if(b == 0 || (a == 0 && b == c) || (a == b && b == c)) return 1;
	else if(a && b && a != b && b != c && c != a) return 3;
	else return 2;
}

int main()
{
	int i, j, k, t;
	
	scanf("%d%s",&n,str);
	
	for(i=1;i<256;i++) D[1][i] = -1e9;
	
	for(i=0;i<n;i++){
		if(str[i] == 'M') t = 1;
		else if(str[i] == 'F') t = 2;
		else t = 3;
		
		for(j=0;j<256;j++) D[i&1][j] = -1e9;
		
		for(j=0;j<256;j++){
			k = shift(j, t, 0);
			D[i&1][k] = max(D[i&1][k], D[~i&1][j] + cost(j, t, 0));
			
			k = shift(j, t, 1);
			D[i&1][k] = max(D[i&1][k], D[~i&1][j] + cost(j, t, 1));
		}
	}
	
	for(i=0;i<256;i++) ans = max(ans, D[~n&1][i]);
	
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

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

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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