답안 #240847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240847	2020-06-21T10:00:32 Z	pavement	Bali Sculptures (APIO15_sculpture)	C++17	21 / 100	32 ms	512 KB

sculpture

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef TEST
#define getchar_unlocked _getchar_nolock
#endif
#define ins insert
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define pp pop
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int ans, N, A, B, Y[2005], P[2005];
char mem[2005][2005];
set<int> S;

bool dp(int n, int x) {
	if (x < 0) return 0;
	if (n == 0) return 1;
	if (mem[n][x] != -1) return mem[n][x];
	bool r = 0;
	for (int i = 0; i < n; i++) {
		bool inv = 0;
		for (int j : S)
			if ((P[n] - P[i]) & (1ll << j)) {
				inv = 1;
				break;
			}
		if (!inv) r |= dp(i, x - 1);
	}
	return mem[n][x] = r;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> A >> B;
	for (int i = 1; i <= N; i++) cin >> Y[i], P[i] = Y[i] + P[i - 1];
	for (int i = 41; i >= 0; i--) {
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= B; j++)
				mem[i][j] = -1;
		S.insert(i);
		bool yes = 0;
		for (int j = A; j <= B; j++)
			if (dp(N, j)) {
				yes = 1;
				break;
			}
		if (!yes) S.erase(i), ans |= (1ll << i);
	}
	cout << ans << '\n';
}

Compilation message

sculpture.cpp: In function 'bool dp(int, int)':
sculpture.cpp:48:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return mem[n][x] = r;
         ~~~~~~~~~~^~~
sculpture.cpp: At global scope:
sculpture.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	512 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	6 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Incorrect	5 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Incorrect	5 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	5 ms	384 KB	Output is correct
17	Correct	6 ms	384 KB	Output is correct
18	Correct	7 ms	384 KB	Output is correct
19	Correct	7 ms	384 KB	Output is correct
20	Correct	5 ms	512 KB	Output is correct
21	Correct	6 ms	384 KB	Output is correct
22	Correct	7 ms	512 KB	Output is correct
23	Correct	7 ms	512 KB	Output is correct
24	Correct	6 ms	512 KB	Output is correct
25	Correct	7 ms	512 KB	Output is correct
26	Correct	9 ms	512 KB	Output is correct
27	Correct	10 ms	512 KB	Output is correct
28	Correct	13 ms	512 KB	Output is correct
29	Correct	32 ms	512 KB	Output is correct
30	Correct	5 ms	512 KB	Output is correct
31	Correct	14 ms	512 KB	Output is correct
32	Correct	15 ms	512 KB	Output is correct

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Incorrect	5 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Incorrect	5 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

답안 #240847

Compilation message

Subtask #1 0 / 9.0

Subtask #2 0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
0 / 9.0

Subtask #2
0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0