oj.uz

답안 #961819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961819 2024-04-12T13:57:51 Z vjudge1 Bali Sculptures (APIO15_sculpture) C++14
37 / 100
 6 ms 604 KB 
#include<bits/stdc++.h>

using namespace std;

const int _N=2010;
int a[_N], n, l, r, pf[_N];

namespace sub5{
   const int N=2010;
   bool adj[N][N];
   int f[N];
   bool check(int msk){
      for (int i=0; i<=n; ++i) for (int j=i+1; j<=n; ++j) adj[i][j]=((pf[j]-pf[i])&msk)==0;
      memset(f, 0x3f, sizeof f);
      f[0]=0;
      for (int i=0; i<n; ++i) for (int j=i+1; j<=n; ++j) if (adj[i][j]){
         f[j]=min(f[j], f[i]+1);
      }
      return f[n]<=r;
   }
   void solve(){
      int msk=(1<<30)-1;
      for (int i=29; i>=0; --i){
         if (check((1<<30)-1-(msk^(1<<i)))) msk^=1<<i;
      }
      cout << msk << '\n';
   }
}

namespace sub4{
   const int N=110;
   bool adj[N][N];
   bool f[N][N];
   bool check(int msk){
      for (int i=0; i<=n; ++i) for (int j=i+1; j<=n; ++j) adj[i][j]=((pf[j]-pf[i])&msk)==0;
      memset(f, 0, sizeof f);
      f[0][0]=1;
      for (int i=0; i<n; ++i) for (int j=i+1; j<=n; ++j) if (adj[i][j]){
         for (int k=0; k<n; ++k) f[j][k+1]|=f[i][k];
      }
      return *max_element(f[n]+l, f[n]+r+1);
   }
   void solve(){
      int msk=(1<<30)-1;
      for (int i=29; i>=0; --i){
         if (check((1<<30)-1-(msk^(1<<i)))) msk^=1<<i;
      }
      cout << msk << '\n';
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> l >> r;
   for (int i=1; i<=n; ++i) cin >> a[i];
   partial_sum(a, a+n+1, pf);
   if (n<=100) sub4::solve();
   else sub5::solve();
   return 0;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 396 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 0 ms 348 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 0 ms 352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 352 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 360 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 352 KB Output is correct
17 Correct 0 ms 360 KB Output is correct
18 Correct 0 ms 360 KB Output is correct
19 Correct 1 ms 360 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 504 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 2 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 2 ms 348 KB Output is correct

Subtask #3
21.0 / 21.0

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

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 352 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Incorrect 1 ms 344 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

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