Submission #915214

#	Time	Username	Problem	Language	Result	Execution time	Memory
915214		vjudge1	Shortcut (IOI16_shortcut)	C++17	23 / 100	2065 ms	688 KiB

shortcut

#include "shortcut.h"

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

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
        vector<int64_t> a(n), b(n);  // a = x + d, b = x - d
        vector<int64_t> x(n);
        for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
        for (int i = 0; i < n; i++) a[i] = x[i] + d[i], b[i] = x[i] - d[i];

        auto check = [&](int64_t target) {
                for (int p = 0; p < n; p++) {
                        for (int q = p + 1; q < n; q++) {
                                bool ok = 1;
                                for (int i = 0; i < n; i++) {
                                        for (int j = i + 1; j < n; j++) {
                                                if (x[j] - x[i] + d[i] + d[j] > target) {
                                                        if (abs(x[i] - x[p]) + abs(x[j] - x[q]) + d[i] + d[j] + c > target) ok = 0;
                                                }
                                        }
                                }
                                if (ok == 1) return 1;
                        }
                }
                return 0;
        };

        int64_t low = 0, high = 1ll << 60;
        while (low < high) {
                int64_t mid = low + high >> 1;
                if (check(mid)) {
                        high = mid;
                } else {
                        low = mid + 1;
                }
        }
        return high;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:31:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |                 int64_t mid = low + high >> 1;
      |                               ~~~~^~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 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