oj.uz

Submission #197620

# Submission time Handle Problem Language Result Execution time Memory
197620 2020-01-22T04:11:17 Z arnold518 Miners (IOI07_miners) C++14
100 / 100
 287 ms 110372 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;

int N, A[MAXN+10];
int dp[MAXN+10][16][16];

int f(int a, int b, int c)
{
	int cnt[4]={0, 0, 0, 0};
	cnt[a]++; cnt[b]++; cnt[c]++;
	int ret=0;
	for(int i=0; i<3; i++) ret+=(bool)cnt[i];
	return ret;
}

int solve(int pos, int p, int q)
{
	if(pos==N+1) return 0;
	int &ret=dp[pos][p][q];
	if(ret!=-1) return ret;
	ret=0;

	ret=max(ret, solve(pos+1, p%4*4+A[pos], q)+f(p/4, p%4, A[pos]));
	ret=max(ret, solve(pos+1, p, q%4*4+A[pos])+f(q/4, q%4, A[pos]));
	return ret;
}

int main()
{
	int i, j, k;

	scanf("%d", &N);
	for(i=1; i<=N; i++)
	{
		char c;
		scanf(" %c", &c);
		if(c=='M') A[i]=0;
		if(c=='B') A[i]=1;
		if(c=='F') A[i]=2;
	}

	memset(dp, -1, sizeof(dp));
	printf("%d", solve(1, 15, 15));
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:36:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k;
         ^
miners.cpp:36:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
miners.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
miners.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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