oj.uz

Submission #31128

# Submission time Handle Problem Language Result Execution time Memory
31128 2017-08-10T22:27:19 Z nibnalin Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 0 ms 17728 KB 
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = int(2e3)+5, inf = int(1e9)+5;

int A[maxn], dp[maxn][maxn];

int compute(int idx, int k, int l, int r)
{
	pair<int, int> res = {inf, -1};
	for(int i = max(idx+1, l);i <= r;i++)
	{
		int c = dp[k-1][i]|(A[i-1]-A[idx-1]);
		//cout << idx << " " << i << " " << c << "\n";
		if(c < res.first) res = {c, i};
	}
	dp[k][idx] = res.first;
	return res.second;
}

void solve(int L, int R, int optL, int optR, int k)
{
	int mid = (L+R)/2;
	int loc = compute(mid, k, optL, optR);
	if(mid < R) solve(mid+1, R, loc, optR, k);
	if(L < mid) solve(L, mid-1, optL, loc, k);
}

int main(void)
{
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	for(int i = 1;i <= n;i++) scanf("%d", &A[i]);
	for(int i = 1;i <= n;i++) A[i] += A[i-1];

	for(int i = 1;i <= n;i++) dp[1][i] = A[n]-A[i-1];

	for(int i = 2;i <= b;i++) solve(1, n, 1, n, i);
	printf("%d\n", dp[b][1]);
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &a, &b);
                             ^
sculpture.cpp:35:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i <= n;i++) scanf("%d", &A[i]);
                                              ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17728 KB Output is correct
2 Incorrect 0 ms 17728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17728 KB Output is correct
2 Incorrect 0 ms 17728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17728 KB Output is correct
2 Incorrect 0 ms 17728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17728 KB Output is correct
2 Incorrect 0 ms 17728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17728 KB Output is correct
2 Incorrect 0 ms 17728 KB Output isn't correct
3 Halted 0 ms 0 KB -