Submission #1073897

#TimeUsernameProblemLanguageResultExecution timeMemory
1073897ngraceBali Sculptures (APIO15_sculpture)C++14
25 / 100
80 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define v vector #define ll long long #define ii pair<int,int> #define fi first #define se second #define on(i,mask) ((bool)((1<<(i)) & (mask))) int main(){ int N,A,B; cin>>N>>A>>B; v<ll> Y(N+1,0); v<ll> psum(N+1, 0); ll maxY = 0; for(int i=1; i<=N; i++){ cin>>Y[i]; maxY = max(maxY, Y[i]); psum[i] = psum[i-1]+Y[i]; } if(N<=20){//sub1 ll ans = 1e18; for(int div = (1<<N); div<(1<<(N+1)); div++){ int g = 1; int l=0; ll res = 0; for(int i=1; i<=N; i++){ if(i!=1 && on(i-2,div)!=on(i-1,div)){ g++; res = res | (psum[i-1] - psum[l]); l=i-1; } } res = res | (psum[N]-psum[l]); if(A<=g && g<=B) ans = min(ans, res); } cout<<ans<<endl; } else if(N<=50 && B<=20 && maxY<=10){//sub2 v<v<v<bool>>> dp(B+1, v<v<bool>>(N+1, v<bool>(maxY*N+1, false))); dp[0][0][0] = true; for(int b=0; b<B; b++){ for(int n=0; n<=N; n++){ for(int o=0;o<=maxY*N;o++){ if(dp[b][n][o]){//can cover first n in b groups with or sum o for(int i=n+1; i<=N; i++){ dp[b+1][i][o | (psum[i]-psum[n])] = true; } } } } } int ans = maxY*N; for(int b=A; b<=B; b++){ for(int o=0; o<=ans; o++){ if(dp[b][N][o]){ ans=o; break; } } } cout<<ans<<endl; } }
#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...