oj.uz

Submission #892958

# Submission time Handle Problem Language Result Execution time Memory
892958 2023-12-26T08:59:09 Z LCJLY Miners (IOI07_miners) C++14
52 / 100
 1500 ms 10588 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;

int n;
string s;
int arr[1000005];
int cost[5][5][5];

int dp(int index, int a, int a2, int b, int b2){
	if(index==n) return 0;
	int ans=0;
	
	ans=max(ans,dp(index+1,arr[index],a,b,b2)+cost[a][a2][arr[index]]);
	ans=max(ans,dp(index+1,a,a2,arr[index],b)+cost[b][b2][arr[index]]);
	return ans;
}


void solve(){	
	cin >> n >> s;
	
	for(int x=0;x<n;x++){
		if(s[x]=='M') arr[x]=1;
		else if(s[x]=='B') arr[x]=2;
		else arr[x]=3;
	}
	
	for(int x=0;x<=3;x++){
		for(int y=0;y<=3;y++){
			for(int i=0;i<=3;i++){
				set<int>se;
				se.insert(x);
				se.insert(y);
				se.insert(i);
				if(se.find(0)!=se.end()) se.erase(se.find(0));
				cost[x][y][i]=(int)se.size();
			}	
		}
	}
	
	cout << dp(0,0,0,0,0);
}

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("in.txt", "r", stdin);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1556 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1555 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1542 ms 1116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1542 ms 4700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1509 ms 8796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1549 ms 10588 KB Time limit exceeded
2 Halted 0 ms 0 KB -