oj.uz

Submission #1019776

# Submission time Handle Problem Language Result Execution time Memory
1019776 2024-07-11T08:44:52 Z huutuan Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 348 KB 
#include "shortcut.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=4000, inf=1e18, LG=12;
int n, c, pf[N], w[N], d[N];
pair<int, int> st1[LG][N], st2[LG][N];

pair<int, int> get1(int l, int r){
   if (l>r) return {-inf, -1};
   int lg=__lg(r-l+1);
   return max(st1[lg][l], st1[lg][r-(1<<lg)+1]);
}

pair<int, int> get2(int l, int r){
   if (l>r) return {-inf, -1};
   int lg=__lg(r-l+1);
   return max(st2[lg][l], st2[lg][r-(1<<lg)+1]);
}

long long find_shortcut(int32_t _n, vector<int32_t> _l, vector<int32_t> _d, int32_t _c)
{
   n=_n, c=_c;
   for (int i=0; i<n-1; ++i) w[i]=_l[i];
   for (int i=0; i<n; ++i) d[i]=_d[i];
   for (int i=1; i<n; ++i) pf[i]=pf[i-1]+w[i-1];
   for (int i=0; i<n; ++i) st1[0][i]={d[i]+pf[i], i};
   for (int i=0; i<n; ++i) st2[0][i]={d[i]-pf[i], i};
   for (int k=1; k<LG; ++k) for (int i=0; i+(1<<k)-1<n; ++i){
      st1[k][i]=max(st1[k-1][i], st1[k-1][i+(1<<(k-1))]);
      st2[k][i]=max(st2[k-1][i], st2[k-1][i+(1<<(k-1))]);
   }
   int mxd=*max_element(d, d+n);
   int ans=inf;
   for (int i=0; i<n; ++i){
      for (int j=i, mid1=i, mid2=i; j<n; ++j){
         while (mid1<=j && (pf[mid1]-pf[i])*2<c+pf[j]-pf[i]) ++mid1;
         while (mid2<=j && (pf[j]-pf[mid2])*2>=c+pf[j]-pf[i]) ++mid2;
         pair<int, int> mx={0, i};
         pair<int, int> tmp;
         tmp=get1(0, mid1-1); tmp.first+=d[0];
         mx=max(mx, tmp);
         tmp=get2(mid1, j); tmp.first+=d[0]+pf[i]-pf[0]+c+pf[j];
         mx=max(mx, tmp);
         tmp=get1(j+1, n-1); tmp.first+=d[0]-pf[0]+min(0ll, c-(pf[j]-pf[i]));
         mx=max(mx, tmp);
         int u=mx.second;
         mx={0, u};
         if (0<=u && u<=i){
            tmp=get2(0, u-1); tmp.first+=d[u]+pf[u];
            mx=max(mx, tmp);
            tmp=get1(u+1, mid1-1); tmp.first+=d[u]-pf[u];
            mx=max(mx, tmp);
            tmp=get2(mid1, j); tmp.first+=d[u]+pf[i]-pf[u]+c+pf[j];
            mx=max(mx, tmp);
            tmp=get1(j+1, n-1); tmp.first+=d[u]-pf[u]+min(0ll, c-(pf[j]-pf[i]));
            mx=max(mx, tmp);
         }else if (i<=u && u<=j){
            tmp=get2(0, i); tmp.first+=d[u]+pf[i]+min(pf[j]-pf[u]+c, pf[u]-pf[i]);
            mx=max(mx, tmp);
            tmp=get1(j, n-1); tmp.first=d[u]-pf[j]+min(pf[j]-pf[u], pf[u]-pf[i]+c);
            mx=max(mx, tmp);
            int l1=pf[u]-pf[i]; int l2=pf[j]-pf[u];
            int sum=pf[j]-pf[i]+c;
            if (l1*2<=c){
               tmp=get2(i, u-1); tmp.first+=d[u]+pf[u];
               mx=max(mx, tmp);
            }else{
               int l=i, r=u-1;
               while (l<=r){
                  int mid=(l+r)>>1;
                  if ((pf[u]-pf[mid])*2>sum) l=mid+1;
                  else r=mid-1;
               }
               tmp=get2(l, u-1); tmp.first+=d[u]+pf[u];
               mx=max(mx, tmp);
               tmp=get1(i, r); tmp.first+=d[u]+pf[j]-pf[u]+c-pf[i];
               mx=max(mx, tmp);
            }
            if (l2*2<=c){
               tmp=get1(u+1, j); tmp.first+=d[u]-pf[u];
               mx=max(mx, tmp);
            }else{
               int l=u+1, r=j;
               while (l<=r){
                  int mid=(l+r)>>1;
                  if ((pf[mid]-pf[u])*2>sum) r=mid-1;
                  else l=mid+1;
               }
               tmp=get1(u+1, r); tmp.first+=d[u]-pf[u];
               mx=max(mx, tmp);
               tmp=get2(l, j); tmp.first+=d[u]+pf[u]-pf[i]+c+pf[j];
               mx=max(mx, tmp);
            }
         }else{
            tmp=get2(0, i); tmp.first+=d[u]+pf[u]+min(0ll, c-(pf[j]-pf[i]));
            mx=max(mx, tmp);
            tmp=get1(i, mid2-1); tmp.first+=d[u]+pf[u]-pf[j]+c-pf[i];
            mx=max(mx, tmp);
            tmp=get2(mid2, u-1); tmp.first+=d[u]+pf[u];
            mx=max(mx, tmp);
            tmp=get1(u+1, n-1); tmp.first+=d[u]-pf[u];
            mx=max(mx, tmp);
         }
         ans=min(ans, max(mxd, mx.first));
      }
   }
   return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 1 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Incorrect 0 ms 348 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -