Submission #409444

#	Time	Username	Problem	Language	Result	Execution time	Memory
409444		TLP39	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	186 ms	4420 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);
        }
    }
}

int main()
{
    init();
    if(a==1)
    {
        solve_big();
        printf("%lld",tot);
        return 0;
    }
    ll ans[101][101];
    for(int i=1;i<=n;i++)
    {
        ans[1][i]=qs[i];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            ans[i][j]=(1ll<<50);
            for(int ii=i-1;ii<j;ii++)
            {
                ans[i][j]=min(ans[i][j],ans[i-1][ii]|(qs[j]-qs[ii]));
            }
        }
    }
    ll fin_ans=(1ll<<50);
    for(int i=a;i<=b;i++)
    {
        fin_ans=min(fin_ans,ans[i][n]);
    }
    printf("%lld",fin_ans);
    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: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 29 / 29