oj.uz

답안 #908707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -