QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#49387 | #682. Stickers | DerekFeng | 54.545455 | 471ms | 6400kb | C++ | 2.9kb | 2022-09-20 19:32:29 | 2022-09-20 19:32:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
bool comp(vector<int>a,vector<int>b){
if(a.size()!=b.size())return a.size()<b.size();
int n=a.size();
for(int i=n-1;~i;i--)
if(a[i]!=b[i])return a[i]<b[i];
return 0;
}
vector<int>I(vector<int>a,vector<int>b){
vector<int>ans;int jw=0;
int n=a.size(),m=b.size();
for(int i=0;i<max(n,m);i++){
int A=i<n?a[i]:0;
int B=i<m?b[i]:0;
ans.push_back((A+B+jw)%10);
jw=(A+B+jw)/10;
}if(jw)ans.push_back(jw);
return ans;
}
vector<int>D(vector<int>a,vector<int>b){
vector<int>ans;int jw=0;
int n=a.size(),m=b.size();
for(int i=0;i<max(n,m);i++){
int A=i<n?a[i]:0;
int B=i<m?b[i]:0;
A-=B+jw;
if(A<0)A+=10,jw=1;
ans.push_back(A);
}
while(!ans.empty()&&ans.back()==0)ans.pop_back();
return ans;
}
struct BIG{
vector<int>v;bool fu;
BIG(){v.clear(),fu=0;}
void set(int x){
fu=0,v.clear();if(x<0)fu=1,x=abs(x);
while(x)v.push_back(x%10),x/=10;
}
bool operator <(const BIG o){
if(fu!=o.fu)return o.fu<fu;
return comp(v,o.v)^fu;
}
};
BIG f[104][104],s[104][104];
BIG ans,pw[104],fdp[104],sdp[104];
BIG operator +(BIG a,BIG b){
BIG ans;
if(a.fu==b.fu)ans.fu=a.fu,ans.v=I(a.v,b.v);
else{
if(a.fu)swap(a,b);
if(comp(a.v,b.v))ans.fu=1,ans.v=D(b.v,a.v);
else ans.fu=0,ans.v=D(a.v,b.v);
}
return ans;
}
BIG min(BIG a,BIG b){return a<b?a:b;}
void operator +=(BIG &a,const BIG b){a=a+b;}
void write(BIG a){
if(a.fu)putchar('-');
reverse(a.v.begin(),a.v.end());
for(int i=0;i<a.v.size();i++)putchar(a.v[i]+'0');
}
int a[10];
int main(){
for(int i=0;i<10;i++)scanf("%d",&a[i]);
for(int i=0;i<100;i++){
for(int j=0;j<i;j++)pw[i].v.push_back(0);
pw[i].v.push_back(1);
}BIG fu1;fu1.set(-1);
for(int t=0;t<10;t++){
for(int i=0;i<100;i++){
f[0][i].set(min(a[t]-i,0));
s[0][i].set(a[t]-i);
}
for(int i=1;i<100;i++){
fdp[i]=fdp[i-1],sdp[i]=sdp[i-1];
for(int j=0;i+j<100;j++){
f[i][j].set(0);s[i][j].set(0);
for(int c=0;c<10;c++){
f[i][j]=min(f[i][j],s[i][j]+f[i-1][j+(t==c)]);
s[i][j]+=s[i-1][j+(t==c)];
}
}
for(int c=1;c<10;c++){
fdp[i]=min(fdp[i],sdp[i]+f[i-1][t==c]);
sdp[i]+=s[i-1][t==c];
}
}
int cur=0,D;BIG sum,res;
if(!t){
for(int i=1;i<100;i++){
for(int c=1;c<10;c++){
if((sum+f[i-1][0]).fu){
D=i;break;
}
sum+=s[i-1][c==t],res+=pw[i-1];
}
}
}else{
for(int i=99;i;i--){
if(!fdp[i-1].fu){
res+=pw[i-1],res+=fu1,sum=sdp[i-1];
for(int c=1;c<10;c++){
if((sum+f[i-1][c==t]).fu){
D=i;cur+=(c==t);
break;
}
sum+=s[i-1][c==t],res+=pw[i-1];
}
break;
}
}
}
for(int i=D-1;i;i--){
for(int c=0;c<10;c++){
if((sum+f[i-1][cur+(t==c)]).fu){
cur+=(t==c);break;
}
sum+=s[i-1][cur+(t==c)],res+=pw[i-1];
}
}
if(!t)ans=res;
else ans=min(ans,res);
}
write(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 9.09091
Accepted
time: 423ms
memory: 6312kb
input:
1 2 1 1 1 1 1 1 1 1
output:
28263827
result:
ok single line: '28263827'
Test #2:
score: 9.09091
Accepted
time: 420ms
memory: 6308kb
input:
1 2 1 1 1 1 1 1 1 1
output:
28263827
result:
ok single line: '28263827'
Test #3:
score: 0
Wrong Answer
time: 412ms
memory: 6240kb
input:
1 2 2 2 2 1 1 1 1 1
output:
5555254642
result:
wrong answer 1st lines differ - expected: '5555555554', found: '5555254642'
Test #4:
score: 9.09091
Accepted
time: 421ms
memory: 6240kb
input:
2 2 2 2 2 2 2 2 2 2
output:
1999919999999980
result:
ok single line: '1999919999999980'
Test #5:
score: 0
Wrong Answer
time: 427ms
memory: 6400kb
input:
4 3 2 2 2 2 2 2 2 3
output:
282638284214224879
result:
wrong answer 1st lines differ - expected: '282638284722222221', found: '282638284214224879'
Test #6:
score: 0
Wrong Answer
time: 420ms
memory: 6248kb
input:
2 4 3 3 3 3 3 3 3 3
output:
1000124111730625212319
result:
wrong answer 1st lines differ - expected: '1005594043670359641774', found: '1000124111730625212319'
Test #7:
score: 0
Wrong Answer
time: 422ms
memory: 6376kb
input:
4 4 4 4 4 4 3 3 3 3
output:
666304172852237360905223736088
result:
wrong answer 1st lines differ - expected: '666666666666666666666666666665', found: '666304172852237360905223736088'
Test #8:
score: 0
Wrong Answer
time: 412ms
memory: 6340kb
input:
4 5 5 5 5 5 7 8 9 9
output:
100014544250231555116210164232211341723120
result:
wrong answer 1st lines differ - expected: '100559404367035964177652825361730559404364', found: '100014544250231555116210164232211341723120'
Test #9:
score: 9.09091
Accepted
time: 428ms
memory: 6292kb
input:
6 6 6 6 5 5 5 5 5 5
output:
4999999949999999994999999999499999999949999999953
result:
ok single line: '4999999949999999994999999999499999999949999999953'
Test #10:
score: 9.09091
Accepted
time: 422ms
memory: 6216kb
input:
7 8 8 7 7 7 7 7 7 7
output:
371599993999999999399999999939999999993999999999399999999939999999938
result:
ok single line: '371599993999999999399999999939...3999999999399999999939999999938'
Test #11:
score: 9.09091
Accepted
time: 471ms
memory: 6268kb
input:
9 9 9 9 9 9 9 9 9 9
output:
19999199999999919999999991999999999199999999919999999991999999999199999999919999999918
result:
ok single line: '199991999999999199999999919999...1999999999199999999919999999918'