Submission #1283623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283623		stanwaibbange	Shortcut (IOI16_shortcut)	C++20	31 / 100	2094 ms	432 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] + l[i-1],d[i]);
    // }
    // mr[n-1] = d[n-1];
    // for (int i{n-2};i>=0;--i) {
    //     mr[i] = max(ml[i+1] + l[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] + l[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] + l[i] + d[i],mll[i+1]);
    // };
    //
    // return 0;
    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{0}; a < n; ++a)
            {
                for (int b{a+1}; b < n; ++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]));
                    mm += d[a] + 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: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3