Untitled

 avatar
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...