Submission #197620

#	Time	Username	Problem	Language	Result	Execution time	Memory
197620		arnold518	Miners (IOI07_miners)	C++14	100 / 100	287 ms	110372 KiB

miners

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8