Submission #603153

#	Time	Username	Problem	Language	Result	Execution time	Memory
603153		DanerZein	Uplifting Excursion (BOI22_vault)	C++14	5 / 100	5058 ms	8020 KiB

vault

#pragma GCC optimize("O2")
#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[abs(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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10