oj.uz

Submission #572623

# Submission time Handle Problem Language Result Execution time Memory
572623 2022-06-04T21:07:16 Z beaconmc Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
#define double long double

using namespace std;

ll n,a,b;
ll nums[2005];
ll dp1[2005];
ll dp2[2005][2005];


ll poww(ll n){
	ll sus = 1;

	FOR(i,0,n){
		sus *= 2;
	}
	return sus;
}
int check(ll v){
	FOR(i,0,n+2) FOR(j,0,n+2) dp2[i][j] = 100;

	FOR(i,0,n+1) dp1[i] = 100;

	dp1[0] = 0;

	if (a==1){
		FOR(i,0,n+1){
			ll cur = 0;
			FOR(x, i+1, n+1){
				cur += nums[x];
				if ((cur&v)==cur) dp1[x] = min(dp1[x], dp1[i] | cur);
			}
		}
		if ((dp1[n]&v)==dp1[n]) return 1;
		return 0;
	}else{
		dp2[0][0] = 0;

		FOR(i,0,n+1){
			FOR(j,0,n+1){
				ll cur = 0;
				FOR(x, i+1, n+1){
					cur += nums[x];
					if ((cur&v)==cur) dp2[x][j+1] = min(dp2[x][j+1], dp2[i][j] | cur);
				}
			}
		}


		FOR(i,a,b+1){
			if ((dp2[n][i]&v) == dp2[n][i]) return 1;
		}
	}


	return 0;

}


int main(){
	cin >> n >> a >> b;
	FOR(i,0,n) cin >> nums[i+1];

	ll sus = (1<<31)-1;

	FORNEG(i, 30, -1){
		sus -= poww(i);
		if (check(sus)) continue;
		else sus += poww(i);
	}
	cout << sus;

}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:71:18: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
   71 |  ll sus = (1<<31)-1;
      |           ~~~~~~~^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -