I love max and multiply
#include<iostream> #include<cstring> using namespace std; typedef long long LL; const int N=1000010; const int mod=998244353; int T,n; LL a[N],b[N]; LL mxA[N],mxB[N]; LL mnA[N],mnB[N]; int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lld",&a[i]); for(int i=0;i<n;i++) scanf("%lld",&b[i]); LL res=0; LL maxn=-2e18; for(int i=n-1;i>=0;i--){ mxA[i]=mnA[i]=a[i]; mxB[i]=mnB[i]=b[i]; for(int j=0;j<=18;j++){ if(((i>>j)&1)==0){ int x=i+(1<<j); if(x<n){ mxA[i]=max(mxA[i],mxA[x]); mnA[i]=min(mnA[i],mnA[x]); mxB[i]=max(mxB[i],mxB[x]); mnB[i]=min(mnB[i],mnB[x]); } } } maxn=max(maxn,max(mxA[i]*mxB[i],mxA[i]*mnB[i])); maxn=max(maxn,mnA[i]*mxB[i]); maxn=max(maxn,mnA[i]*mnB[i]); res=(res+maxn)%mod; } res=(res+mod)%mod; printf("%lld\n",res); } }
I love exam
#include<iostream> #include<cstring> #include<map> #include<vector> using namespace std; const int N=510; struct node{ int x,y; }; int T; int n,m,t,p; int f[N]; int dp[N][5],tmp[N][5]; map<string,int> mp; vector<node> a[55]; int main(){ cin.tie(0); cout.tie(0); cin>>T; while(T--){ cin>>n; string s; mp.clear(); for(int i=1;i<=n;i++){ cin>>s; mp[s]=i; a[i].clear(); } cin>>m; for(int i=1;i<=m;i++){ int x,y; cin>>s>>x>>y; int id=mp[s]; a[id].push_back({x,y}); } cin>>t>>p; p=min(n,p); memset(dp,-1,sizeof dp); dp[0][0]=0; for(int i=1;i<=n;i++){ memset(f,0,sizeof f); for(auto q:a[i]) for(int j=t;j>=q.y;j--) f[j]=max(f[j],min(100,f[j-q.y]+q.x)); memset(tmp,-1,sizeof tmp); for(int j=0;j<=t;j++) for(int k=0;k<=p;k++){ if(dp[j][k]==-1) continue; for(int d=0;d<=t;d++){ int s=k; if(f[d]<60) s+=1; if(j+d<=t&&s<=p) tmp[j+d][s]=max(tmp[j+d][s],dp[j][k]+f[d]); } } for(int j=0;j<=t;j++) for(int k=0;k<=p;k++) dp[j][k]=tmp[j][k]; } int ans=-1; for(int i=0;i<=t;i++) for(int j=0;j<=p;j++) ans=max(ans,dp[i][j]); printf("%d\n",ans); } }