# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
409444 | TLP39 | Bali Sculptures (APIO15_sculpture) | C++14 | 186 ms | 4420 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |