Submission #619643

#TimeUsernameProblemLanguageResultExecution timeMemory
619643aminBoxes with souvenirs (IOI15_boxes)C++14
100 / 100
672 ms200788 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; long long n,l,k,ans[20000000]; long long s[20000000]; long long tr(long i) { if(i==-1) { return 1e18; } //cout<<i<<endl; //cout<<i<<endl; long long num=n-i*k; long long f=i*l; long long j; //cout<<n<<' '<<i*k<<endl; j=1e18; if(num<=0) { j=min(j,f); return j; } // cout<<num<<endl; // cout<<num<<endl; if(s[n-num]>l/2) { j=min(j,f+ans[n-num]); } for(long y=0;y<num;y++) { // cout<<y<<' '<<i*k+y+1<<endl; f=i*l; if(s[y]>l/2) { break; } if(y+i*k+1==n) { j=min(j,f+ans[y]); break; } //cout<<y<<endl; if(y+i*k+1>n) { break; } if(s[y+i*k+1]<=l/2) { continue; } //cout<<y<<endl; f+=ans[y]; f+=ans[i*k+y+1]; j=min(j,f); // cout<<y<<' '<<i*k+y+1<<endl; } // cout<<i<<' '<<j<<endl; return j; } long long delivery(int N, int K, int L, int p[]) { n=N; k=K; l=L; sort(p,p+n); for(long i=0;i<n;i++) { s[i]=p[i]; } long long preo[n]; long long pree[n]; long long v=0; for(long i=0;i<n;i++) { if(p[i]>l/2) break; if(i<k) { ans[i]=p[i]*2; continue; } ans[i]=ans[i-k]+p[i]*2; } for(long i=n-1;i>=0;i--) { if(p[i]<=l/2) { break; } long long sum=0; if(n-1-i<k) { ans[i]=(l-p[i])*2; continue; } ans[i]=ans[i+k]+(l-p[i])*2; } /* for(long i=0;i<n;i++) { cout<<ans[i]<<endl; }*/ //return v; long long h=1e18; long long f=0; long long i=0; /* long long u=pow(2,25); while(u>n/k) { u/=2; } long long e=u; /* while(u>=1) { u/=2; if(tr(e-u)>tr(e+u)) { e+=u; }else { e-=u; } }*/ return min(tr(0),tr(1)); }

Compilation message (stderr)

boxes.cpp:129:3: warning: "/*" within comment [-Wcomment]
  129 |   /* while(u>=1)
      |    
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:105:18: warning: unused variable 'sum' [-Wunused-variable]
  105 |        long long sum=0;
      |                  ^~~
boxes.cpp:78:14: warning: unused variable 'preo' [-Wunused-variable]
   78 |    long long preo[n];
      |              ^~~~
boxes.cpp:79:14: warning: unused variable 'pree' [-Wunused-variable]
   79 |    long long pree[n];
      |              ^~~~
boxes.cpp:82:14: warning: unused variable 'v' [-Wunused-variable]
   82 |    long long v=0;
      |              ^
boxes.cpp:120:14: warning: unused variable 'h' [-Wunused-variable]
  120 |    long long h=1e18;
      |              ^
boxes.cpp:121:14: warning: unused variable 'f' [-Wunused-variable]
  121 |    long long f=0;
      |              ^
boxes.cpp:122:14: warning: unused variable 'i' [-Wunused-variable]
  122 |    long long i=0;
      |              ^
#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...