Submission #580045

#TimeUsernameProblemLanguageResultExecution timeMemory
580045haojiandanUplifting Excursion (BOI22_vault)C++14
20 / 100
5036 ms4956 KiB
// 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; void solve(vector<int> &V,int flag) { 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:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0;i<V.size();i++) {
      |                  ~^~~~~~~~~
vault.cpp:29:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j=max(0LL,i+l);j<=i+r&&j<V.size();j++) {
      |                                         ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...