oj.uz

Submission #41414

# Submission time Handle Problem Language Result Execution time Memory
41414 2018-02-17T07:49:34 Z cmaster Bali Sculptures (APIO15_sculpture) C++14
16 / 100
 1000 ms 8976 KB 
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>*/
 
#define pb push_back
#define mp make_pair
#define sz(s) ((int)(s.size()))
#define all(s) s.begin(), s.end()
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, n, a) for (int i = n; i >= a; --i)
#define onlycin ios_base::sync_with_stdio(false); cin.tie(0) 
#define F first
#define S second
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
/*typedef tree<
pair < int, int >,
null_type,
less< pair < int, int > >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
// find_by_order() order_of_key()
const int MAXN = (int)5e5+228;
const char nxtl = '\n';
const int mod = (int)1e9+7;
const double eps = (double)1e-7;
template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

int n, a[MAXN], l, r;
map < pair < int, pair < int, int > >, int > dp;

int rec(int i, int cost, int cnt) {
	if(i == n+1) {
		if(l <= cnt && cnt <= r) return cost;
		return mod;
	}
	if(dp.count(mp(i, mp(cost, cnt)))) return dp[mp(i, mp(cost, cnt))];
	int ans = mod;
	int sum = 0;
	rep(j, i, n) {
		sum += a[j];
		ans = min(ans, rec(j+1, cost | sum, cnt+1));
	}
	return dp[mp(i, mp(cost, cnt))] = ans;
}

int main() {
	#ifdef accepted
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	onlycin;
	cin >> n >> l >> r;
	rep(i, 1, n) cin >> a[i];
	cout << rec(1, 0, 0) << nxtl;
	
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 1 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 3 ms 580 KB Output is correct
10 Correct 2 ms 584 KB Output is correct
11 Correct 2 ms 584 KB Output is correct
12 Correct 2 ms 584 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 1 ms 640 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 2 ms 640 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 2 ms 640 KB Output is correct
21 Correct 2 ms 640 KB Output is correct
22 Correct 2 ms 640 KB Output is correct
23 Correct 2 ms 640 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 2 ms 640 KB Output is correct
26 Correct 3 ms 640 KB Output is correct
27 Incorrect 2 ms 640 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 664 KB Output is correct
11 Correct 2 ms 664 KB Output is correct
12 Correct 2 ms 664 KB Output is correct
13 Correct 3 ms 664 KB Output is correct
14 Correct 1 ms 664 KB Output is correct
15 Correct 2 ms 664 KB Output is correct
16 Correct 2 ms 664 KB Output is correct
17 Correct 2 ms 664 KB Output is correct
18 Correct 2 ms 664 KB Output is correct
19 Correct 2 ms 664 KB Output is correct
20 Correct 2 ms 664 KB Output is correct
21 Correct 3 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Correct 2 ms 748 KB Output is correct
26 Correct 2 ms 748 KB Output is correct
27 Correct 3 ms 748 KB Output is correct
28 Correct 4 ms 748 KB Output is correct
29 Correct 21 ms 1132 KB Output is correct
30 Correct 30 ms 1516 KB Output is correct
31 Correct 102 ms 2324 KB Output is correct
32 Correct 45 ms 2324 KB Output is correct
33 Correct 43 ms 2324 KB Output is correct
34 Correct 61 ms 2324 KB Output is correct
35 Correct 57 ms 2324 KB Output is correct
36 Correct 76 ms 2324 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2324 KB Output is correct
2 Correct 2 ms 2324 KB Output is correct
3 Correct 2 ms 2324 KB Output is correct
4 Correct 1 ms 2324 KB Output is correct
5 Correct 2 ms 2324 KB Output is correct
6 Correct 2 ms 2324 KB Output is correct
7 Correct 2 ms 2324 KB Output is correct
8 Correct 3 ms 2324 KB Output is correct
9 Correct 3 ms 2324 KB Output is correct
10 Correct 2 ms 2324 KB Output is correct
11 Correct 2 ms 2324 KB Output is correct
12 Correct 2 ms 2324 KB Output is correct
13 Correct 2 ms 2324 KB Output is correct
14 Correct 3 ms 2324 KB Output is correct
15 Correct 5 ms 2324 KB Output is correct
16 Correct 21 ms 2324 KB Output is correct
17 Correct 29 ms 2324 KB Output is correct
18 Correct 102 ms 2416 KB Output is correct
19 Correct 44 ms 2416 KB Output is correct
20 Correct 48 ms 2416 KB Output is correct
21 Correct 61 ms 2416 KB Output is correct
22 Correct 56 ms 2416 KB Output is correct
23 Correct 77 ms 2416 KB Output is correct
24 Correct 108 ms 2540 KB Output is correct
25 Correct 374 ms 4892 KB Output is correct
26 Correct 856 ms 8176 KB Output is correct
27 Execution timed out 1070 ms 8976 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8976 KB Output is correct
2 Correct 1 ms 8976 KB Output is correct
3 Correct 2 ms 8976 KB Output is correct
4 Correct 2 ms 8976 KB Output is correct
5 Correct 1 ms 8976 KB Output is correct
6 Correct 2 ms 8976 KB Output is correct
7 Correct 2 ms 8976 KB Output is correct
8 Correct 2 ms 8976 KB Output is correct
9 Correct 3 ms 8976 KB Output is correct
10 Correct 2 ms 8976 KB Output is correct
11 Correct 2 ms 8976 KB Output is correct
12 Correct 2 ms 8976 KB Output is correct
13 Correct 2 ms 8976 KB Output is correct
14 Incorrect 1 ms 8976 KB Output isn't correct
15 Halted 0 ms 0 KB -