Submission #499010

#	Time	Username	Problem	Language	Result	Execution time	Memory
499010		amukkalir	Bali Sculptures (APIO15_sculpture)	C++17	21 / 100	18 ms	31876 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 

const ll INF = 1e15; 
const int nax = 2000; 
ll a, b, n; 
ll y[nax+5]; 
ll p[nax+5]; 
ll dp[nax+5][nax+5]; 

bool ok (int x) {
	return a <= x && x <= b; 
}

ll f(int idx, int grup) {
	if(idx == n+1) return ok(grup) ? 0 : 1e5; 

	ll &res = dp[idx][grup]; 
	if(~res) return res; 

	res = INF; 

	for(int i=idx; i<=n; i++) {
		res = min(res, (p[i] - p[idx-1]) | f(i+1, grup+1)); 
	}
	//cerr << idx << " " << grup << " " << res << endl; 
	return res; 
}

ll rec(int idx, ll sum, ll val, int grup) {
	if(idx==n) return (a <= grup && grup <= b) ? (val | (sum + y[n])) : INF; 
	return min(rec(idx+1, sum+y[idx], val, grup), rec(idx+1, 0, val | (sum+y[idx]), grup+1)); 
}

ll solve1 () {
	memset(dp, -1, sizeof (dp)); 
	return f(1,0); 
}

ll solve2(){
	return rec(1, 0, 0, 1); 
}

mt19937 mt(time(nullptr)); 

ll rand (ll x) {
	unsigned long long m = mt(); 
	return m % x; 
}

int main() {
	scanf("%lld %lld %lld", &n, &a, &b); 

	for(int i=1; i<=n; i++) {
		scanf("%lld", &y[i]); 
		p[i] = y[i] + p[i-1]; 
	}
	
	solve1(); 

	printf("%lld", f(1, 0)); 
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%lld %lld %lld", &n, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%lld", &y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

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