QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61243 | #3068. Kitchen Knobs | chiranko# | RE | 3ms | 3356kb | C++11 | 3.3kb | 2022-11-11 18:06:35 | 2022-11-11 18:06:38 |
Judging History
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...