Submission #68367

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
68367	2018-08-16 20:43:07	thebes	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	127 ms	2456 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;
typedef long long ll;
const int MN=2002,LG=45;
ll N, A, B, ans, i, j, k, psa[MN], mn[MN];
bitset<MN> dp[MN];
bool idk(ll m){
  for(i=2;i<=N+1;i++) mn[i]=1<<30;
  for(i=1;i<=N;i++){
    for(j=i+1;j<=N+1;j++){
      if((m|(psa[j-1]-psa[i-1]))!=m) continue;
      mn[j] = min(mn[j], mn[i]+1);
    }
  }
  return mn[N+1]<=B;
}
bool check(ll m){
  if(A==1) return idk(m);
  for(i=1;i<=N;i++) dp[i].reset();
  dp[0][0] = 1;
  for(i=1;i<=N;i++){
    for(j=i;j>=1;j--){
      if((m|(psa[i]-psa[j-1]))!=m) continue;
      for(k=0;k<B;k++) if(dp[j-1][k]) dp[i][k+1]=1;
    }
  }
  for(i=A;i<=B;i++) if(dp[N][i]) return 1;
  return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&N,&A,&B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:35:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&psa[i]),psa[i]+=psa[i-1];
   ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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