Submission #1315680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315680		Luvidi	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	332 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pb push_back

long long find_shortcut(int n, std::vector<int> L, std::vector<int> D, int C)
{   
    ll l[n],d[n];
    for(int i=0;i<n-1;i++)l[i]=L[i];
    l[n-1]=0;
    for(int i=0;i<n;i++)d[i]=D[i];
    ll c=C;

    ll c1[n],c2[n];
    c1[0]=d[0];
    for(int i=1;i<n;i++)c1[i]=max(c1[i-1]+l[i-1],d[i]);
    c2[n-1]=d[n-1];
    for(int i=n-2;i>-1;i--)c2[i]=max(c2[i+1]+l[i],d[i]);

    ll ans=1e18;
    for(int x=0;x<n;x++){
        for(int y=x+1;y<n;y++){
            ll dx=d[x],dy=d[y],ly=l[y];
            d[x]=c1[x];
            d[y]=c2[y];
            l[y]=c;

            ll s=0;
            for(int i=x;i<=y;i++)s+=l[i];
            s/=2;
            multiset<ll> ms;
            ms.insert(d[x]);
            ll mx=0;
            for(ll i=x,j=x,pi=0,pj=0;i<=y;i++){
                while(pj+l[j]-pi<=s){
                    pj+=l[j];
                    j++;
                    if(j>y)j=x;
                    ms.insert(pj+d[j]);
                }
                mx=max(mx,*ms.rbegin()-pi+d[i]);
                ms.erase(ms.find(pi+d[i]));
                pi+=l[i];
            }
            ans=min(ans,mx);
            d[x]=dx;
            d[y]=dy;
            l[y]=ly;
        }
    }

    return ans;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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