oj.uz

Submission #624372

# Submission time Handle Problem Language Result Execution time Memory
624372 2022-08-08T04:54:51 Z brucecccccc Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 300 KB 
#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
  vector<ll> prefix(n);
  for (int i = 1; i < n; i++) {
    prefix[i] = prefix[i-1] + l[i-1];
  }

  vector<vector<ll>> maxFrom(n, vector<ll>(n));
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    auto& m = maxFrom[i];
    for (int j = i+1; j < n; j++) {
      ll x = prefix[j] - prefix[i] + d[j];
      ans = max(ans, x + d[i]);
      m[j] = max(m[j-1], x);
    }
    m[i] = d[i];
    for (int j = i-1; j >= 0; j--) {
      ll x = prefix[i] - prefix[j] + d[j];
      ans = max(ans, x + d[i]);
      m[j] = max(m[j+1], x);
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (prefix[j] - prefix[i] <= c) continue;
      ll a = 0;
      int s = i;
      while (s + 1 <= j && prefix[s + 1] - prefix[i] < c + prefix[j] - prefix[s + 1]) {
        s++;
      }
      for (int b = 0; b <= i; b++) {
        a = max(a, d[b] + maxFrom[b][i]);
        a = max(a, d[b] + prefix[i] - prefix[b] + c + maxFrom[j][n-1]);
      }
      for (int b = j; b < n; b++) {
        a = max(a, d[b] + maxFrom[b][n-1]);
        a = max(a, d[b] + prefix[j] - prefix[b] + c + maxFrom[i][0]);
      }

      
      for (int b = i+1; b < j; b++) {
        s = max(s, b);

        while (s >= b && s+1 <= j && prefix[s+1] - prefix[b] < c + prefix[j] - prefix[s+1] + prefix[b] - prefix[i]) {
          s++;
          if (s == j) s = i;
        }
        while (s < b && c + prefix[j] - prefix[b] + prefix[s] - prefix[i] < prefix[b] - prefix[s]) {
          s++;
        }

        if (s > b) {
          // a = max(a, maxFrom[b][i]);
          a = max(a, d[b] + prefix[b] - prefix[i] + maxFrom[i][0]);
          a = max(a, d[b] + prefix[b] - prefix[i] + c + max(maxFrom[j][s+1], maxFrom[j][n-1]));
          a = max(a, d[b] + maxFrom[b][s]);
        } else if (s == i) {
          a = max(a, d[b] + maxFrom[b][n-1]);
          a = max(a, d[b] + maxFrom[b][0]);
        } else {
          a = max(a, d[b] + prefix[j] - prefix[b] + maxFrom[j][n-1]);
          a = max(a, d[b] + prefix[j] - prefix[b] + c + max(maxFrom[i][s], maxFrom[i][0]));
        }

        // if (i == 3 && j == 8) {
        //   if (b == 7) {
        //     cout << d[i] + maxFrom[b][0] << endl;
        //   }
        //   if (a == 90) cout << b << endl;
        // }
      }
      
      
      // cout << i << ' ' << j << endl;
      
      // cout << a << endl;
      ans = min(ans, a);
    }
  }

  return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 256 KB n = 9, 110 is a correct answer
3 Correct 1 ms 212 KB n = 4, 21 is a correct answer
4 Correct 0 ms 300 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -