Submission #1074824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074824		huutuan	Uplifting Excursion (BOI22_vault)	C++14	90 / 100	5061 ms	11948 KiB

vault

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

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

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

vector<pair<int, int>> v[60];

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){
      int val=i, cnt=0;
      while (val%2==0) val/=2, ++cnt;
      for (int j=0; j<60; ++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<60; ++j) if (a[m+i]>>j&1) v[j+cnt].emplace_back(val, 1ll<<j);
   }
   pair<pair<int, int>, vector<int>> f={{0, 0}, {a[m]}};
   for (int i=0; i<60; ++i){
      dp(1ll<<i, f, v[i]);
      if (abs(f.first.first-L)>>i&1){
         f.first.first+=1ll<<i;
         if (f.second.empty()) impossible();
         f.second.erase(f.second.begin());
      }
      if (abs(f.first.second-L)>>i&1){
         f.first.second-=1ll<<i;
         if (f.second.empty()) impossible();
         f.second.pop_back();
      }
      vector<int> tmp;
      for (int j=0; j<(int)f.second.size(); j+=2) tmp.push_back(f.second[j]);
      tmp.swap(f.second);
   }
   if (f.first.first>L || f.first.second<L) impossible();
   cout << f.second[(L-f.first.first)>>60] << '\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