QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #407023 | #5100. 卡牌游戏 | zwh2008 | Compile Error | / | / | C++14 | 4.8kb | 2024-05-07 21:25:50 | 2024-05-07 21:25:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=5e5+5,M=750;
int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
ll f[N],g[N],mx[N],mx1[N],w[20][N];
template<class T>void gmax(T&x,T y){x=(x>y?x:y);}
void upd(int l,int r,ll v) {
if(l>r)return;
int k=__lg(r-l+1);
gmax(w[k][l],v),gmax(w[k][r-(1<<k)+1],v);
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>S>>type>>tid;
for(int i=1;i<=n;i++)cin>>a[i],a[i]=min(a[i],S+1);
for(int i=1;i<=S+1;i++)b[i]=S/i*i;
int B=sqrt(S);
for(int i=1;i<=B;i++)for(int j=0;j<i;j++)G[i][j]=i/__gcd(i,j);
memset(mx,-0x3f,sizeof(mx));
for(int i=1;i<=n;i++) {
if(a[i]<=B) {
for(int j=i-1,k=(a[j]<=B);j&&k<2;j--,k+=a[j]<=B)gmax(f[i],f[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
for(int j=i+1,k=(a[j]<=B);j<=n&&k<2;j++,k+=a[j]<=B)gmax(f[j],f[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
}else {
f[i]=max(f[i],f[i-1]);
for(int j=a[i];j<=S;j+=a[i])gmax(f[i],mx[j]+j);
for(int j=a[i];j<=S;j+=a[i])mx[j]=f[i];
}
}
cout<<f[n]<<' ';
if(!type)return 0;
memset(mx,-0x3f,sizeof(mx)),memset(mx1,-0x3f,sizeof(mx1));
for(int i=n;i;i--) {
if(a[i]<=B) {
for(int j=i+1,k=(a[j]<=B);j<=n&&k<2;j++,k+=a[j]<=B)gmax(g[i],g[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
for(int j=i-1,k=(a[j]<=B);j&&k<2;j--,k+=a[j]<=B)gmax(g[j],g[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
}else {
gmax(g[i],g[i+1]);
for(int j=a[i];j<=S;j+=a[i])if(lst[j])upd(i+1,lst[j]-1,mx[j]+f[i]+j),gmax(w[0][lst[j]],mx1[j]+f[i]+j),gmax(g[i],mx[j]+j);
for(int j=a[i];j<=S;j+=a[i])mx1[j]=mx[j],lst[j]=i,mx[j]=g[i];
}
}
memset(lst,0,sizeof(lst));
for(int i=1;i<=n;i++)if(a[i]<=B) {
int l=max(1,i-1),r=min(n,i+1);
for(int k=(a[l]<=B);l>1&&k<2;l--,k+=a[l]<=B);
for(int k=(a[r]<=B);r<n&&k<2;r++,k+=a[r]<=B);
ll mx=0;
for(int j=l;j<i;j++)gmax(w[0][j],mx),gmax(mx,f[j]+g[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
mx=0;for(int j=r;j>i;j--)gmax(w[0][j],mx),gmax(mx,f[i]+g[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
}
for(int i=19;i;i--)for(int j=1;j<=n-(1<<i)+1;j++)gmax(w[i-1][j],w[i][j]),gmax(w[i-1][j+(1<<i-1)],w[i][j]);
ll ans=0;
for(int i=1;i<=n;i++)ans^=max(f[i-1]+g[i+1],w[0][i])*i;
cout<<ans<<'\n';
return 0;
}
/*
5 10 1 1
3 2 1 4 5
10 9999 1 1
93 120 538 410 1 248 100 11 45 14
*/#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=5e5+5,M=750;
int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
ll f[N],g[N],mx[N],mx1[N],w[N],lv[20][N],rv[20][N];
template<class T>void gmax(T&x,T y){x=(x>y?x:y);}
void upd(int l,int r,ll v) {
if(l>r)return;int k=__lg(l^r);
assert(k<20&&k>=0&&l>=1&&l<=n&&r>=1&&r<=n);
gmax(lv[k][l],v),gmax(rv[k][r],v);
// for(int i=l;i<=r;i++)gmax(w[i],v);
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>S>>type>>tid;
for(int i=1;i<=n;i++)cin>>a[i],a[i]=min(a[i],S+1);
for(int i=1;i<=S+1;i++)b[i]=S/i*i;
int B=sqrt(S);
for(int i=1;i<=B;i++)for(int j=0;j<i;j++)G[i][j]=i/__gcd(i,j);
memset(mx,-0x3f,sizeof(mx));
for(int i=1;i<=n;i++) {
if(a[i]<=B) {
for(int j=i-1,k=(a[j]<=B);j&&k<2;j--,k+=a[j]<=B)gmax(f[i],f[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
for(int j=i+1,k=(a[j]<=B);j<=n&&k<2;j++,k+=a[j]<=B)gmax(f[j],f[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
}else {
f[i]=max(f[i],f[i-1]);
for(int j=a[i];j<=S;j+=a[i])gmax(f[i],mx[j]+j);
for(int j=a[i];j<=S;j+=a[i])mx[j]=f[i];
}
}
cout<<f[n]<<' ';
if(!type)return 0;
memset(mx,-0x3f,sizeof(mx)),memset(mx1,-0x3f,sizeof(mx1));
for(int i=n;i;i--) {
if(a[i]<=B) {
for(int j=i+1,k=(a[j]<=B);j<=n&&k<2;j++,k+=a[j]<=B)gmax(g[i],g[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
for(int j=i-1,k=(a[j]<=B);j&&k<2;j--,k+=a[j]<=B)gmax(g[j],g[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
}else {
gmax(g[i],g[i+1]);
for(int j=a[i];j<=S;j+=a[i])if(lst[j])upd(i+1,lst[j]-1,mx[j]+f[i]+j),gmax(w[lst[j]],mx1[j]+f[i]+j),gmax(g[i],mx[j]+j);
for(int j=a[i];j<=S;j+=a[i])mx1[j]=mx[j],lst[j]=i,mx[j]=g[i];
}
}
return 0;
memset(lst,0,sizeof(lst));
for(int i=1;i<=n;i++)if(a[i]<=B) {
int l=max(1,i-1),r=min(n,i+1);
for(int k=(a[l]<=B);l>1&&k<2;l--,k+=a[l]<=B);
for(int k=(a[r]<=B);r<n&&k<2;r++,k+=a[r]<=B);
ll mx=0;
for(int j=l;j<i;j++)gmax(w[j],mx),gmax(mx,f[j]+g[i]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
mx=0;for(int j=r;j>i;j--)gmax(w[j],mx),gmax(mx,f[i]+g[j]+b[min(S+1,a[j]*G[a[i]][a[j]%a[i]])]);
}
for(int i=0;i<20;i++) {
for(int j=1;j<=n;gmax(w[j],lv[i][j]),j++)if(j&(1<<i)-1)gmax(lv[i][j],lv[i][j-1]);
for(int j=n;j;gmax(w[j],rv[i][j]),j--)if(j+1&(1<<i)-1)gmax(rv[i][j],rv[i][j+1]);
}
ll ans=0;
for(int i=1;i<=n;i++)ans^=max(f[i-1]+g[i+1],w[i])*i;
cout<<ans<<'\n';
return 0;
}
/*
5 10 1 1
3 2 1 4 5
10 9999 1 1
93 120 538 410 1 248 100 11 45 14
*/
Details
answer.code:74:11: error: redefinition of ‘const int N’
74 | const int N=5e5+5,M=750;
| ^
answer.code:7:11: note: ‘const int N’ previously defined here
7 | const int N=5e5+5,M=750;
| ^
answer.code:74:19: error: redefinition of ‘const int M’
74 | const int N=5e5+5,M=750;
| ^
answer.code:7:19: note: ‘const int M’ previously defined here
7 | const int N=5e5+5,M=750;
| ^
answer.code:75:5: error: redefinition of ‘int n’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:8:5: note: ‘int n’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:75:7: error: redefinition of ‘int S’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:8:7: note: ‘int S’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:75:9: error: redefinition of ‘int type’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^~~~
answer.code:8:9: note: ‘int type’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^~~~
answer.code:75:14: error: redefinition of ‘int tid’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^~~
answer.code:8:14: note: ‘int tid’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^~~
answer.code:75:18: error: redefinition of ‘int a [500005]’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:8:18: note: ‘int a [500005]’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:75:23: error: redefinition of ‘int b [500005]’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:8:23: note: ‘int b [500005]’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:75:28: error: redefinition of ‘int lst [500005]’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^~~
answer.code:8:28: note: ‘int lst [500005]’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^~~
answer.code:75:35: error: redefinition of ‘int G [750][750]’
75 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:8:35: note: ‘int G [750][750]’ previously declared here
8 | int n,S,type,tid,a[N],b[N],lst[N],G[M][M];
| ^
answer.code:76:4: error: redefinition of ‘ll f [500005]’
76 | ll f[N],g[N],mx[N],mx1[N],w[N],lv[20][N],rv[20][N];
| ^
answer.code:9:4: note: ‘ll f [500005]’ previously declared here
9 | ll f[N],g[N],mx[N],mx1[N],w[20][N];
| ^
answer.code:76:9: error: redefinition of ‘ll g [500005]’
76 | ll f[N],g[N],mx[N],mx1[N],w[N],lv[20][N],rv[20][N];
| ^
answer.code:9:9: note: ‘ll g [500005]’ previously declared here
9 | ll f[N],g[N],mx[N],mx1[N],w[20][N];
| ^
answer.code:76:14: error: redefinition of ‘ll mx [500005]’
76 | ll f[N],g[N],mx[N],mx1[N],w[N],lv[20][N],rv[20][N];
| ^~
answer.code:9:14: note: ‘ll mx [500005]’ previously declared here
9 | ll f[N],g[N],mx[N],mx1[N],w[20][N];
| ^~
answer.code:76:20: error: redefinition of ‘ll mx1 [500005]’
76 | ll f[N],g[N],mx[N],mx1[N],w[N],lv[20][N],rv[20][N];
| ^~~
answer.code:9:20: note: ‘ll mx1 [500005]’ previously declared here
9 | ll f[N],g[N],mx[N],mx1[N],w[20][N];
| ^~~
answer.code:76:27: error: conflicting declaration ‘ll w [500005]’
76 | ll f[N],g[N],mx[N],mx1[N],w[N],lv[20][N],rv[20][N];
| ^
answer.code:9:27: note: previous declaration as ‘ll w [20][500005]’
9 | ll f[N],g[N],mx[N],mx1[N],w[20][N];
| ^
answer.code:77:23: error: redefinition of ‘template<class T> void gmax(T&, T)’
77 | template<class T>void gmax(T&x,T y){x=(x>y?x:y);}
| ^~~~
answer.code:10:23: note: ‘template<class T> void gmax(T&, T)’ previously declared here
10 | template<class T>void gmax(T&x,T y){x=(x>y?x:y);}
| ^~~~
answer.code:78:6: error: redefinition of ‘void upd(int, int, ll)’
78 | void upd(int l,int r,ll v) {
| ^~~
answer.code:11:6: note: ‘void upd(int, int, ll)’ previously defined here
11 | void upd(int l,int r,ll v) {
| ^~~
answer.code:84:5: error: redefinition of ‘int main()’
84 | int main() {
| ^~~~
answer.code:16:5: note: ‘int main()’ previously defined here
16 | int main() {
| ^~~~
answer.code: In function ‘int main()’:
answer.code:111:98: error: no matching function for call to ‘gmax(ll [500005], ll)’
111 | for(int...