Untitled
unknown
plain_text
4 years ago
4.1 kB
7
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long int #define fi first #define se second ll maxi[10001][4][4]={0}; ll fun(ll n,ll p,ll q) { ll dp[p+1]; dp[0]=0; for(ll i=1;i<=p;i++){ dp[i]=-1e13; } for(ll mm=1;mm<=n;mm++) { ll dp2[p+1]; for(ll i=1;i<=p;i++){ dp2[i]=-1e13; } dp2[0]=0; for(ll i=1;i<=p;i++) { ll sum=max(maxi[mm][1][1],max(maxi[mm][2][1],maxi[mm][3][1])); if(i==p) { dp2[0]=max(dp2[0],dp[i-1]+sum*q); break; } dp2[i]=max(dp[i-1]+sum,dp2[i]); } for(ll i=1;i<=p;i++) { ll sum=maxi[mm][1][1]+maxi[mm][1][2]; ll temp=maxi[mm][1][1]; if(i==p) { dp2[0]=max(dp2[0],dp[i-2]+sum+temp*(q-1)); continue; } if(i==1) { dp2[1]=max(dp[p-1]+sum+temp*(q-1),dp2[1]); continue; } dp2[i]=max(dp2[i],dp[i-2]+sum); } for(ll i=1;i<=p;i++) { ll sum=maxi[mm][1][1]+maxi[mm][1][2]+maxi[mm][1][3]; ll temp=maxi[mm][1][1]; if(i==p) { dp2[0]=max(dp2[0],dp[i-3]+sum+temp*(q-1)); continue; } if(i==1) { dp2[1]=max(dp[p-2]+sum+temp*(q-1),dp2[1]); continue; } if(i==2) { dp2[2]=max(dp[p-1]+sum+temp*(q-1),dp2[2]); continue; } dp2[i]=max(dp2[i],dp[i-3]+sum); } for(ll i=1;i<=p;i++) { ll sum=maxi[mm][1][1]+maxi[mm][2][1]; ll temp=maxi[mm][2][1]; ll gg=maxi[mm][1][1]; if(i==p) { dp2[0]=max(dp2[0],dp[i-2]+sum+max(temp,gg)*(q-1)); continue; } if(i==1) { dp2[1]=max(dp2[1],dp[p-1]+sum+max(temp,gg)*(q-1)); continue; } dp2[i]=max(dp[i-2]+sum,dp2[i]); } for(ll i=0;i<=p-1;i++) { dp[i]=max(dp[i],dp2[i]); } } sort(dp,dp+p+1); return dp[p]; } void solve() { ll n,p,q,ct,r,s; cin>>n>>ct; ll gg[n+1]; pair<ll,ll> pp[ct+1]; for(ll mm=1;mm<=n;mm++) { cin>>gg[mm]; } for(ll i=1;i<=ct;i++){ cin>>pp[i].fi>>pp[i].se; } cin>>p>>q>>r>>s; ll curr=1; for(ll mm=1;mm<=n;mm++) { for(ll i=1;i<=3;i++){ for(ll j=1;j<=3;j++){ maxi[mm][i][j]=-1e13; } } for(ll i=1;i<=gg[mm];i++) { ll c,d; c=pp[curr].fi,d=pp[curr].se; if(c==300){ c=1; } else if(c==500){ c=2; } else c=3; ll cur=d; for(ll j=1;j<=3;j++) { if(cur>=maxi[mm][c][j]) { swap(cur,maxi[mm][c][j]); } } curr++; } } ll ans1=fun(n,p,q),ans2=fun(n,r,s); if(ans1>ans2){ cout<<"ALICE"<<" "<<ans1-ans2<<endl; } else cout<<"BOB"<<" "<<ans2-ans1<<endl; } int main(){ solve(); }
Editor is loading...