QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358245 | #8225. 最小值之和 | dengtingyu | 0 | 2ms | 11724kb | C++14 | 1.6kb | 2024-03-19 18:24:53 | 2024-03-19 18:24:53 |
Judging History
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){return y<=x[y%len];}
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];
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]))push(u,v,a[r],r-1);
if(pd(f[l+1][r],a[l]))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;t++){
push(u,v,o,j);o-=tem;
}
}
}
}
}if(!pd(f[1][n],0)){cout<<"No";return 0;}
cout<<"Yes"<<'\n';
suan(1,n,0,0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 2ms
memory: 11724kb
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: 1ms
memory: 8584kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 1
result:
ok The answer is correct.
Test #3:
score: -11
Wrong Answer
time: 1ms
memory: 8180kb
input:
5 4 13 14 14 13
output:
No
result:
wrong answer Line 1 expected 0g
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%