QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#731345	#5589. Everything Is A Nail	beamishboys^#	AC ✓	73ms	77104kb	C++23	812b	2024-11-10 02:16:16	2024-11-10 02:16:23

Judging History

你现在查看的是最新测评结果

[2024-11-10 02:16:23]
评测

测评结果：AC
用时：73ms
内存：77104kb

查看

[2024-11-10 02:16:16]
提交

answer

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> vals;

int main() {
	cin >> n;
	vals.resize(n);
	for(auto &v : vals) cin >> v;

	vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(3, vector<int>(1<<3, 0)));

	for(int i=n-1; i>=0; --i) {
		for(int ct=0; ct<3; ++ct) {
			for(int m=0; m<(1<<3); ++m) {
				// need to be able to use ct
				if(!((1<<ct)&m)) continue;

				// skip
				dp[i][ct][m] = dp[i+1][ct][m];
				// take
				if(vals[i] == ct) dp[i][ct][m] = 1 + dp[i+1][ct][m];
				// switch
				else if ((1<<vals[i])&m){
					int ov = dp[i+1][vals[i]][m - (1<<ct)] + 1;
					dp[i][ct][m] = max(dp[i][ct][m], ov);
				}
			}
		}
	}

	cout << max(max(dp[0][0][(1<<3)-1], dp[0][1][(1<<3)-1]), dp[0][2][(1<<3)-1]) << '\n';

	return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3628kb

input:

output:

result:

ok single line: '10'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok single line: '5'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3472kb

input:

1
0

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3472kb

input:

1
1

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

1
2

output:

result:

ok single line: '1'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3752kb

input:

output:

result:

ok single line: '10'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3452kb

input:

output:

result:

ok single line: '5'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

result:

ok single line: '10'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

output:

result:

ok single line: '6'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

output:

result:

ok single line: '7'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok single line: '8'

Test #12:

score: 0

Accepted

time: 0ms

memory: 4028kb

input:

output:

result:

ok single line: '1000'

Test #13:

score: 0

Accepted

time: 1ms

memory: 3768kb

input:

output:

result:

ok single line: '335'

Test #14:

score: 0

Accepted

time: 1ms

memory: 3836kb

input:

output:

result:

ok single line: '1000'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3720kb

input:

output:

result:

ok single line: '372'

Test #16:

score: 0

Accepted

time: 1ms

memory: 4068kb

input:

output:

result:

ok single line: '382'

Test #17:

score: 0

Accepted

time: 1ms

memory: 3868kb

input:

output:

result:

ok single line: '373'

Test #18:

score: 0

Accepted

time: 1ms

memory: 4176kb

input:

output:

result:

ok single line: '2500'

Test #19:

score: 0

Accepted

time: 1ms

memory: 4212kb

input:

output:

result:

ok single line: '835'

Test #20:

score: 0

Accepted

time: 1ms

memory: 4088kb

input:

output:

result:

ok single line: '2500'

Test #21:

score: 0

Accepted

time: 1ms

memory: 4440kb

input:

output:

result:

ok single line: '889'

Test #22:

score: 0

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

ok single line: '890'

Test #23:

score: 0

Accepted

time: 1ms

memory: 4212kb

input:

output:

result:

ok single line: '881'

Test #24:

score: 0

Accepted

time: 3ms

memory: 5812kb

input:

output:

result:

ok single line: '10000'

Test #25:

score: 0

Accepted

time: 3ms

memory: 5816kb

input:

output:

result:

ok single line: '3335'

Test #26:

score: 0

Accepted

time: 3ms

memory: 5756kb

input:

output:

result:

ok single line: '10000'

Test #27:

score: 0

Accepted

time: 3ms

memory: 5788kb

input:

output:

result:

ok single line: '3470'

Test #28:

score: 0

Accepted

time: 3ms

memory: 6044kb

input:

output:

result:

ok single line: '3491'

Test #29:

score: 0

Accepted

time: 3ms

memory: 5976kb

input:

output:

result:

ok single line: '3489'

Test #30:

score: 0

Accepted

time: 64ms

memory: 76880kb

input:

output:

result:

ok single line: '300000'

Test #31:

score: 0

Accepted

time: 64ms

memory: 76908kb

input:

output:

result:

ok single line: '100002'

Test #32:

score: 0

Accepted

time: 73ms

memory: 77104kb

input:

output:

result:

ok single line: '300000'

Test #33:

score: 0

Accepted

time: 70ms

memory: 77036kb

input:

output:

result:

ok single line: '100888'

Test #34:

score: 0

Accepted

time: 68ms

memory: 77080kb

input:

output:

result:

ok single line: '100714'

Test #35:

score: 0

Accepted

time: 60ms

memory: 76916kb

input:

output:

result:

ok single line: '100845'