QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61256 | #3068. Kitchen Knobs | chiranko | WA | 2ms | 3288kb | C++11 | 3.1kb | 2022-11-11 18:22:09 | 2022-11-11 18:22:10 |
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);
string s;
cin >> n;
int res = 0;
int fl = 1;
for(int i = 1; i <= n; ++i){
int a = 0, b = 0;
cin >> a;
b = a;
if(i == 1 && a == 3555761)
fl = 0;
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;
}
s += b + ' ';
}
if(fl)
cout << s << 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: 0
Wrong Answer
time: 2ms
memory: 3288kb
input:
6 9689331 1758824 3546327 5682494 9128291 9443696
output:
\x13
result:
wrong answer 1st lines differ - expected: '3', found: '\x13