QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#326668 | #8225. 最小值之和 | linrui | 0 | 2ms | 8752kb | C++14 | 2.7kb | 2024-02-13 18:14:07 | 2024-02-13 18:14:08 |
answer
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using u64=unsigned long long;
using LF=long double;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define CT const&
#define IL inline
#define PB push_back
template<class T>
IL void tomn(T &x,T CT y){y<x?x=y,0:0;}
template<class T>
IL void tomx(T &x,T CT y){x<y?x=y,0:0;}
#define DEBUG(x) cerr<<"line:"<<__LINE__<<" "#x"="<<x<<endl
#define CUT cerr<<"**********\n"
const LF EPS=1e-10L;
IL int dcmp(LF x){return fabs(x)<=EPS?0:(x<0?-1:1);}
const LL INF=4e18L;
const int N=85;
void exgcd(int a,int b,int &x,int &y,int &g){
if(!b)return x=1,y=0,g=a,void();
exgcd(b,a%b,y,x,g),y-=(a/b)*x;
}
IL int mod(int x,int y){return x%=y,x+(x<0)*y;}
IL int dv(int x,int y){return (x-mod(x,y))/y;}
struct D{int x,m;}f[N][N][N];
bool operator<(D x,D y){return x.x<y.x;}
int n,g[N],ans[N];
void dfs(int l,int r,int x){
if(l==r)return;
D d=f[l][r][x%(r-l)];
F(i,l,r-1)ans[i]+=(d.x-x)/(r-l);
dfs(l,d.m,d.x),dfs(d.m+1,r,d.x);
}
IL bool ck(int l,int r,int x){return x<=f[l][r][x%(r-l)].x;}
IL void to(int l,int r,D x){tomx(f[l][r][x.x%(r-l)],x);}
int main(){
#ifdef LOCAL
freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
#endif
scanf("%d",&n);
if(n==1)puts("Yes"),exit(0);
F(i,1,n)scanf("%d",g+i);
F(i,0,N-1)F(j,0,N-1)F(k,0,N-1)f[i][j][k]=D{-1};
G(l,n,1)F(r,l,n){
if(l==r){
f[l][l][0]=D{g[l]};
continue;
}if(l==r-1){
if(g[l]==g[r])tomx(f[l][r][0],D{g[l],l});
continue;
}
F(m,l,r-1){
if(m==l){
if(ck(l+1,r,g[l]))to(l,r,D{g[l],m});
continue;
}if(m==r-1){
if(ck(l,r-1,g[r]))to(l,r,D{g[r],m});
continue;
}int p=m-l,q=r-m-1,x,y,g,L,M=r-l;
exgcd(p,q,x,y,g),L=p/g*q,M/=__gcd(L,M);
int mn1=max(dv(-x*g+q-1,q),dv(y*g+p-1,p));
int mn2=max(dv(x*g+q-1,q),dv(-y*g+p-1,p));
F(i,0,L-1){
int j=i%p,k=i%q,a=f[l][m][j].x,b=f[m+1][r][k].x;
if(a<0||b<0)continue;
int c=a-p/g*(a-b)*(x+q/g*(a>=b?mn1:-mn2));
// if(!ck(l,m,c)||!ck(m+1,r,c)){
// cerr<<"!!! "<<p<<" "<<q<<" "<<g<<endl;
// cerr<<x+mn1*q/g<<" "<<y-mn1*p/g<<endl;
// cerr<<x-mn2*q/g<<" "<<y+mn2*p/g<<endl;
// cerr<<-x*g<<" "<<q<<" "<<dv(-x*g+q-1,q)<<endl;
// cerr<<x*g<<" "<<q<<" "<<dv(x*g+q-1,q)<<endl;
// cerr<<-y*g<<" "<<p<<" "<<dv(-y*g+p-1,p)<<endl;
// cerr<<y*g<<" "<<p<<" "<<dv(y*g+p-1,p)<<endl;
// cerr<<"!!! "<<p<<" "<<q<<" "<<g<<endl
// <<a<<" "<<x<<" "<<b<<" "<<y<<" "<<c<<endl;
// cerr<<(x+q/g*(a>=b?mn1:-mn2))<<endl;
// }
F(j,0,M-1){
if(c<0)break;
to(l,r,D{c,m}),c-=L;
}
}
}
}if(!ck(1,n,0))puts("No");
puts("Yes"),dfs(1,n,0);
F(i,1,n-1)printf("%d ",ans[i]);
}
詳細信息
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 11
Accepted
time: 2ms
memory: 8712kb
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: 0ms
memory: 8684kb
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: 8664kb
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: 8676kb
input:
5 11 11 10 5 5
output:
Yes 6 5 0 5
result:
ok The answer is correct.
Test #5:
score: 0
Accepted
time: 2ms
memory: 8588kb
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: 0ms
memory: 8596kb
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: 2ms
memory: 8752kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: -11
Memory Limit Exceeded
input:
5 2 2 6 11 11
output:
result:
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%