Submission #49554

#TimeUsernameProblemLanguageResultExecution timeMemory
49554hamzqq9Bali Sculptures (APIO15_sculpture)C++14
100 / 100
217 ms11604 KiB
#include<bits/stdc++.h> #define lf double #define ll long long #define cc pair<char,char> #define ull unsigned ll #define ii pair<int,int> #define li pair<ll,int> #define iii pair<ii,int> #define iiii pair<ii,ii> #define iiii2 pair<int,iii> #define lii pair<ll,ii> #define lolo pair<ll,ll> #define heap priority_queue #define mp make_pair #define st first #define nd second #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define all(x) x.begin(),x.end() #define len(x) strlen(x) #define sz(x) (int) x.size() #define orta ((bas+son)/2) #define min3(x,y,z) min(min(x,y),z) #define max3(x,y,z) max(max(x,y),z) #define umin(x,y) x=min(x,y) #define umax(x,y) x=max(x,y) #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define MOD 1000000007 #define inf 1000000005 #define M 10000002 #define N 2005 #define LOG 40 #define magic 100 #define KOK 250 #define EPS 0.0025 #define pw(x) ((1ll)<<(x)) #define PI 3.1415926535 using namespace std; int n,a,b; int ar[N],mn[N]; bool dp[105][105]; vector<int> v[N]; bool ok(ll val) { for(int i=1;i<=n;i++) { v[i-1].clear(); mn[i]=inf; ll sum=0; for(int j=i-1;j>=0;j--) { sum+=ar[j+1]; if((sum|val)==val) { v[j].pb(i); umin(mn[i],mn[j]+1); } } } if(a==1) { return (mn[n]<=b); } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int l=1;l<=n;l++) { for(int i=0;i<=n;i++) { if(dp[l-1][i]) { for(int ind:v[i]) { dp[l][ind]=1; } } } } for(int i=a;i<=b;i++) if(dp[i][n]) return true; return false; } int main() { #if 0 freopen("input.txt","r",stdin); #endif scanf("%d %d %d",&n,&a,&b); for(int i=1;i<=n;i++) { scanf("%d",&ar[i]); } ll full=pw(LOG+1)-1; for(int i=LOG;i>=0;i--) { full-=pw(i); if(!ok(full)) full+=pw(i); } printf("%lld",full); }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&ar[i]);
   ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...