oj.uz

Submission #603146

# Submission time Handle Problem Language Result Execution time Memory
603146 2022-07-23T16:03:49 Z DanerZein Uplifting Excursion (BOI22_vault) C++14
0 / 100
 268 ms 8652 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_L=505000;
const int MAX_N=110;
vector<int> mapo(MAX_L);
vector<int> mane(MAX_L);
void maxObjects(vector<int> &x, vector<int> &dp,const int MAX_L){
  for(int i=0;i<x.size();i++){
    if(x[i]==0) continue;
    vector<int> spa;
    for(int j=0;j<=MAX_L;j++){
      if(dp[j]!=0) spa.push_back(j);
    }
    for(int j=0;j<spa.size();j++){
      for(int k=1;k<=x[i];k++){
	dp[spa[j]+(i+1)*k]=max(dp[spa[j]+(i+1)*k],dp[spa[j]]+k);
      }
    }
    for(int k=1;k<=x[i];k++){
      dp[(i+1)*k]=max(dp[(i+1)*k],k);
    }
  }
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int n; ll L; cin>>n>>L;
  vector<int> neg;
  for(int i=0;i<n;i++){
    int a; cin>>a;
    neg.push_back(a);
  }
  reverse(neg.begin(),neg.end());
  int c0; cin>>c0;
  vector<int> pos;
  for(int i=0;i<n;i++){
    int a; cin>>a;
    pos.push_back(a);
  }
  //const int MAX_L=(n*(n+1)/2)*n;
  if(abs(L)>MAX_L){
    cout<<"impossible\n";
    return 0;
  }
  mapo[0]=mane[0]=c0;
  maxObjects(neg,mane,MAX_L);
  maxObjects(pos,mapo,MAX_L);
  int ans;
  if(L>0) ans=mapo[L];
  else ans=mane[L];
  for(int i=0;i<=MAX_L;i++){
    int d=i-L;
    if(d>=0 && mane[d]!=0 && mapo[i]!=0){
      ans=max(ans,mapo[i]+mane[d]-c0);
    }
  }
  if(ans==0) cout<<"impossible\n";
  else
    cout<<ans<<endl;
}

Compilation message

vault.cpp: In function 'void maxObjects(std::vector<int>&, std::vector<int>&, int)':
vault.cpp:9:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |   for(int i=0;i<x.size();i++){
      |               ~^~~~~~~~~
vault.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int j=0;j<spa.size();j++){
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4180 KB Output is correct
2 Correct 7 ms 4180 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 14 ms 4224 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 268 ms 4668 KB Output is correct
7 Runtime error 86 ms 8652 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4180 KB Output is correct
2 Correct 7 ms 4180 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 14 ms 4224 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 268 ms 4668 KB Output is correct
7 Runtime error 86 ms 8652 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4288 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4288 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4288 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4180 KB Output is correct
2 Correct 7 ms 4180 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 14 ms 4224 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 268 ms 4668 KB Output is correct
7 Runtime error 86 ms 8652 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4288 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4180 KB Output is correct
2 Correct 7 ms 4180 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 14 ms 4224 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 268 ms 4668 KB Output is correct
7 Runtime error 86 ms 8652 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4288 KB Output is correct
2 Incorrect 2 ms 4180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4180 KB Output is correct
2 Correct 7 ms 4180 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 14 ms 4224 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 268 ms 4668 KB Output is correct
7 Runtime error 86 ms 8652 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -