oj.uz

Submission #955725

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

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=1; i<=n+1; i++)
        for(int j=0; j<comp.size(); j++)
            for(int k=j; k<comp.size(); k++) dp[i][j][k] = 1e14;

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

    for(int i=n+1; i>=2; i--) {
        for(int j=0; j<comp.size(); j++) {
            for(int k=j; k<comp.size(); k++) {
                if(dp[i][j][k] >= 1e14) continue;
                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] >= 1e14) 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:34:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j=0; j<comp.size(); j++)
      |                      ~^~~~~~~~~~~~
pinball.cpp:35:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int k=j; k<comp.size(); k++) dp[i][j][k] = 1e14;
      |                          ~^~~~~~~~~~~~
pinball.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0; i<comp.size(); i++) dp[n+1][i][i] = 0;
      |                  ~^~~~~~~~~~~~
pinball.cpp:40:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j=0; j<comp.size(); j++) {
      |                      ~^~~~~~~~~~~~
pinball.cpp:41:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int k=j; k<comp.size(); k++) {
      |                          ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 5 ms 23008 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 5 ms 23008 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct
9 Correct 84 ms 186684 KB Output is correct
10 Correct 72 ms 247892 KB Output is correct
11 Correct 91 ms 282172 KB Output is correct
12 Incorrect 220 ms 403940 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 12632 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 5 ms 23008 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct
9 Correct 84 ms 186684 KB Output is correct
10 Correct 72 ms 247892 KB Output is correct
11 Correct 91 ms 282172 KB Output is correct
12 Incorrect 220 ms 403940 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 12632 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 5 ms 23008 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Correct 3 ms 22876 KB Output is correct
8 Correct 3 ms 22876 KB Output is correct
9 Correct 84 ms 186684 KB Output is correct
10 Correct 72 ms 247892 KB Output is correct
11 Correct 91 ms 282172 KB Output is correct
12 Incorrect 220 ms 403940 KB Output isn't correct
13 Halted 0 ms 0 KB -