# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1244398 | SpyrosAliv | Shortcut (IOI16_shortcut) | C++20 | 0 ms | 0 KiB |
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e17;
long long find_shortcut(int n, std::vector<int> len, std::vector<int> d, int c) {
vector<ll> ps(n);
ps[0] = 0;
for (int i = 1; i < n; i++) {
ps[i] = ps[i-1] + len[i-1];
}
ll ans = INF;
int al = 0, ar = 0;
int st = 0, en = 0;
for (int l = 0; l < n; l++) {
for (int r = l+1; r < n; r++) {
ll diam = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
ll dis = d[i];
ll dis = min(ps[j] - ps[i] + d[j], abs(ps[l] - ps[i]) + c + abs(ps[r] - ps[j]) + d[j]);
}
}
ans = min(ans, diam);
}
}
return ans;
}
/*
int main() {
int n, c; cin >> n >> c;
vector<int> l(n-1), d(n);
for (int i = 0; i < n-1; i++) cin >> l[i];
for (int i = 0; i < n; i++) cin >> d[i];
cout << find_shortcut(n, l, d, c) << "\n";
}*/