oj.uz

Submission #397024

# Submission time Handle Problem Language Result Execution time Memory
397024 2021-05-01T07:08:42 Z amunduzbaev Bali Sculptures (APIO15_sculpture) C++14
100 / 100
 101 ms 460 KB 
/* 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

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); }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 320 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 316 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 400 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 2 ms 320 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 5 ms 332 KB Output is correct
30 Correct 7 ms 332 KB Output is correct
31 Correct 10 ms 460 KB Output is correct
32 Correct 10 ms 416 KB Output is correct
33 Correct 10 ms 332 KB Output is correct
34 Correct 10 ms 332 KB Output is correct
35 Correct 10 ms 332 KB Output is correct
36 Correct 10 ms 316 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 5 ms 332 KB Output is correct
17 Correct 6 ms 332 KB Output is correct
18 Correct 10 ms 412 KB Output is correct
19 Correct 10 ms 408 KB Output is correct
20 Correct 10 ms 332 KB Output is correct
21 Correct 10 ms 332 KB Output is correct
22 Correct 10 ms 332 KB Output is correct
23 Correct 10 ms 332 KB Output is correct
24 Correct 10 ms 412 KB Output is correct
25 Correct 20 ms 412 KB Output is correct
26 Correct 33 ms 452 KB Output is correct
27 Correct 52 ms 332 KB Output is correct
28 Correct 73 ms 332 KB Output is correct
29 Correct 67 ms 332 KB Output is correct
30 Correct 70 ms 392 KB Output is correct
31 Correct 67 ms 332 KB Output is correct
32 Correct 75 ms 452 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 416 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 2 ms 332 KB Output is correct
39 Correct 5 ms 332 KB Output is correct
40 Correct 6 ms 320 KB Output is correct
41 Correct 12 ms 336 KB Output is correct
42 Correct 10 ms 332 KB Output is correct
43 Correct 11 ms 332 KB Output is correct
44 Correct 10 ms 332 KB Output is correct
45 Correct 10 ms 416 KB Output is correct
46 Correct 10 ms 316 KB Output is correct
47 Correct 10 ms 332 KB Output is correct
48 Correct 20 ms 420 KB Output is correct
49 Correct 34 ms 336 KB Output is correct
50 Correct 53 ms 456 KB Output is correct
51 Correct 68 ms 332 KB Output is correct
52 Correct 79 ms 332 KB Output is correct
53 Correct 73 ms 452 KB Output is correct
54 Correct 68 ms 396 KB Output is correct
55 Correct 69 ms 332 KB Output is correct
56 Correct 8 ms 332 KB Output is correct
57 Correct 25 ms 416 KB Output is correct
58 Correct 39 ms 324 KB Output is correct
59 Correct 50 ms 340 KB Output is correct
60 Correct 49 ms 332 KB Output is correct
61 Correct 48 ms 332 KB Output is correct
62 Correct 53 ms 332 KB Output is correct
63 Correct 52 ms 320 KB Output is correct
64 Correct 52 ms 332 KB Output is correct
65 Correct 9 ms 332 KB Output is correct
66 Correct 15 ms 332 KB Output is correct
67 Correct 24 ms 332 KB Output is correct
68 Correct 38 ms 332 KB Output is correct
69 Correct 49 ms 332 KB Output is correct
70 Correct 58 ms 332 KB Output is correct
71 Correct 51 ms 396 KB Output is correct
72 Correct 52 ms 396 KB Output is correct
73 Correct 51 ms 336 KB Output is correct
74 Correct 51 ms 332 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 412 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 5 ms 332 KB Output is correct
27 Correct 7 ms 332 KB Output is correct
28 Correct 10 ms 412 KB Output is correct
29 Correct 10 ms 332 KB Output is correct
30 Correct 10 ms 332 KB Output is correct
31 Correct 10 ms 332 KB Output is correct
32 Correct 10 ms 332 KB Output is correct
33 Correct 10 ms 332 KB Output is correct
34 Correct 11 ms 332 KB Output is correct
35 Correct 20 ms 332 KB Output is correct
36 Correct 33 ms 388 KB Output is correct
37 Correct 52 ms 392 KB Output is correct
38 Correct 68 ms 332 KB Output is correct
39 Correct 68 ms 388 KB Output is correct
40 Correct 77 ms 332 KB Output is correct
41 Correct 67 ms 332 KB Output is correct
42 Correct 68 ms 332 KB Output is correct
43 Correct 8 ms 332 KB Output is correct
44 Correct 30 ms 332 KB Output is correct
45 Correct 45 ms 332 KB Output is correct
46 Correct 50 ms 332 KB Output is correct
47 Correct 49 ms 332 KB Output is correct
48 Correct 50 ms 332 KB Output is correct
49 Correct 52 ms 388 KB Output is correct
50 Correct 54 ms 388 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 8 ms 332 KB Output is correct
53 Correct 13 ms 344 KB Output is correct
54 Correct 25 ms 332 KB Output is correct
55 Correct 25 ms 332 KB Output is correct
56 Correct 90 ms 332 KB Output is correct
57 Correct 83 ms 340 KB Output is correct
58 Correct 85 ms 332 KB Output is correct
59 Correct 88 ms 332 KB Output is correct
60 Correct 85 ms 332 KB Output is correct
61 Correct 1 ms 204 KB Output is correct
62 Correct 14 ms 332 KB Output is correct
63 Correct 27 ms 332 KB Output is correct
64 Correct 23 ms 332 KB Output is correct
65 Correct 44 ms 332 KB Output is correct
66 Correct 66 ms 332 KB Output is correct
67 Correct 101 ms 332 KB Output is correct
68 Correct 94 ms 344 KB Output is correct
69 Correct 88 ms 332 KB Output is correct