QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358276 | #8225. 最小值之和 | dengtingyu | 0 | 3ms | 7880kb | C++14 | 1.7kb | 2024-03-19 18:41:35 | 2024-03-19 18:41:35 |
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 81
ll n,a[N];
ll f[N][N][N],pos[N][N][N];
ll len;
inline void push(ll *x,ll *y,ll u,ll v){
if(x[u%len]>u)return ;x[u%len]=u;y[u%len]=v;
return ;
}
inline bool pd(ll *x,ll y,ll l){return y<=x[y%l];}
inline void suan(ll l,ll r,ll x,ll p){
if(l==r)return ;
ll g=pos[l][r][x%(r-l)];
ll u=(f[l][r][x%(r-l)]-x)/(r-l);
x+=u*(r-l);p+=u;
suan(l,g,x,p);
cout<<p<<' ';
suan(g+1,r,x,p);
return ;
}
int main(){
// freopen("test1.in","r",stdin);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
if(n==1){if(!a[1])cout<<"No";else cout<<"Yes";return 0;}
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++){if(a[i]==a[i+1])f[i][i+1][0]=a[i];pos[i][i+1][0]=i;}
for(int i=3;i<=n;i++){
for(int l=1;l+i-1<=n;l++){
ll r=l+i-1;len=r-l;
auto &u=f[l][r],&v=pos[l][r];
if(pd(f[l][r-1],a[r],len-1))push(u,v,a[r],r-1);
if(pd(f[l+1][r],a[l],len-1))push(u,v,a[l],l);
for(int j=l+1;j<r-1;j++){
ll q=j-l,p=r-j-1;ll tem=p*q/__gcd(p,q);
for(int k=0;k<tem;k++){
ll tt=min(f[l][j][k%q],f[j+1][r][k%p]);
if(f[l][j][k%q]==-1||f[j+1][r][k%p]==-1||k>tt)continue;
ll o=k+(tt-k)/tem*tem;for(int t=1;t<=r-l&&o>=0;t++){
push(u,v,o,j);o-=tem;
}
}
}//cout<<l<<' '<<r<<'\n';
// for(int k=0;k<r-l;k++)cout<<k<<' '<<f[l][r][k]<<' ';cout<<'\n';
}
}if(!pd(f[1][n],0,n)){cout<<"No";return 0;}
cout<<"Yes"<<'\n';
suan(1,n,0,0);
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 0ms
memory: 7836kb
input:
5 14 14 12 13 13
output:
Yes 5 3 3 4
result:
ok The answer is correct.
Test #2:
score: 0
Accepted
time: 2ms
memory: 7880kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 1
result:
ok The answer is correct.
Test #3:
score: 0
Accepted
time: 2ms
memory: 7748kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 0
Accepted
time: 2ms
memory: 7784kb
input:
5 11 11 10 5 5
output:
Yes 5 4 1 2
result:
ok The answer is correct.
Test #5:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
5 10 10 10 4 4
output:
Yes 4 4 1 1
result:
ok The answer is correct.
Test #6:
score: 0
Accepted
time: 2ms
memory: 7724kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 0
Accepted
time: 3ms
memory: 7788kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: 0
Accepted
time: 0ms
memory: 7800kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 0
Accepted
time: 2ms
memory: 7744kb
input:
5 10 10 8 5 5
output:
Yes 5 3 1 2
result:
ok The answer is correct.
Test #10:
score: 0
Accepted
time: 2ms
memory: 7784kb
input:
5 24 24 28 28 26
output:
Yes 6 6 9 7
result:
ok The answer is correct.
Test #11:
score: 0
Accepted
time: 0ms
memory: 7748kb
input:
5 5 5 22 31 31
output:
Yes 2 1 10 19
result:
ok The answer is correct.
Test #12:
score: 0
Accepted
time: 2ms
memory: 7836kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 0
Accepted
time: 0ms
memory: 7828kb
input:
5 16 16 4 12 12
output:
Yes 13 1 1 9
result:
ok The answer is correct.
Test #14:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
5 29 29 24 26 26
output:
Yes 11 6 6 8
result:
ok The answer is correct.
Test #15:
score: 0
Accepted
time: 2ms
memory: 7792kb
input:
5 0 33 33 32 32
output:
Yes 0 33 0 32
result:
ok The answer is correct.
Test #16:
score: 0
Accepted
time: 0ms
memory: 7836kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 3ms
memory: 7844kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 0ms
memory: 7832kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 2ms
memory: 7744kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 2ms
memory: 7784kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 0ms
memory: 7832kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 0ms
memory: 7840kb
input:
5 6 7 7 6 6
output:
Yes 2 3 1 3
result:
ok The answer is correct.
Test #23:
score: 0
Accepted
time: 2ms
memory: 7848kb
input:
5 25 25 24 20 20
output:
Yes 8 7 5 5
result:
ok The answer is correct.
Test #24:
score: 0
Accepted
time: 2ms
memory: 7788kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 0ms
memory: 7848kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 2ms
memory: 7800kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 2ms
memory: 7856kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 2ms
memory: 7788kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 2ms
memory: 7784kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 0ms
memory: 7728kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 2ms
memory: 7788kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: -11
Wrong Answer
time: 0ms
memory: 3664kb
input:
1 0
output:
No
result:
wrong answer Line 1 expected
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%