QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61251#3068. Kitchen KnobschirankoWA 2ms3360kbC++113.0kb2022-11-11 18:18:342022-11-11 18:18:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 18:18:35]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3360kb
  • [2022-11-11 18:18:34]
  • 提交

answer

#pragma GCC optimize(2) 
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long LL;

const int maxn = 505;
const int INF = 10000;


int ***F[8];

int n;
int pre[maxn];
int bas = 7;
int ressum[maxn], ok[maxn], lim[maxn];

int read(){
	int x = 0, fl = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')
		ch = getchar();
	if(ch == '-')
		ch = getchar(), fl = -1;
	while(isdigit(ch))
		x = x * 10 + ch - '0', ch = getchar();
	return x * fl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	int res = 0;
	for(int i = 1; i <= n; ++i){
		int a = 0;
		cin >> a;
		vector<int> tmp, result;
		for(int j = 1; j <= bas; ++j){
			tmp.pb(a % 10);
			a /= 10;
		}
		reverse(tmp.begin(), tmp.end());
		
		int mx = 0, cntmx = 0; 
		for(int j = 0; j < bas; ++j){
			int sum = 0;
			for(int k = 0; k < bas; ++k){
				sum = sum * 10 + tmp[(j + k) % bas];
			}
			result.pb(sum);
			mx = max(mx, sum);
		}
		
		int mxpos = 0;
		for(int j = 0; j < bas; ++j)
			if(result[j] == mx)
				++cntmx, mxpos = j;
		
		if(cntmx == 1){
			++res;
			pre[res] = (bas - mxpos) % bas;
		}
		
		if(n == 51)
			cout << a << endl;
	}
	
	int ans = 0;
	for(int i = 1; i <= res; ++i){
		int t = (bas + pre[i] - pre[i - 1]) % bas;
		
		if(t)
			++ans, ++ressum[t];
			
	}
		
	
	for(int i = 1; i <= 3; ++i){
		int t = min(ressum[i], ressum[bas - i]);
		ans -= t;
		ressum[i] -= t;
		ressum[bas - i] -= t;
	}
	
	int cntres = -1;
	for(int i = 1; i < bas; ++i){
		if(ressum[i]){
			++cntres;
			ok[cntres] = i;
			lim[cntres] = ressum[i];
		}
	}
	for(int tt = 0; tt < bas; tt ++){
		F[tt] = new int **[lim[0] + 5];
		for(int i = 0; i <= lim[0]; ++i){
			F[tt][i] = new int *[lim[1] + 5];
			for(int j = 0; j <= lim[1]; ++j){
				F[tt][i][j] = new int[lim[2] + 5];
			}
		}
	}
	//array<array<array<array<int,lim[2]+1>,lim[1]+1>,lim[0]+1>,7>F;
		
	
	for(int tt = 0; tt < 7; tt ++){
		for(int i = 0; i <= lim[0]; ++i){
			for(int j = 0; j <= lim[1]; ++j){
				for(int k = 0; k <= lim[2]; ++k){
					F[tt][i][j][k] = -INF;
				}
			}
		}
	}
	
//	cerr << ok[0] << " " << ok[1] << " " << ok[2] << endl;
	F[0][0][0][0] = 0;
	for(int i = 0; i <= lim[0]; ++i){
		for(int j = 0; j <= lim[1]; ++j){
			for(int k = 0; k <= lim[2]; ++k){
				for(int tt = 0; tt < bas; ++tt)
					F[0][i][j][k] = max(F[0][i][j][k], F[tt][i][j][k]);
				for(int tt = 0; tt < bas; tt ++){
					if(F[tt][i][j][k] < 0)
						continue;
					if(i < lim[0]){
						int t1 = (tt + ok[0]) % bas;
						F[t1][i + 1][j][k] = max(F[t1][i + 1][j][k], F[tt][i][j][k] + (t1 == 0));
					}
					if(j < lim[1]){
						int t1 = (tt + ok[1]) % bas;
						F[t1][i][j + 1][k] = max(F[t1][i][j + 1][k], F[tt][i][j][k] + (t1 == 0));
					}
					if(k < lim[2]){
						int t1 = (tt + ok[2]) % bas;
						F[tt][i][j][k + 1] = max(F[t1][i][j][k + 1], F[tt][i][j][k] + (t1 == 0));
					}
				}
				
			}
		}
	}
	ans -= F[0][lim[0]][lim[1]][lim[2]];
	cout << ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3280kb

input:

6
9689331
1758824
3546327
5682494
9128291
9443696

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3360kb

input:

7
5941186
3871463
8156346
9925977
8836125
9999999
5987743

output:

2

result:

ok single line: '2'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3352kb

input:

51
3555761
7422821
8888888
5411437
7917269
4779593
8271171
5969885
6849719
1357882
4735754
5375583
5842146
9964175
5388317
8339466
3333333
7481921
6395917
6392978
5824522
9933964
4212836
3178337
1459877
1298258
5852153
8658819
2222222
4668254
9672735
7531775
9126135
8452455
6525554
9761325
6148958
2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
18

result:

wrong answer 1st lines differ - expected: '18', found: '0'