QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#49398 | #682. Stickers | DerekFeng | 100 ✓ | 487ms | 6404kb | C++ | 2.9kb | 2022-09-20 22:07:37 | 2022-09-20 22:07:39 |
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,jw=0;
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=0;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][0],res+=pw[i-1];
}
if(D)break;
}
}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);
}
詳細信息
Test #1:
score: 9.09091
Accepted
time: 413ms
memory: 6244kb
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: 414ms
memory: 6404kb
input:
1 2 1 1 1 1 1 1 1 1
output:
28263827
result:
ok single line: '28263827'
Test #3:
score: 9.09091
Accepted
time: 417ms
memory: 6308kb
input:
1 2 2 2 2 1 1 1 1 1
output:
5555555554
result:
ok single line: '5555555554'
Test #4:
score: 9.09091
Accepted
time: 405ms
memory: 6308kb
input:
2 2 2 2 2 2 2 2 2 2
output:
1999919999999980
result:
ok single line: '1999919999999980'
Test #5:
score: 9.09091
Accepted
time: 487ms
memory: 6168kb
input:
4 3 2 2 2 2 2 2 2 3
output:
282638284722222221
result:
ok single line: '282638284722222221'
Test #6:
score: 9.09091
Accepted
time: 408ms
memory: 6244kb
input:
2 4 3 3 3 3 3 3 3 3
output:
1005594043670359641774
result:
ok single line: '1005594043670359641774'
Test #7:
score: 9.09091
Accepted
time: 418ms
memory: 6232kb
input:
4 4 4 4 4 4 3 3 3 3
output:
666666666666666666666666666665
result:
ok single line: '666666666666666666666666666665'
Test #8:
score: 9.09091
Accepted
time: 422ms
memory: 6232kb
input:
4 5 5 5 5 5 7 8 9 9
output:
100559404367035964177652825361730559404364
result:
ok single line: '100559404367035964177652825361730559404364'
Test #9:
score: 9.09091
Accepted
time: 418ms
memory: 6376kb
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: 423ms
memory: 6328kb
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: 426ms
memory: 6132kb
input:
9 9 9 9 9 9 9 9 9 9
output:
19999199999999919999999991999999999199999999919999999991999999999199999999919999999918
result:
ok single line: '199991999999999199999999919999...1999999999199999999919999999918'