QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358276#8225. 最小值之和dengtingyu0 3ms7880kbC++141.7kb2024-03-19 18:41:352024-03-19 18:41:35

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 18:41:35]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:7880kb
  • [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%