oj.uz

Submission #882409

# Submission time Handle Problem Language Result Execution time Memory
882409 2023-12-03T07:08:39 Z vjudge1 Bali Sculptures (APIO15_sculpture) C++17
37 / 100
 132 ms 27308 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n, a, b, A[N], pref[N];
bool dp[105][105][2200];
void solve(){
  cin >> n >> a >> b;
  for(int i = 1; i <= n; ++i) cin >> A[i];
  pref[0] = 0;
  for(int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + A[i];
  for(int i = 0; i <= n; ++i) for(int l = 0; l <= n; ++l) for(int j = 0; j <= 5000 ;++j) dp[i][l][j] = 0;
  dp[0][0][0] = 1;
  for(int i = 1; i <= n; ++i){
    for(int j = 0; j < i; ++j){
      for(int k = 1; k <= j + 1; ++k){
        for(int s = 0; s <= pref[j]; ++s){
          dp[i][k][(pref[i] - pref[j]) | s] |= dp[j][k - 1][s];
        }
      }
    }
  } 
  int ans = MOD;
  for(int i = a; i <= b; ++i){
    for(int j = 0; j <= pref[n]; ++j) if(dp[n][i][j]) ans = min(ans, j);
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:41:15: warning: unused variable 'aa' [-Wunused-variable]
   41 |   int tt = 1, aa;
      |               ^~
sculpture.cpp: In function 'void solve()':
sculpture.cpp:20:102: warning: iteration 2200 invokes undefined behavior [-Waggressive-loop-optimizations]
   20 |   for(int i = 0; i <= n; ++i) for(int l = 0; l <= n; ++l) for(int j = 0; j <= 5000 ;++j) dp[i][l][j] = 0;
      |                                                                                          ~~~~~~~~~~~~^~~
sculpture.cpp:20:76: note: within this loop
   20 |   for(int i = 0; i <= n; ++i) for(int l = 0; l <= n; ++l) for(int j = 0; j <= 5000 ;++j) dp[i][l][j] = 0;
      |                                                                          ~~^~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 1 ms 10584 KB Output is correct
12 Correct 2 ms 10584 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6744 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 10588 KB Output is correct
22 Correct 1 ms 10588 KB Output is correct
23 Correct 1 ms 10588 KB Output is correct
24 Correct 1 ms 10588 KB Output is correct
25 Correct 2 ms 10584 KB Output is correct
26 Correct 1 ms 10584 KB Output is correct
27 Runtime error 7 ms 12892 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 1 ms 10588 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 10588 KB Output is correct
22 Correct 2 ms 10768 KB Output is correct
23 Correct 2 ms 10588 KB Output is correct
24 Correct 2 ms 10588 KB Output is correct
25 Correct 2 ms 10584 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 1 ms 10588 KB Output is correct
28 Correct 2 ms 10588 KB Output is correct
29 Correct 3 ms 14680 KB Output is correct
30 Correct 3 ms 14684 KB Output is correct
31 Correct 7 ms 16988 KB Output is correct
32 Correct 7 ms 16988 KB Output is correct
33 Correct 6 ms 16988 KB Output is correct
34 Correct 5 ms 16984 KB Output is correct
35 Correct 5 ms 16988 KB Output is correct
36 Correct 5 ms 17240 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 2 ms 10664 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 1 ms 10588 KB Output is correct
14 Correct 1 ms 10764 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 7 ms 16988 KB Output is correct
19 Correct 7 ms 16984 KB Output is correct
20 Correct 6 ms 16984 KB Output is correct
21 Correct 4 ms 16732 KB Output is correct
22 Correct 5 ms 16988 KB Output is correct
23 Correct 5 ms 16988 KB Output is correct
24 Correct 7 ms 16984 KB Output is correct
25 Correct 16 ms 21084 KB Output is correct
26 Correct 32 ms 23200 KB Output is correct
27 Correct 55 ms 27228 KB Output is correct
28 Correct 74 ms 27292 KB Output is correct
29 Correct 132 ms 27224 KB Output is correct
30 Correct 127 ms 27224 KB Output is correct
31 Correct 89 ms 27308 KB Output is correct
32 Correct 101 ms 27228 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 1 ms 10584 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8536 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 2 ms 10588 KB Output is correct
23 Correct 1 ms 10588 KB Output is correct
24 Correct 1 ms 10588 KB Output is correct
25 Correct 1 ms 10588 KB Output is correct
26 Correct 1 ms 10588 KB Output is correct
27 Runtime error 6 ms 13088 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8696 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10704 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 1 ms 10588 KB Output is correct
14 Runtime error 7 ms 12904 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -