QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61243#3068. Kitchen Knobschiranko#RE 3ms3356kbC++113.3kb2022-11-11 18:06:352022-11-11 18:06:38

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:06:38]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:3356kb
  • [2022-11-11 18:06:35]
  • 提交

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[7];

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;
		}
		
	}
	
	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 = 0; i < bas; ++i){
		cerr << "res " << i << " " << ressum[i] << endl;
	}
	
	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));
					}
					
//					if(F[tt][i][j][k])
//						cerr << "F " << tt << " " << i << " " << j << " " << k << " " << F[tt][i][j][k] << endl;
				}
				
			}
		}
	}
	assert(F[0][lim[0]][lim[1]][lim[2]] >= 0);
	assert(ans <= n);
	assert(n <= 10);
	ans -= F[0][lim[0]][lim[1]][lim[2]];
	cout << ans;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3356kb

input:

6
9689331
1758824
3546327
5682494
9128291
9443696

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3336kb

input:

7
5941186
3871463
8156346
9925977
8836125
9999999
5987743

output:

2

result:

ok single line: '2'

Test #3:

score: -100
Dangerous Syscalls

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:


result: