Submission #1074843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074843		huutuan	Uplifting Excursion (BOI22_vault)	C++14	90 / 100	5064 ms	8540 KiB

vault

#include <bits/stdc++.h>

using namespace std;

using ll=long long;
// #define int long long

const int M=310;
const ll inf=3e18;
int m;
ll L, a[M*2];

void impossible(){
   cout << "impossible\n";
   exit(0);
}

ll tl, tr;

struct Vector{
   ll data[1000000];
   int size;
   Vector(){
      memset(data, -1, sizeof data);
      size=0;
   }
   void reverse(){
      std::reverse(data, data+size);
   }
   void resize(int x){
      while (size>x) data[--size]=-1;
      while (size<x) data[size++]=-1;
   }
   void pop_back(){
      data[--size]=-1;
   }
} f;

void dp(ll power2, vector<pair<ll, ll>> v){
   ll szl=max(0ll, min(m*m*2ll, (tl-(-inf))/power2));
   ll szr=max(0ll, min(m*m*2ll, (inf-tr)/power2));
   tl-=szl*power2, tr+=szr*power2;
   f.reverse();
   f.resize(f.size+szl);
   f.reverse();
   f.resize(f.size+szr);
   for (auto &i:v){
      ll val=i.first, cnt=i.second;
      if (val>0){
         for (int j=f.size-1; j>=val; --j){
            if (f.data[j-val]!=-1) f.data[j]=max(f.data[j], f.data[j-val]+cnt);
         }
      }else{
         for (int j=0; j-val<f.size; ++j){
            if (f.data[j-val]!=-1) f.data[j]=max(f.data[j], f.data[j-val]+cnt);
         }
      }
   }
   f.reverse();
   while (f.size && f.data[f.size-1]==-1){
      tl+=power2;
      f.pop_back();
   }
   f.reverse();
   while (f.size && f.data[f.size-1]==-1){
      tr-=power2;
      f.pop_back();
   }
   if (!f.size) impossible();
   return;
}

vector<pair<ll, ll>> v[50];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> m >> L;
   for (int i=-m; i<=m; ++i) cin >> a[m+i];
   for (int i=-m; i<=m; ++i) if (i){
      ll val=i, cnt=0;
      while (val%2==0) val/=2, ++cnt;
      for (int j=0; j<50; ++j) if (a[m+i]>=(1ll<<j)) v[j+cnt].emplace_back(val, 1ll<<j), a[m+i]-=1ll<<j;
      for (int j=0; j<50; ++j) if (a[m+i]>>j&1) v[j+cnt].emplace_back(val, 1ll<<j);
   }
   tl=0, tr=0, f.data[0]=a[m], f.size=1;
   for (int i=0; i<50; ++i){
      dp(1ll<<i, v[i]);
      if (abs(tl-L)>>i&1){
         tl+=1ll<<i;
         if (!f.size) impossible();
         f.reverse();
         f.pop_back();
         f.reverse();
      }
      if (abs(tr-L)>>i&1){
         tr-=1ll<<i;
         if (!f.size) impossible();
         f.pop_back();
      }
      for (int j=0; j<f.size; j+=2) f.data[j/2]=f.data[j];
      f.resize(f.size/2+1);
   }
   if (tl>L || tr<L) impossible();
   cout << f.data[(L-tl)>>50] << '\n';
   return 0;
}

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