Submission #580320

#	Time	Username	Problem	Language	Result	Execution time	Memory
580320		haojiandan	Uplifting Excursion (BOI22_vault)	C++14	100 / 100	1501 ms	7172 KiB

vault

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
    t=0; char ch=getchar(); int f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
    if (t<0) { putchar('-'); write(-t); return; }
    if (t>9) write(t/10);
    putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=300*300+10;
const ll INF=1e18;
int m;
ll rub[maxn];
ll L,sum,ans;
ll *a,*b,*now=rub;
ll f[maxn*2],g[maxn*2];
int N=300*300+2;
ll l,r;
int hd,tl,q[maxn*2];
ll dp[maxn*2];
void solve(vector<int> &V,int flag) {
    for (int i=0;i<V.size();i++) g[V[i]]=-INF;
    hd=1,tl=0;
    int R=-1;
    for (int i=0;i<V.size();i++) {
        while (R+1<V.size()&&R+1<=i+r) {
            R++;
            ll tmp=f[V[R]]+(flag?-R:R);
            while (hd<=tl&&dp[tl]<tmp) tl--;
            q[++tl]=R,dp[tl]=tmp;
        }
        while (hd<=tl&&q[hd]<i+l) hd++;
        assert(hd<=tl);
        g[V[i]]=dp[hd]+(flag?i:-i);
    }/*
    for (int i=0;i<V.size();i++) {
        g[V[i]]=-INF;
        for (int j=max(0LL,i+l);j<=i+r&&j<V.size();j++) {
            g[V[i]]=max(g[V[i]],f[V[j]]+(flag?i-j:j-i));
        }
    }*/
}
int main() {
    //freopen("1.txt","r",stdin);
    read(m); read(L);
    now+=m,a=now,now+=m+1,now+=m,b=now,now+=m+1;
    for (int i=-m;i<=m;i++) read(a[i]),sum+=a[i]*i;
    if (sum<L) {
        reverse(a-m,a+m+1),sum*=-1,L*=-1;
    }
    sum=0; for (int i=-m;i<0;i++) sum+=a[i]*i,b[i]=a[i];
    if (sum>L) { puts("impossible"); return 0; }
    for (int i=0;i<=m;i++) {
        if (!i) b[i]=a[i]; else b[i]=min(a[i],(L-sum)/i);
        sum+=b[i]*i;
        //printf(" %lld\n",b[i]);
    }
    //printf("%lld %lld\n",sum,L);
    for (int i=-m;i<=m;i++) ans+=b[i];
    //printf("> %lld\n",ans);
    //N=10;
    for (int i=-N;i<=N;i++) f[i+N]=-INF;
    f[N]=0;
    for (int i=-m;i<=m;i++) if (i!=0) {
        if (i<0) l=0,r=a[i]; else l=-b[i],r=a[i]-b[i];
        //printf(" %d %lld %lld\n",i,abs(i)*l,abs(i)*r);
        l*=-1,r*=-1,swap(l,r);
        vector<int> V1;
        for (int j=0;j<abs(i);j++) {
            V1.clear();
            for (int k=j;k>=-N;k-=abs(i)) V1.push_back(k+N);
            reverse(V1.begin(),V1.end());
            for (int k=j+abs(i);k<N;k+=abs(i)) V1.push_back(k+N);
            solve(V1,(i>0?1:0));
        }
        for (int j=0;j<N*2;j++) f[j]=g[j];
    }
    //printf("> %lld %lld\n",L-sum,f[L-sum+N]);
    if (f[L-sum+N]+ans>=0) printf("%lld\n",f[L-sum+N]+ans);
    else puts("impossible");
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
 
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
   
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
   
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Compilation message (stderr)

vault.cpp: In function 'void solve(std::vector<int>&, int)':
vault.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0;i<V.size();i++) g[V[i]]=-INF;
      |                  ~^~~~~~~~~
vault.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i=0;i<V.size();i++) {
      |                  ~^~~~~~~~~
vault.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while (R+1<V.size()&&R+1<=i+r) {
      |                ~~~^~~~~~~~~

• 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: 10 / 10