Submission #1283625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283625		stanwaibbange	Shortcut (IOI16_shortcut)	C++20	0 / 100	1 ms	336 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = numeric_limits<ll>::max();

long long find_shortcut(int n, std::vector<int> len, std::vector<int> d, int c)
{
    std::vector<int> ml(n);
    std::vector<int> mr(n);
    ml[0] = d[0];
    for (int i{1};i<n;++i) {
        ml[i] = max(ml[i-1] + len[i-1],d[i]);
    }
    mr[n-1] = d[n-1];
    for (int i{n-2};i>=0;--i) {
        mr[i] = max(mr[i+1] + len[i],d[i]);
    };
     std::vector<int> mll(n);
    std::vector<int> mrr(n);
    mll[0] = d[0];
    for (int i{1};i<n;++i) {
        mll[i] = max(ml[i-1] + len[i-1] + d[i],mll[i-1]);
    }
    mrr[n-1] = d[n-1];
    for (int i{n-2};i>=0;--i) {
        mrr[i] = max(ml[i+1] + len[i] + d[i],mll[i+1]);
    };
    
    vector<ll> pre(n);
    pre[0] = 0;
    for (int i{1}; i < n; ++i)
    {
        pre[i] = pre[i - 1] + len[i - 1];
    }
    ll o = INF;
    for (int l{0}; l < n; ++l)
    {
        for (int r{l+1}; r < n; ++r)
        {
            ll m {0};
            for (int a{l}; a < r; ++a)
            {
                for (int b{a+1}; b <= r; ++b)
                {
                    ll mm{INF};
                    mm = min(mm, pre[b] - pre[a]);
                    mm = min(mm, abs(pre[a] - pre[l]) + c + abs(pre[b] - pre[r]));
                    mm = min(mm, abs(pre[a] - pre[r]) + c + abs(pre[b] - pre[l]));
                    if (a == l) {
                        mm += max(d[a],ml[a]);
                    }
                    else {
                        mm += d[a];
                    }
                    if (b == r) {
                        mm += max(d[b],mr[b]);
                    }
                    else {
                        mm += d[b];
                    }
                    m = max(m,mm);
                }
            }
            o = min(o,m);
        }
    }
    return o;
}

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