Submission #131740

#	Time	Username	Problem	Language	Result	Execution time	Memory
131740		Just_Solve_The_Problem	Pinball (JOI14_pinball)	C++11	51 / 100	1056 ms	524288 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = (int)1e5 + 7;
const int smalln = (int)5e3 + 7;

int n, m;
int a[maxn], b[maxn], c[maxn], d[maxn];
int used[maxn];
ll dp[2][smalln][smalln];
ll ans;
vector <int> vec;

int getx(int x) {
  return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

main() {
  scanf("%d %d", &m, &n);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
    vec.push_back(a[i]);
    vec.push_back(b[i]);
    vec.push_back(c[i]);
  }
  if (n == 1) {
    puts("0");
    return 0;
  }
  ans = 1e18;
  vec.push_back(1);
  vec.push_back(n);
  sort(vec.begin(), vec.end());
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  for (int i = 0; i <= m; i++) {
    for (int j = 0; j < vec.size(); j++) {
      dp[0][i][j] = dp[1][i][j] = 1e18;
    }
  }
  dp[0][0][0] = 0;
  for (int i = 0; i < m; i++) {
    a[i] = getx(a[i]);
    b[i] = getx(b[i]);
    c[i] = getx(c[i]);
    for (int j = 0; j < vec.size(); j++) {
      dp[0][i + 1][j] = dp[0][i][j];
    }
    for (int j = a[i]; j <= b[i]; j++) {
      dp[0][i + 1][c[i]] = min(dp[0][i + 1][c[i]], dp[0][i][j] + d[i]);
    }
  }
  dp[1][0][vec.size() - 1] = 0;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < vec.size(); j++) {
      dp[1][i + 1][j] = dp[1][i][j];
    }
    for (int j = a[i]; j <= b[i]; j++) {
      dp[1][i + 1][c[i]] = min(dp[1][i + 1][c[i]], dp[1][i][j] + d[i]);
    }
  }
  ans = 1e18;
  for (int i = 0; i < m; i++) {
    for (int j = 1; j < vec.size(); j++) {
      dp[1][i][j] = min(dp[1][i][j], dp[1][i][j - 1]);
    }
    for (int j = vec.size() - 2; j >= 0; j--) {
      dp[0][i][j] = min(dp[0][i][j], dp[0][i][j + 1]);
    }
    ans = min(ans, d[i] + dp[0][i][a[i]] + dp[1][i][b[i]]);
  }
  if (ans == (ll)1e18) ans = -1;
  printf("%lld\n", ans);
}

Compilation message (stderr)

pinball.cpp:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
pinball.cpp: In function 'int main()':
pinball.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < vec.size(); j++) {
                     ~~^~~~~~~~~~~~
pinball.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < vec.size(); j++) {
                     ~~^~~~~~~~~~~~
pinball.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < vec.size(); j++) {
                     ~~^~~~~~~~~~~~
pinball.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 1; j < vec.size(); j++) {
                     ~~^~~~~~~~~~~~
pinball.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &m, &n);
   ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49