oj.uz

Submission #412326

# Submission time Handle Problem Language Result Execution time Memory
412326 2021-05-26T17:20:52 Z model_code Road Closures (APIO21_roads) C++17
7 / 100
 73 ms 10560 KB 
#include "roads.h"

#include <vector>
#include <numeric>
#include <cstring>
using namespace std;

const long long LINF = 4557430888798830399LL;
vector <long long> arr;
int n;
long long memo[100005][2];
long long dp(int pos, bool take) {
  if (pos == n - 1) return 0;
  long long &ret = memo[pos][take];
  if (~ret) return ret;
  ret = dp(pos + 1, 0) + (long long) arr[pos];
  if (!take) ret = min(ret, dp(pos + 1, 1));
  return ret;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
    std::vector<int> V,
    std::vector<int> W) {
  n = N;
  memset(memo, -1, sizeof(memo));
  vector <long long> ans(N, 0);
  for (auto i : W) ans[0] += i, arr.push_back(i);
  ans[1] = dp(0, 0);
  return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Incorrect 2 ms 1996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 45 ms 9088 KB Output is correct
3 Correct 48 ms 9948 KB Output is correct
4 Correct 73 ms 10536 KB Output is correct
5 Correct 52 ms 10560 KB Output is correct
6 Correct 3 ms 1996 KB Output is correct
7 Correct 3 ms 1996 KB Output is correct
8 Correct 2 ms 1968 KB Output is correct
9 Correct 2 ms 1740 KB Output is correct
10 Correct 2 ms 1868 KB Output is correct
11 Correct 2 ms 1740 KB Output is correct
12 Correct 29 ms 7016 KB Output is correct
13 Correct 50 ms 10544 KB Output is correct
14 Correct 1 ms 1740 KB Output is correct
15 Correct 40 ms 9640 KB Output is correct
16 Correct 48 ms 10544 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1740 KB Output is correct
2 Incorrect 1 ms 1740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1740 KB Output is correct
2 Incorrect 1 ms 1740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 10256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 10256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Incorrect 2 ms 1996 KB Output isn't correct
3 Halted 0 ms 0 KB -