Submission #926002

#	Time	Username	Problem	Language	Result	Execution time	Memory
926002		pan	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	90 ms	604 KiB

sculpture

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll const INF = 1e9;
int main()
{
	ll n,a, b;
	input3(n,a,b);
	ll arr[n+1], ps[n+1];
	for (ll i=1; i<=n; ++i) input(arr[i]);
	ps[0] = 0;
	for (ll i=1; i<=n; ++i) {ps[i] = ps[i-1]+arr[i];}
	if (a==1) // fast sol
	{
		ll mask = 0; // 1 if bit must not have, 0 mean can have
		for (ll i=51; i>=0; i--)
		{
			vector<ll> dp(n+1, INF);
			dp[0] = 0;
			mask|=(1LL<<i); // aim to not have most-significant bit
			for (ll j=1; j<=n; ++j)
			{
				for (ll k=1; k<=j; ++k)
				{
					if ((ps[j]-ps[k-1])&mask) continue;
					dp[j] = min(dp[j], dp[k-1]+1);
				}
			}
			if (dp[n]>b) mask^=(1LL<<i); // sorry, must have that bit
		}
		mask^=((1LL<<52)-1);
		print(mask, '\n');
 
	}
	else // slower sol
	{
		ll mask = 0;
		for (ll i=51; i>=0; i--)
		{
			mask|=(1LL<<i);
			vector<vector<ll> > dp(n+1, vector<ll> (n+1, 0));
			dp[0][0] = 1;
			for (ll j=1; j<=n; ++j)
			{
				for (ll k=1; k<=j; ++k)
				{
					for (ll p = 1; p<=j; ++p)
					{
						if ((ps[j]-ps[p-1])&mask) continue;
						dp[j][k] |= dp[p-1][k-1];
					}
				}
			}
			ll can = false;
			for (ll j=a; j<=b; ++j) can|=dp[n][j];
			if (!can) mask^=(1LL<<i);
			
		}
		mask^=((1LL<<52)-1);
		print(mask, '\n');
	}
	
	
	return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:13:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:33:2: note: in expansion of macro 'input3'
   33 |  input3(n,a,b);
      |  ^~~~~~
sculpture.cpp:11:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
sculpture.cpp:35:26: note: in expansion of macro 'input'
   35 |  for (ll i=1; i<=n; ++i) input(arr[i]);
      |                          ^~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29