Submission #1201776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201776		Aviansh	Shortcut (IOI16_shortcut)	C++20	0 / 100	1 ms	328 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>

using namespace std;

long long find_shortcut(int n, vector<int> lens, vector<int> d, int c){
    long long ans = 2e18;
    for(int l = 0;l<n;l++){
        for(int r = l+1;r<n;r++){
            //len inds from l -> r-1
            long long dist = d[0];
            long long maxima = dist;
            for(int i = 0;i<n-1;i++){
                dist+=lens[i];
                if(i==r-1){
                    priority_queue<array<long long,2>,vector<array<long long,2>>, greater<array<long long,2>>>pq;
                    pq.push({0,r});
                    pq.push({c,l});
                    long long di[n];
                    fill(di,di+n,2e18);
                    while(!pq.empty()){
                        array<long long,2> a = pq.top();
                        pq.pop();
                        if(di[a[1]]<=a[0])
                            continue;
                        di[a[1]]=a[0];
                        if(a[1]){
                            pq.push({a[0]+lens[a[1]-1],a[1]-1});
                        }
                        if(a[1]<n-1){
                            pq.push({a[0]+lens[a[1]],a[1]+1});
                        }
                    }
                    for(int i = 0;i<n;i++){
                        if(i==r)
                            continue;
                        di[i]+=d[i];
                    }
                    dist=*max_element(di,di+r);
                }
                maxima=max(maxima,dist+d[i+1]);
                dist=max(dist,(long long)d[i+1]);
            }
            ans=min(ans,maxima);
        }
    }
    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