Submission #397024

#TimeUsernameProblemLanguageResultExecution timeMemory
397024amunduzbaevBali Sculptures (APIO15_sculpture)C++14
100 / 100
101 ms460 KiB
/* made by amunduzbaev */
/*
made by T1mofey778 : 

                    iiisrr;;r;,,,,;..,;;:..:rSs                                                      
                    isisrr:;r;,,,,;..,;;:..sSS5XS                                                    
                    isisrr:;r;,,,,;..:;;:.r2SSSX25
                    isirrr:;r;,,.::..:;;:.5SSSS2222S
                    ssirrr:;r;,,.::..:;;:55SSSS22X225Ss,rrrrr;
                    ssir;;:;;;,.,::..:;;,5SSSSS222s;::::;;;::,,,,,,:.
                    siis;;::;;,..::..:;:rSSSi5;;:rSSSSSSiiiiiSi;siiiis:;
                    siis;;::;;,..:,..:;:5S55r;sS5SSSSSSSSSSiSSiiiiiiiiii;:s
                    siss;;::;:,.,:,..::rSS;r55S5SS5SSSSiSiSSSSSSSSSiSSSSSSs:r       ;isssssrss
                    sssr;::;;:,.,:..,;:irS5555555Ss2SSSSSi 5SSSSSSSSSSSSSSSSS;iiSiiissssssrrs
                    ssir;:::;:,..:..,:rs5555555i;55S52S2   ,S5S555S55S555555SSriiiiiissssssss
                    rsir;:::;:,.,;..r 5555525r r55555.      S55555i55555555555SSSiiiiiiissi5,
                    rssr;:::;:,,.;:i.S5522555.555252        S25S555i2525555255555iiiiiiiS55s
                    rssr;::,;S  S s:55222255s22552           255255i5222222S22222222225555i
                    rssr:;       ii22222225i2225.            225;25Si2222225S2222222222225
                    rsr;   .     s5222222252222              X22S225r2222222SXX2222222222S
                    ;srr       ,iS5222222552,5               5225222;2222222iX2222222222S
                    rrs:       ii222225 .52 X                2252222i2222222S22222222225s   ;s5i
                    rrr;,.:i .SiS52222. i2                   525522Xi2222222sS222222225ir,;i  ..:;:
                    ;rrr      r525255.  5                    5Xi225522222222i222222525Sissi;r,rssss
                    rrr    .  i555555   s                    25 522S25222222s22X2:5SXiiSS55555SSS5i
                    i        Si5552:                         2  522SXX222225i522X  Si    r555S52S5S
                             sS5522 .225S2                      255 2222222Si2225  .      5S5i55
                            ss5555252  2522:                    525 2222222iS22s  i ;      5S2S5r
                            ii55522:i ;525r2                    55  2222222i52i             5S
                            ii55555 . i55S55           iisS55S2 5   2222222i22,
            :        .      si5555.   s,;i2              5522225i   2222225i22    . .
          SS                i55525     ;2;               S5525 52S  2222225S55       ;
        :iSSi           :   s55222                       si55S2 52  222222S252      :  ,   .
       5SSiiiSs           r:s5555S                        s Ss ,    252255ii5S
     25SSSSSiSSs        :,;:s5525                                   222255i s        .
   55SSSSSSSSSSiS      ;r,;:i5522                                   222225S s;
 5SSSSSSSSSSSSiSi5S   rrr::;i5522                                   25222S  52
SSSSSSSSSSSSSSS5S     sr;:,:i5222s                                  52222i X22
SSSSSSSSSSS5SSS2      ...   i55222                                 S22225522XX           ,
55555555SSS522        rrr:::S525252                                25522i2222
SS55555555525         rrr,;:S522222;         .                   ,s22255S2222.
555555S5225S          sr;,;:S222222.,                           59322225X2225s           .
55555555S2S          ;ss;:;:S222222 :                           X,52222S22222
55555555552,         ris::r:r2XX222 , .                           22225222222
5555555525S22.,SS    rrs::r:;5XX222..                5S          222225222225  .i5s      ,
555555X25555555552.  r;s::r:;52X222,..  5222225X22X;            iX222225X222X SSSSSS5i
5522X25555555555555S5555555555XX222;  .:55X25  r                22X225S 522225SSSSSSS52i5s           .
555555555555555555555555555555XX22S                            :XX2X5   2X55 55SSSSSSSSiSS           
555555555555555555525555555555XX225                            XXX22         SSSSSSSSSSSis           
5555555555555555555525555555555X2X2              .             22X25        SSSSSSSSS5SSS;           
52S5S55S555555555555522555555552X2X              :            i2325         5S5555SSSSSSS;           
    5555555555555555552X2555555.X22              .           :XX22:         2S5555SSSSSSS            
       25S55555255555552XXX25S2 ;XX                          XXX2X          555555SSSS5Si            
         55555552255555552XXXXi  3X                          222i          55555555SSS5SS            
            5S22552255555552X2    X                         3X5S          55555555555SS5S            
               255252555555522    5:                       rX32         :55S555555555SSSi            
                   2252255552      2                       X2          ;5525555555555SSSS            
                     si5X252.                      .      2X          :5552555555555555SS            
siisssiiiiisississssisss;:s5                             3S           S5552255555555555S5            
SS555S555SSSS55555SSSsss;;S2                            .            2222525555555555555S            
ssiiisiiiiiiiiiiisssisis;;X2       .:rr:,   ,                       522X5222555555555555Ss           
iiiiiiiiiiiiiiiiiiiiissr;r22522255255555255X.XX2SrS                2552XX5222222255555555            
iiiiiiiiiiiiiiiiiiiiiiir:52222222222525isi5i5i522522XXX           2225XXXX222222252555552            
iiiiiiiiiiiiiiiiiiiiiiis;2222222222s5X22252222S5225222522i        2222XXXX222222222255555           
iiiiiSiiiiiiiiiiiiiiSiis;222222222sXX5S5i222S222S5522222222225   X2222XX33X2222222225555             
iiiiiiiiiiiiiiiiiissiiis5222222222S2252iX222ii52XXS5222222222222X2X222X3333X22222222252              
SSSSS5SSSSSSSSSSSSSSSiis2222222222222Xi22222sXs52XXSS22222222222222222X3333 .522222225               
55SS55555555555555555SssX22222222222XS52X2XXS222i2ii25X222222222222222233X    5222222      

*/

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define tut(x) array<int, x> 
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
 
template<class T> bool umin(T& a, const T& b) { return a > b? a = b, true:false; }
template<class T> bool umax(T& a, const T& b) { return a < b? a = b, true:false; }
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); }
//template<class T> tree<T, 
//less<T>, null_type, rb_tree_tag, 
//tree_order_statistics_node_update> ordered_set;
 
const int N = 2e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
const int B = 500;

#define MULTI 0
int n, m, ans, q, k, res, a[N];
int b, dp[N], pref[N], num;
bool check(int a, int b) { return (((a>>b) | num) == num); }

/*

6 1 3
8 1 2 1 5 4

*/

void solve(int t_case){
	cin>>n;
	if(n <= 100){
		int l, r; cin>>l>>r;
		vv<vii> dp(105, vii(105, 0));
		for(int i=1;i<=n;i++) cin>>a[i], pref[i] = pref[i-1] + a[i];
		for(int b=45;b>=0;b--){
			for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j] = 0;
			dp[0][0] = 1;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					for(int l=0;l<i;l++){
						if(check(pref[i] - pref[l], b)) dp[i][j] |= dp[l][j-1];
					}
				}
			} 
			
			bool ok = 1;
			for(int i=l;i<=r;i++) if(dp[n][i]) ok = 0;
			if(ok) num += 1;
			num<<=1;
		} num>>=1; cout<<num<<"\n";
	} else {
		cin>>b, assert(b == 1), cin>>b;
		for(int i=1;i<=n;i++) cin>>a[i], pref[i] = pref[i-1] + a[i];
		num = 0;
		for(int bit=45;bit>=0;bit--){
			for(int i=1;i<=n;i++) dp[i] = mod;
			for(int i=1;i<=n;i++){
				//if(check(pref[i], bit)) dp[i] = 1;
				for(int j=0;j<i;j++) if(check(pref[i] - pref[j], bit)) umin(dp[i], dp[j] + 1);
			} 
			if(dp[n] > b) num += 1;
			num <<= 1; 
		} num >>=1; cout<<num<<"\n";\
	}
}
 
signed main(){ 
	NeedForSpeed
	if(!MULTI) {
		solve(1);
	} else {
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'void usaco(std::string)':
sculpture.cpp:100:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  100 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:101:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  101 |  freopen((s+".out").c_str(),"w",stdout); }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...