oj.uz

Submission #653542

# Submission time Handle Problem Language Result Execution time Memory
653542 2022-10-27T08:43:36 Z atigun Uplifting Excursion (BOI22_vault) C++14
5 / 100
 5000 ms 2284 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 50;

int M;
ll L;

vector<int> pos(maxn+5), neg(maxn+5);

void solve(){
  cin >> M >> L;
  for(int i = 1; i <= M; i++)
    cin >> neg[M-i+1];
  ll ans;
  cin >> ans;
  for(int i = 1; i <= M; i++)
    cin >> pos[i];
  int maxn3 = maxn*maxn*maxn;
  vector<ll> knapsack1(maxn3+5, -1e18);
  knapsack1[0] = 0;
  for(int i = 1; i <= M; i++){
    for(int make = maxn3; make >= 0; make--){
      for(int use = 1; use <= pos[i] && use*1ll*i <= maxn3; use++){
        if(use*i <= make && knapsack1[make-use*i] != -1e18)
          knapsack1[make] = max(knapsack1[make], knapsack1[make-use*i]+use);
      }
    }
  }
  vector<ll> knapsack2(maxn3+5, -1e18);
  knapsack2[0] = 0;
  for(int i = 1; i <= M; i++){
    for(int make = maxn3; make >= 0; make--){
      for(int use = 1; use <= neg[i] && use*1ll*i <= maxn3; use++){
        if(use*i <= make && knapsack2[make-use*i] != -1e18)
          knapsack2[make] = max(knapsack2[make], knapsack2[make-use*i]+use);
      }
    }
  }
  ll add = -1e18;
  for(int i = 0; i <= maxn3; i++){
    ll need = L-i;
    if(need > 0){
      continue;
    }else if(need == 0){
      add = max(add, knapsack1[i]);
    }else if(-need >= maxn3 || knapsack2[-need] == -1e18 || knapsack1[i] == -1e18){
      continue;
    }else{
      add = max(add, knapsack1[i] + knapsack2[-need]);
    }
  }
  if(add == -1e18){
    cout << "impossible\n";
  }else{
    cout << ans+add;
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while(tt--){
    solve();
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 5 ms 2260 KB Output is correct
4 Correct 18 ms 2260 KB Output is correct
5 Correct 573 ms 2184 KB Output is correct
6 Correct 623 ms 2196 KB Output is correct
7 Correct 269 ms 2268 KB Output is correct
8 Correct 598 ms 2272 KB Output is correct
9 Correct 1218 ms 2184 KB Output is correct
10 Correct 33 ms 2252 KB Output is correct
11 Correct 46 ms 2200 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 5 ms 2260 KB Output is correct
4 Correct 18 ms 2260 KB Output is correct
5 Correct 573 ms 2184 KB Output is correct
6 Correct 623 ms 2196 KB Output is correct
7 Correct 269 ms 2268 KB Output is correct
8 Correct 598 ms 2272 KB Output is correct
9 Correct 1218 ms 2184 KB Output is correct
10 Correct 33 ms 2252 KB Output is correct
11 Correct 46 ms 2200 KB Output is correct
12 Correct 4 ms 2240 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 3 ms 2260 KB Output is correct
15 Correct 14 ms 2260 KB Output is correct
16 Correct 579 ms 2268 KB Output is correct
17 Correct 627 ms 2284 KB Output is correct
18 Correct 264 ms 2280 KB Output is correct
19 Correct 621 ms 2188 KB Output is correct
20 Correct 1263 ms 2188 KB Output is correct
21 Correct 54 ms 2272 KB Output is correct
22 Correct 40 ms 2232 KB Output is correct
23 Runtime error 3364 ms 2188 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2260 KB Output is correct
2 Execution timed out 5031 ms 1236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2260 KB Output is correct
2 Execution timed out 5031 ms 1236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2260 KB Output is correct
2 Execution timed out 5031 ms 1236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 5 ms 2260 KB Output is correct
4 Correct 18 ms 2260 KB Output is correct
5 Correct 573 ms 2184 KB Output is correct
6 Correct 623 ms 2196 KB Output is correct
7 Correct 269 ms 2268 KB Output is correct
8 Correct 598 ms 2272 KB Output is correct
9 Correct 1218 ms 2184 KB Output is correct
10 Correct 33 ms 2252 KB Output is correct
11 Correct 46 ms 2200 KB Output is correct
12 Correct 25 ms 2260 KB Output is correct
13 Execution timed out 5031 ms 1236 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2260 KB Output is correct
2 Execution timed out 5031 ms 1236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 5 ms 2260 KB Output is correct
4 Correct 18 ms 2260 KB Output is correct
5 Correct 573 ms 2184 KB Output is correct
6 Correct 623 ms 2196 KB Output is correct
7 Correct 269 ms 2268 KB Output is correct
8 Correct 598 ms 2272 KB Output is correct
9 Correct 1218 ms 2184 KB Output is correct
10 Correct 33 ms 2252 KB Output is correct
11 Correct 46 ms 2200 KB Output is correct
12 Correct 4 ms 2240 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 3 ms 2260 KB Output is correct
15 Correct 14 ms 2260 KB Output is correct
16 Correct 579 ms 2268 KB Output is correct
17 Correct 627 ms 2284 KB Output is correct
18 Correct 264 ms 2280 KB Output is correct
19 Correct 621 ms 2188 KB Output is correct
20 Correct 1263 ms 2188 KB Output is correct
21 Correct 54 ms 2272 KB Output is correct
22 Correct 40 ms 2232 KB Output is correct
23 Runtime error 3364 ms 2188 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2260 KB Output is correct
2 Execution timed out 5031 ms 1236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2260 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct
3 Correct 5 ms 2260 KB Output is correct
4 Correct 18 ms 2260 KB Output is correct
5 Correct 573 ms 2184 KB Output is correct
6 Correct 623 ms 2196 KB Output is correct
7 Correct 269 ms 2268 KB Output is correct
8 Correct 598 ms 2272 KB Output is correct
9 Correct 1218 ms 2184 KB Output is correct
10 Correct 33 ms 2252 KB Output is correct
11 Correct 46 ms 2200 KB Output is correct
12 Correct 4 ms 2240 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 3 ms 2260 KB Output is correct
15 Correct 14 ms 2260 KB Output is correct
16 Correct 579 ms 2268 KB Output is correct
17 Correct 627 ms 2284 KB Output is correct
18 Correct 264 ms 2280 KB Output is correct
19 Correct 621 ms 2188 KB Output is correct
20 Correct 1263 ms 2188 KB Output is correct
21 Correct 54 ms 2272 KB Output is correct
22 Correct 40 ms 2232 KB Output is correct
23 Runtime error 3364 ms 2188 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -