Submission #409461

#	Time	Username	Problem	Language	Result	Execution time	Memory
409461		TLP39	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	167 ms	4256 KiB

sculpture

#include <stdio.h>
#include <math.h>
#include <utility>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pp;

int n,a,b;
ll y[2001];
ll qs[2001]={};
bool cango[2001][2001];
int dist[2001];
ll tot=0;

void init()
{
    scanf("%d %d %d",&n,&a,&b);
    qs[0]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&y[i]);
        qs[i]=qs[i-1]+y[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            cango[i][j]=true;
        }
    }
}

bool checkgo(int p,int q,int r)
{
    return ((qs[q]-qs[p])>>r)&1;
}

bool testgo(int r)
{
    dist[0]=0;
    for(int i=1;i<=n;i++) dist[i]=1000000;
    for(int i=0;i<n;i++)
    {
        if(dist[i]==1000000) continue;
        for(int j=i+1;j<=n;j++)
        {
            if(!cango[i][j]) continue;
            if(!checkgo(i,j,r)) dist[j]=min(dist[j],dist[i]+1);
        }
        if(dist[n]<=b) return true;
    }
    return false;
}

void solve_big()
{
    bool res;
    for(int i=40;i>=0;i--)
    {
        res=testgo(i);
        if(res)
        {
            for(int j=0;j<n;j++)
            {
                for(int ii=j+1;ii<=n;ii++)
                {
                    if(checkgo(j,ii,i)) cango[j][ii]=false;
                }
            }
        }
        else
        {
            tot|=(1ll<<i);
        }
    }
}

ll tot2=0;

bool checksm(int st,int ed,int r)
{
    return tot2==(tot2|(((qs[ed]-qs[st])>>r)<<r));
}

bool cando[101][101];

void getsm(int r,int aa)
{
    if(aa==1)
    {
        for(int i=1;i<=n;i++)
        {
            cando[aa][i]=checksm(0,i,r);
        }
        return;
    }
    for(int i=aa;i<=n;i++)
    {
        for(int j=aa-1;j<i;j++)
        {
            cando[aa][i]=cando[aa-1][j] && checksm(j,i,r);
            if(cando[aa][i]) break;
        }
    }
}

void solve_small()
{
    bool ch;
    for(int i=40;i>=0;i--)
    {
        ch=false;
        for(int j=1;j<=n;j++)
        {
            getsm(i,j);
        }
        for(int j=a;j<=b;j++)
        {
            ch=ch|cando[j][n];
        }
        if(!ch) tot2|=(1ll<<i);
    }
}

int main()
{
    init();
    if(a==1)
    {
        solve_big();
        printf("%lld",tot);
        return 0;
    }
    solve_small();
    printf("%lld",tot2);
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'void init()':
sculpture.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d %d",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%lld",&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29