Submission #602399

#	Time	Username	Problem	Language	Result	Execution time	Memory
602399		A_D	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	212 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int N=3e3+100;
long long pre[N];
long long pre1[N];
long long suf1[N];
vector<long long> dd;
vector<long long> ll;
long long cc;
int nn;
vector<long long> vec;
vector<long long> co;

deque<pair<int,pair<long long,long long>>> deq;

void ad(int r)
{
    long long u=co[r];
    long long h=vec[r];
    while(deq.empty()==0&&deq.back().S.F+deq.back().S.S<u+h){
        deq.pop_back();
    }
    deq.push_back({r,{h,u}});
}

long long con(int l,int r)
{
//    for(auto x:dd)cout<<x<<" ";cout<<"\n";
  //  for(auto x:ll)cout<<x<<" ";cout<<"\n";
    deq.clear();
    vec.clear();
    co.clear();
    long long ret=0;

    for(int i=1;i<=l;i++){
        ret=max(ret,pre1[i-1]+ll[i-1]+dd[i]);
    }
    for(int i=nn-2;i>=r;i--){
        ret=max(ret,suf1[i+1]+ll[i]+dd[i]);
    }
//    cout<<ret<<"\n";
    long long sum=0;
    for(int j=1;j<=2;j++){
        co.push_back(cc);
        sum+=cc;
        for(int i=l;i<r;i++){
            co.push_back(ll[i]);
            sum+=ll[i];
        }
    }
    sum/=2;

    for(int j=1;j<=2;j++){

        vec.push_back(pre1[l]);
        for(int i=l+1;i<=r-1;i++){
            vec.push_back(dd[i]);
        }
        vec.push_back(suf1[r]);

    }

    cout<<"\n";

//    for(auto x:vec)cout<<x<<" ";cout<<"\n";
  //  for(auto x:co)cout<<x<<" ";cout<<"\n";
    for(int i=1;i<co.size();i++){
        co[i]+=co[i-1];
    }
    //cout<<sum<<"\n";
//    cout<<"\n";
    l=0,r=1;
    deq.push_back({r,{vec[r],co[r]}});
    while(r<vec.size()){
        if(sum-(co[r]-co[l])>=co[r]-co[l]&&l!=r){
            long long u1=deq[0].S.F;
            long long u2=deq[0].S.S;
            u2-=co[l];
            u1+=vec[l];
            ret=max(ret,u1+u2);
        }
        if(sum-(co[r+1]-co[l])>=co[r+1]-co[l]){
            r++;
            ad(r);
        }
        else{
            if(l==r){
                l++;
                r++;
                continue;
            }
            else{
                if(deq.empty()==0&&deq[0].F==l+1){
                    deq.pop_front();
                }
                l++;
            }
        }
    }




    return ret;
}


long long find_shortcut(int n,vector<int> l,vector<int> d,int c)
{
    nn=n;
    cc=c;
    for(auto x:d)dd.push_back((long long)x);
    for(auto x:l)ll.push_back((long long)x);
    pre1[0]=dd[0];
    suf1[nn-1]=dd[nn-1];
    for(int i=1;i<nn;i++){
        pre1[i]=max(pre1[i-1]+ll[i-1],dd[i]);
    }
    for(int i=nn-2;i>=0;i--){
        suf1[i]=max(suf1[i+1]+ll[i],dd[i]);
    }
    pre[0]=l[0];
    for(int i=1;i<n-1;i++){
        pre[i]=pre[i-1]+l[i];
    }
    long long ans=1e18;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
  //          cout<<"\n\n\n";
            long long me=con(i,j);
    //        cout<<i<<" "<<j<<" "<<me<<"\n";
            ans=min(ans,me);
        }
    }
    return ans;
}

/*

2 1
1
0 1000






*/

Compilation message (stderr)

shortcut.cpp: In function 'long long int con(int, int)':
shortcut.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=1;i<co.size();i++){
      |                 ~^~~~~~~~~~
shortcut.cpp:81:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     while(r<vec.size()){
      |           ~^~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3