Submission #87777

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
87777	2018-12-02 13:19:51	KCSC	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	158 ms	2340 KiB

sculpture

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int DIM = 2005;
int dp1[DIM]; long long psm[DIM];
bool dp2[DIM][DIM];
bool solve(long long val, int n, int a, int b) {
  long long aux = ((1LL << 50) - 1) ^ val;
  if (a == 1) {
    dp1[0] = 0; 
    for (int i = 1; i <= n; ++i) {
      dp1[i] = b + 1;
      for (int j = i; j >= 1; --j) {
        if (!((psm[i] - psm[j - 1]) & aux)) {
          dp1[i] = min(dp1[i], dp1[j - 1] + 1); } } }
    return dp1[n] <= b; }
  else {
    dp2[0][0] = true;
    for (int k = 1; k <= b; ++k) {  
      for (int i = 1; i <= n; ++i) {
        dp2[k][i] = false;  
        for (int j = i; j >= 1; --j) {
          if (!((psm[i] - psm[j - 1]) & aux)) {
            dp2[k][i] |= dp2[k - 1][j - 1]; } } } }
    for (int k = a; k <= b; ++k) {
      if (dp2[k][n]) { 
        return true; } }
    return false; } }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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