oj.uz

Submission #908707

# Submission time Handle Problem Language Result Execution time Memory
908707 2024-01-16T17:22:12 Z vjudge1 Pinball (JOI14_pinball) C++17
11 / 100
 300 ms 524288 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby

typedef long long ll;

struct Device {
  int a, b, c, d;
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m;
  std::cin >> n >> m;

  Device a[n + 1];
  std::vector<int> norm;
  norm.push_back(1);
  norm.push_back(m);

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
    norm.push_back(a[i].a);
    norm.push_back(a[i].b);
    norm.push_back(a[i].c);
  }

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());

  for (int i = 1; i <= n; i++) {
    a[i].a = std::lower_bound(norm.begin(), norm.end(), a[i].a) - norm.begin() + 1;
    a[i].b = std::lower_bound(norm.begin(), norm.end(), a[i].b) - norm.begin() + 1;
    a[i].c = std::lower_bound(norm.begin(), norm.end(), a[i].c) - norm.begin() + 1;
  }

  int sz = (int) norm.size();

  ll dp[n + 5][sz + 1][sz + 1];
  for (int i = 0; i <= n; i++) {
    for (int l = 1; l <= sz; l++) {
      for (int r = l; r <= sz; r++) {
        dp[i][l][r] = 1e18;
      }
    }
  }

  dp[0][1][sz] = 0;

  for (int i = 1; i <= n; i++) {
    for (int l = 1; l <= sz; l++) {
      for (int r = l; r <= sz; r++) {
        dp[i][l][r] = std::min(dp[i][l][r], dp[i - 1][l][r]);
        int newL = l, newR = r;
        if (a[i].a <= l && l <= a[i].b) {
          newL = a[i].c;
        }
        if (a[i].a <= r && r <= a[i].b) {
          newR = a[i].c;
        }
        dp[i][newL][newR] = std::min(dp[i][newL][newR], dp[i][l][r] + a[i].d);
      }
    }
  }

  ll answer = 1e18;

  for (int i = 1; i <= sz; i++) {
    answer = std::min(answer, dp[n][i][i]);
  }

  if (answer == 1e18) {
    answer = -1;
  }
  std::cout << answer;

  return 0;
}

Compilation message

pinball.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 8 ms 10584 KB Output is correct
10 Correct 70 ms 64628 KB Output is correct
11 Correct 118 ms 114772 KB Output is correct
12 Runtime error 300 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 8 ms 10584 KB Output is correct
10 Correct 70 ms 64628 KB Output is correct
11 Correct 118 ms 114772 KB Output is correct
12 Runtime error 300 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 424 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 8 ms 10584 KB Output is correct
10 Correct 70 ms 64628 KB Output is correct
11 Correct 118 ms 114772 KB Output is correct
12 Runtime error 300 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -