QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61250 | #3068. Kitchen Knobs | chiranko | WA | 4ms | 3488kb | C++11 | 3.0kb | 2022-11-11 18:18:07 | 2022-11-11 18:18:08 |
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[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)
cerr << 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: 3304kb
input:
6 9689331 1758824 3546327 5682494 9128291 9443696
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
7 5941186 3871463 8156346 9925977 8836125 9999999 5987743
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 4ms
memory: 3356kb
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:
18
result:
ok single line: '18'
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 3352kb
input:
51 1111111 5555555 5497193 1811365 8859453 6886872 7634217 3237143 4444444 3422896 6353449 3791691 9188945 7244531 7112132 8922591 7448166 6576374 7189671 7985791 3825273 9642994 8876381 4823917 3855491 3723917 9424184 5263364 5542214 6319672 5138439 7212896 9999999 2122863 3284475 4376758 1841928 5...
output:
20
result:
wrong answer 1st lines differ - expected: '21', found: '20'