oj.uz

Submission #40711

# Submission time Handle Problem Language Result Execution time Memory
40711 2018-02-06T22:45:02 Z IvanC Bali Sculptures (APIO15_sculpture) C++14
21 / 100
 4 ms 1428 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 110;
const ll INF = (ll)1e17;
ll dp[MAXN][MAXN],soma[MAXN],vetor[MAXN],n,a,b;
ll calc(ll a,ll b){return soma[b] - soma[a-1];}
ll solve(ll pos,ll resta){
	if(pos == n + 1){
		if(resta == 0) return 0;
		else return INF; 
	}
	if(resta <= 0){
		return INF;
	}
	if(dp[pos][resta] != -1) return dp[pos][resta];
	ll best = INF;
	for(int quebra = pos;quebra<=n;quebra++){
		best = min(best, calc(pos,quebra) | solve(quebra+1,resta - 1) );
	}
	return dp[pos][resta] = best;
}	
int main(){
	memset(dp,-1,sizeof(dp));
	cin >> n >> a >> b;
	for(int i = 1;i<=n;i++){
		cin >> vetor[i];
		soma[i] = vetor[i] + soma[i-1];
	}
	ll best = solve(1,a);
	for(int i = a+1;i<=b;i++) best = min(best, solve(1,i) );
	cout << best << endl;
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 1 ms 712 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 1 ms 732 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 1 ms 776 KB Output is correct
12 Correct 2 ms 776 KB Output is correct
13 Correct 2 ms 776 KB Output is correct
14 Correct 2 ms 776 KB Output is correct
15 Correct 2 ms 776 KB Output is correct
16 Correct 1 ms 780 KB Output is correct
17 Correct 2 ms 784 KB Output is correct
18 Correct 2 ms 792 KB Output is correct
19 Correct 2 ms 792 KB Output is correct
20 Correct 2 ms 796 KB Output is correct
21 Incorrect 2 ms 800 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 804 KB Output is correct
2 Correct 2 ms 808 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 872 KB Output is correct
10 Correct 1 ms 916 KB Output is correct
11 Correct 2 ms 916 KB Output is correct
12 Correct 2 ms 916 KB Output is correct
13 Correct 1 ms 916 KB Output is correct
14 Correct 1 ms 916 KB Output is correct
15 Correct 1 ms 916 KB Output is correct
16 Correct 1 ms 916 KB Output is correct
17 Correct 2 ms 916 KB Output is correct
18 Correct 2 ms 916 KB Output is correct
19 Correct 2 ms 916 KB Output is correct
20 Correct 1 ms 916 KB Output is correct
21 Incorrect 2 ms 1012 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1084 KB Output is correct
2 Correct 1 ms 1084 KB Output is correct
3 Correct 1 ms 1084 KB Output is correct
4 Correct 1 ms 1084 KB Output is correct
5 Correct 2 ms 1084 KB Output is correct
6 Correct 2 ms 1084 KB Output is correct
7 Correct 2 ms 1084 KB Output is correct
8 Correct 2 ms 1084 KB Output is correct
9 Correct 1 ms 1084 KB Output is correct
10 Correct 2 ms 1084 KB Output is correct
11 Correct 2 ms 1100 KB Output is correct
12 Correct 2 ms 1100 KB Output is correct
13 Correct 2 ms 1100 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 2 ms 1100 KB Output is correct
20 Correct 1 ms 1228 KB Output is correct
21 Incorrect 2 ms 1228 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 2 ms 1228 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Correct 2 ms 1228 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1228 KB Output is correct
11 Correct 2 ms 1228 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 1 ms 1228 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1228 KB Output is correct
16 Correct 2 ms 1228 KB Output is correct
17 Correct 1 ms 1228 KB Output is correct
18 Correct 2 ms 1340 KB Output is correct
19 Correct 1 ms 1340 KB Output is correct
20 Correct 2 ms 1348 KB Output is correct
21 Correct 2 ms 1348 KB Output is correct
22 Correct 2 ms 1348 KB Output is correct
23 Correct 1 ms 1348 KB Output is correct
24 Correct 2 ms 1348 KB Output is correct
25 Correct 2 ms 1348 KB Output is correct
26 Correct 2 ms 1408 KB Output is correct
27 Correct 2 ms 1408 KB Output is correct
28 Correct 2 ms 1408 KB Output is correct
29 Correct 2 ms 1408 KB Output is correct
30 Correct 2 ms 1408 KB Output is correct
31 Correct 1 ms 1408 KB Output is correct
32 Correct 2 ms 1408 KB Output is correct
33 Correct 1 ms 1408 KB Output is correct
34 Correct 2 ms 1428 KB Output is correct
35 Correct 1 ms 1428 KB Output is correct
36 Correct 2 ms 1428 KB Output is correct
37 Correct 2 ms 1428 KB Output is correct
38 Correct 3 ms 1428 KB Output is correct
39 Correct 3 ms 1428 KB Output is correct
40 Correct 1 ms 1428 KB Output is correct
41 Correct 2 ms 1428 KB Output is correct
42 Correct 3 ms 1428 KB Output is correct
43 Incorrect 2 ms 1428 KB Output isn't correct
44 Halted 0 ms 0 KB -