Submission #285885

#	Time	Username	Problem	Language	Result	Execution time	Memory
285885		Dymo	Portals (BOI14_portals)	C++14	0 / 100	1 ms	384 KiB

portals

#include<bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define all(n) n.begin(),n.end()
#define eb emplace_back
#define endl "\n"
#define pll pair<ll,ll>
#define ff first
#define ss second
using namespace std;
const ll maxn=2e3+5;
const ll mod=998244353;
const ll base=1e15;

ll ans=0;

bool chk(ll p,ll bit)
{
    for (ll i=42; i>=bit; i--)
    {
        if ((ans&(1ll<<i)))
        {
        }
        else
        {
             if (p&(1ll<<i))
                return false;
        }
    }
    return true;
}
ll dp[maxn][maxn];
ll dp1[maxn][maxn];
ll dp2[maxn];
ll dp3[maxn];

ll f[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*if (fopen("terrorists.inp","r"))
    {
        freopen("terrorists.inp","r",stdin);
        freopen("terrorists.out","w",stdout);
    }*/
    ll n, a, b;
    cin>>n>>a>>b;
    for (int i=1; i<=n; i++)
    {
        ll x;
        cin>>x;
        f[i]=f[i-1]+x;

    }

       if (n<=100)
       {

        for (int i=1; i<=b; i++)
        {
            for (int j=i; j<=n; j++)
            {
                dp[i][j]=1;

            }
        }
        for (ll bit=42; bit>=0; bit--)
        {

            for (int i=1; i<=b; i++)
            {
                for (int j=i; j<=n; j++)
                {
                    dp1[i][j]=dp[i][j];

                }
            }
            for (int j=1; j<=n; j++)
            {
                if (!dp1[1][j])
                    continue;

                ll p=f[j];
                 if (!chk(p,bit))
                {
                    dp1[1][j]=0;

                }
            }
            bool kt=false;
            if (dp1[1][n]&&1>=b) kt=true;

            for (int i=2; i<=b; i++)
            {
                for (int j=i; j<=n; j++)
                {
                    if (!dp1[i][j])
                        continue;
                    dp1[i][j]=0;
                    for (int k=j-1; k>=i-1; k--)
                    {
                        if (!dp1[i-1][k])
                            continue;
                        ll p=f[j]-f[k];
                        if (chk(p,bit))
                        {
                            dp1[i][j]=1;
                            break;
                        }
                    }

                }
                if (i>=a&&dp1[i][n])
                    {
                        kt=true;

                    }
            }
            if (kt)
            {

                for (int i=1; i<=b; i++)
                {
                    for (int j=i; j<=n; j++)
                    {
                        dp[i][j]=dp1[i][j];

                    }
                }
            }
            else
            {
                ans=ans+(1ll<<bit);
            }
        }
       }
       else
       {
          for (ll bit=42;bit>=0;bit--)
          {
              for (int i=0;i<=n;i++)
                dp2[i]=dp3[i];
              for (int i=1;i<=n;i++)
              {
                  if(dp2[i]==base) continue;
                  dp2[i]=base;
                  for (int j=i-1;j>=0;j--)
                  {
                      if (dp2[j]==base) continue;

                    ll p= f[i]-f[j];
                     if (chk(p,bit))
                     {
                         dp2[i]=min(dp2[i],dp2[j]+1);

                     }
                  }
                  if (dp2[i]>b) dp2[i]=base;


              }
              if (dp2[n]<=b)
              {
                   for (int i=0;i<=n;i++)
                   {
                       dp3[i]=dp2[i];
                   }
              }
              else
              {
                 ans=ans+(1ll<<bit);
              }
          }
       }



   /* else
    {

    }*/
    cout <<ans<<endl ;



}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30