Submission #42708

#	Time	Username	Problem	Language	Result	Execution time	Memory
42708		funcsr	Shortcut (IOI16_shortcut)	C++14	23 / 100	2033 ms	1116 KiB

shortcut

#include "shortcut.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)

int N;
long long B[1000000], D[1000000];
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int C) {
  N = n;
  B[0] = 0;
  rep(i, N-1) B[i+1] = B[i]+l[i];
  rep(i, N) D[i] = d[i];
  long long m = 1LL<<60;
  rep(x, N) for (int y=x+1; y<N; y++) {
    long long s = 0;
    rep(i, N) for (int j=i+1; j<N; j++) {
      s = max(s, min(B[j]-B[i], abs(B[i]-B[x])+abs(B[j]-B[y])+C)+D[i]+D[j]);
    }
    m = min(m, s);
  }
  return m;
}

• 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