QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709108 | #8225. 最小值之和 | miaomiaomiaowu | Compile Error | / | / | C++20 | 4.6kb | 2024-11-04 11:35:22 | 2024-11-04 11:35:22 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MP make_pair
#define pii pair<ll,ll>
const double PI=acos(-1.0);
template <class Miaowu>
inline void in(Miaowu &x){
char c;x=0;bool f=0;
for(c=getchar();c<'0'||c>'9';c=getchar())f|=c=='-';
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
struct fastmod{
typedef unsigned long long u64;
typedef __uint128_t u128;
int m;u64 b;
fastmod(int m):m(m),b(((u128)1<<64)/m){}
int reduce(u64 a){
u64 q=((u128)a*b)>>64;
int r=a-q*m;
return r<m?r:r-m;
}
}z(2);
int n,Lx[81],Rx[81];
ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81];
struct Node{int k,l,r;ll x;}pd[81][81][81];
inline ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){x=1,y=0;return a;}
ll d=exgcd(b,a%b,x,y);
ll x0=x,y0=y;x=y0,y=x0-a/b*y0;
return d;
}
inline pii calc(ll t1,ll m1,ll lim1,ll t2,ll m2,ll lim2){
if(m2<m1)swap(t1,t2),swap(m1,m2),swap(lim1,lim2);
ll X,Y,d=exgcd(t1,t2,X,Y),xx=m2-m1;
if(xx%d!=0)return MP(-1,-1);
X*=xx/d,Y*=xx/d,Y=-Y;
ll mx=0,q1=lcm[t1][t2]/t1,q2=lcm[t1][t2]/t2;
if(X>lim1)mx=max(mx,(X-lim1-1)/q1+1);
if(Y>lim2)mx=max(mx,(Y-lim2-1)/q2+1);
if(mx!=0)X-=q1*mx,Y-=q2*mx;
ll mn;
if(X==lim1||Y==lim2)mn=0;
else mn=min((lim1-X)/q1,(lim2-Y)/q2);
if(mn!=0)X+=mn*q1,Y+=mn*q2;
if(X<0||Y<0)return MP(-1,-1);
return MP(X*t1+m1,min(X/q1,Y/q2));
}
inline void getans(int l,int r,int x,ll nw){
if(l==r)return;
int k=pd[l][r][x].k,xl=pd[l][r][x].l,xr=pd[l][r][x].r;
ll num=(pd[l][r][x].x-nw)/(r-l);
for(int i=l;i<r;i++)ans[i]+=num;
getans(l,k,xl,pd[l][r][x].x);
getans(k+1,r,xr,pd[l][r][x].x);
}
int main(){
for(int i=1;i<=80;i++)for(int j=1;j<=80;j++)
lcm[i][j]=i/__gcd(i,j)*j;
in(n);
memset(dp,-1,sizeof dp);
for(int i=1;i<=n;i++)in(a[i]);
for(int i=1;i<n;i++)if(a[i]==a[i+1])dp[i][i+1][0]=a[i],pd[i][i+1][0]=Node{i,0,0,a[i]};
for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){
mn[i][j]=a[i];
for(int k=i+1;k<=j;k++)mn[i][j]=min(mn[i][j],a[k]);
}
for(int d=3;d<=n;d++){
for(int l=1,r=d;r<=n;l++,r++){
for(int k=l;k<r;k++){
memset(dis,-1,sizeof dis);
if(k==l){
for(int xr=0;xr<r-k-1;xr++)if(dp[k+1][r][xr]!=-1){
ll num=(r-k-1)*dp[k+1][r][xr]+xr;
if(num>=a[l]&&(num-a[l])%(r-k-1)==0){
int rst=a[l]%(r-l);ll qwq=a[l]/(r-l);
if(qwq>dp[l][r][rst])dp[l][r][rst]=qwq,pd[l][r][rst]=Node{k,0,xr,a[l]};
}
}
continue;
}
if(k==r-1){
for(int xl=0;xl<k-l;xl++)if(dp[l][k][xl]!=-1){
ll num=(k-l)*dp[l][k][xl]+xl;
if(num>=a[r]&&(num-a[r])%(k-l)==0){
int rst=a[r]%(r-l);ll qwq=a[r]/(r-l);
if(qwq>dp[l][r][rst])dp[l][r][rst]=qwq,pd[l][r][rst]=Node{k,xl,0,a[r]};
}
}
continue;
}
for(int xl=0;xl<k-l;xl++)if(dp[l][k][xl]!=-1){
for(int xr=0;xr<r-k-1;xr++)if(dp[k+1][r][xr]!=-1){
pii qwq=calc(k-l,xl,dp[l][k][xl],r-k-1,xr,dp[k+1][r][xr]);
if(qwq.first==-1)continue;
int t=lcm[r-k-1][k-l];
while(qwq.second>=0){
ll xx=qwq.first%(r-l),yy=qwq.first/(r-l);
if(yy>dis[xx])dis[xx]=yy,Lx[xx]=xl,Rx[xx]=xr;
qwq.second--,qwq.first-=t;
}
}
}
for(int i=0;i<r-l;i++)if(dis[i]!=-1){
if(dis[i]>dp[l][r][i]){
dp[l][r][i]=dis[i],pd[l][r][i]=Node{k,Lx[i],Rx[i],dis[i]*(r-l)+i};
}
}
}
}
}
if(dp[1][n][0]==-1)return puts("No"),0;
getans(1,n,0,0);
for(int i=1;i<n;i++)for(int j=i;j<n;j++){
mn[i][j]=ans[i];
for(int k=i+1;k<=j;k++)mn[i][j]=min(mn[i][j],ans[k]);
}
for(int i=1;i<=n;i++){
ll qwq=0;
for(int j=1;j<i;j++)qwq+=mn[j][i-1];
for(int j=i;j<n;j++)qwq+=mn[i][j];
if(qwq!=a[i])return puts("No"),0;
}
puts("Yes");
for(int i=1;i<n;i++)cout<<ans[i]<<' ';
return 0;
}
Details
answer.code: In function ‘std::pair<long long int, long long int> calc(ll, ll, ll, ll, ll, ll)’: answer.code:41:16: error: reference to ‘lcm’ is ambiguous 41 | ll mx=0,q1=lcm[t1][t2]/t1,q2=lcm[t1][t2]/t2; | ^~~ In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:58, from answer.code:1: /usr/include/c++/13/numeric:179:5: note: candidates are: ‘template<class _Mn, class _Nn> constexpr std::common_type_t<_Tp1, _Tp2> std::lcm(_Mn, _Nn)’ 179 | lcm(_Mn __m, _Nn __n) noexcept | ^~~ answer.code:28:25: note: ‘ll lcm [81][81]’ 28 | ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81]; | ^~~ answer.code:43:36: error: ‘q2’ was not declared in this scope; did you mean ‘q1’? 43 | if(Y>lim2)mx=max(mx,(Y-lim2-1)/q2+1); | ^~ | q1 answer.code:44:26: error: ‘q2’ was not declared in this scope; did you mean ‘q1’? 44 | if(mx!=0)X-=q1*mx,Y-=q2*mx; | ^~ | q1 answer.code:47:38: error: ‘q2’ was not declared in this scope; did you mean ‘q1’? 47 | else mn=min((lim1-X)/q1,(lim2-Y)/q2); | ^~ | q1 answer.code:48:29: error: ‘q2’ was not declared in this scope; did you mean ‘q1’? 48 | if(mn!=0)X+=mn*q1,Y+=mn*q2; | ^~ | q1 answer.code:50:34: error: ‘q2’ was not declared in this scope; did you mean ‘q1’? 50 | return MP(X*t1+m1,min(X/q1,Y/q2)); | ^~ | q1 answer.code: In function ‘int main()’: answer.code:62:9: error: reference to ‘lcm’ is ambiguous 62 | lcm[i][j]=i/__gcd(i,j)*j; | ^~~ /usr/include/c++/13/numeric:179:5: note: candidates are: ‘template<class _Mn, class _Nn> constexpr std::common_type_t<_Tp1, _Tp2> std::lcm(_Mn, _Nn)’ 179 | lcm(_Mn __m, _Nn __n) noexcept | ^~~ answer.code:28:25: note: ‘ll lcm [81][81]’ 28 | ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81]; | ^~~ answer.code:99:31: error: reference to ‘lcm’ is ambiguous 99 | int t=lcm[r-k-1][k-l]; | ^~~ /usr/include/c++/13/numeric:179:5: note: candidates are: ‘template<class _Mn, class _Nn> constexpr std::common_type_t<_Tp1, _Tp2> std::lcm(_Mn, _Nn)’ 179 | lcm(_Mn __m, _Nn __n) noexcept | ^~~ answer.code:28:25: note: ‘ll lcm [81][81]’ 28 | ll a[81],dp[81][81][81],lcm[81][81],dis[81],mn[81][81],ans[81]; | ^~~