QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61232 | #3068. Kitchen Knobs | chiranko# | WA | 2ms | 3492kb | C++11 | 3.0kb | 2022-11-11 17:27:55 | 2022-11-11 17:27:57 |
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;
set<int> st;
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 = 0;
for(int i = 1; i <= bas; ++i){
if(ressum[i]){
++cntres;
ok[cntres] = i;
lim[cntres] = ressum[i];
}
}
for(int tt = 0; tt < 7; tt ++){
F[tt] = new int **[lim[0] + 1];
for(int i = 0; i <= lim[0]; ++i){
F[tt][i] = new int *[lim[1] + 1];
for(int j = 0; j <= lim[1]; ++j){
F[tt][i][j] = new int[lim[2] + 1];
}
}
}
//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;
}
}
}
}
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 < 7; 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[tt][i][j][k + 1], F[tt][i][j][k] + (t1 == 0));
}
F[0][i][j][k] = max(F[0][i][j][k], F[tt][i][j][k]);
}
}
}
}
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: 3284kb
input:
6 9689331 1758824 3546327 5682494 9128291 9443696
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
7 5941186 3871463 8156346 9925977 8836125 9999999 5987743
output:
2
result:
ok single line: '2'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3308kb
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:
20
result:
wrong answer 1st lines differ - expected: '18', found: '20'