oj.uz

Submission #955709

# Submission time Handle Problem Language Result Execution time Memory
955709 2024-03-31T11:00:20 Z vjudge1 Pinball (JOI14_pinball) C++17
11 / 100
 221 ms 404048 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

 ll dp[205][505][505];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<array<int, 4> > v(n+2);
    set<int> s; s.insert(1); s.insert(m);
    for(int i=1; i<=n; i++) {
            cin >> v[i][0] >> v[i][1] >> v[i][2] >> v[i][3];
            s.insert(v[i][0]);
            s.insert(v[i][1]);
            s.insert(v[i][2]);
    }

    vector<int> comp(s.begin(), s.end());
    for(int i=1; i<=n; i++) {
        v[i][0] = lower_bound(comp.begin(), comp.end(), v[i][0]) - comp.begin();
        v[i][1] = lower_bound(comp.begin(), comp.end(), v[i][1]) - comp.begin();
        v[i][2] = lower_bound(comp.begin(), comp.end(), v[i][2]) - comp.begin();
    }

    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=comp.size(); j++)
            for(int k=0; k<=comp.size(); k++) dp[i][j][k] = 1e18;

    for(int i=0; i<=comp.size(); i++) dp[n+1][i][i] = 0;

    for(int i=n+1; i>=1; i--) {
        for(int j=0; j<comp.size(); j++) {
            for(int k=j; k<comp.size(); k++) {
                dp[i-1][j][k] = min(dp[i-1][j][k], dp[i][j][k]);
                if(j <= v[i-1][2] && v[i-1][2] <= k) dp[i-1][min(j, v[i-1][0])][max(k, v[i-1][1])] = min(dp[i-1][min(j, v[i-1][0])][max(k, v[i-1][1])], dp[i][j][k] + v[i-1][3]);
            }
        }
    }

    if(dp[1][0][comp.size()-1] == 1e18) cout << -1 << '\n';
    else cout << dp[1][0][comp.size()-1] << '\n';
    return 0;
}

Compilation message

pinball.cpp: In function 'int32_t main()':
pinball.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int j=0; j<=comp.size(); j++)
      |                      ~^~~~~~~~~~~~~
pinball.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             for(int k=0; k<=comp.size(); k++) dp[i][j][k] = 1e18;
      |                          ~^~~~~~~~~~~~~
pinball.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0; i<=comp.size(); i++) dp[n+1][i][i] = 0;
      |                  ~^~~~~~~~~~~~~
pinball.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j=0; j<comp.size(); j++) {
      |                      ~^~~~~~~~~~~~
pinball.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(int k=j; k<comp.size(); k++) {
      |                          ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 3 ms 22876 KB Output is correct
4 Correct 4 ms 23128 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 23080 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 3 ms 22876 KB Output is correct
4 Correct 4 ms 23128 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 23080 KB Output is correct
9 Correct 65 ms 166736 KB Output is correct
10 Correct 69 ms 223568 KB Output is correct
11 Correct 95 ms 263180 KB Output is correct
12 Incorrect 221 ms 404048 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 3 ms 22876 KB Output is correct
4 Correct 4 ms 23128 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 23080 KB Output is correct
9 Correct 65 ms 166736 KB Output is correct
10 Correct 69 ms 223568 KB Output is correct
11 Correct 95 ms 263180 KB Output is correct
12 Incorrect 221 ms 404048 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 3 ms 22876 KB Output is correct
4 Correct 4 ms 23128 KB Output is correct
5 Correct 3 ms 23132 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 23080 KB Output is correct
9 Correct 65 ms 166736 KB Output is correct
10 Correct 69 ms 223568 KB Output is correct
11 Correct 95 ms 263180 KB Output is correct
12 Incorrect 221 ms 404048 KB Output isn't correct
13 Halted 0 ms 0 KB -