oj.uz

답안 #500880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500880 2022-01-01T14:33:22 Z n00bie_1004 Pinball (JOI14_pinball) C++17
51 / 100
 1000 ms 1244 KB 
#include <bits/stdc++.h>
typedef long long int ll; 

using namespace std;

struct pr {
    ll l, r, mid, cost; 
}; 

int main(){ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); 
    ll m, n;
    cin >> m >> n;
    vector<pr> v(m); 
    for(ll i=0;i<m;i++){
        cin >> v[i].l >> v[i].r >> v[i].mid >> v[i].cost; 
        --v[i].l; --v[i].r; --v[i].mid; 
    }
    vector<ll> dpL(m, 1e18); 
    for(ll i=0;i<m;i++){
        if(v[i].l == 0){
            dpL[i] = v[i].cost;
            continue; 
        }
        for(ll j=0;j<i;j++){
            if(v[j].mid >= v[i].l && v[j].mid <= v[i].r){
                dpL[i] = min(dpL[i], dpL[j] + v[i].cost); 
            }
        }
    }
    // for(ll i=0;i<m;i++)
    //     cout << dpL[i] << " "; 
    // cout << "\n"; 
    vector<ll> dpR(m, 1e18); 
    for(ll i=0;i<m;i++){
        if(v[i].r == n - 1){
            dpR[i] = v[i].cost; 
            continue; 
        }
        for(ll j=0;j<i;j++){
            if(v[j].mid >= v[i].l && v[j].mid <= v[i].r){
                dpR[i] = min(dpR[i], dpR[j] + v[i].cost); 
            }
        }
    }
    // for(ll i=0;i<m;i++)
    //     cout << dpR[i] << " ";  
    // cout << "\n"; 
    ll ans = 1e18; 
    for(ll i=0;i<m;i++)
        ans = min(ans, dpL[i] + dpR[i] - v[i].cost);
    if(ans >= 1e18)
        ans = -1;
    cout << ans << "\n"; 
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; 
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 5 ms 332 KB Output is correct
18 Correct 4 ms 332 KB Output is correct
19 Correct 6 ms 356 KB Output is correct
20 Correct 5 ms 360 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 4 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 5 ms 332 KB Output is correct
18 Correct 4 ms 332 KB Output is correct
19 Correct 6 ms 356 KB Output is correct
20 Correct 5 ms 360 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 4 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 423 ms 736 KB Output is correct
26 Execution timed out 1027 ms 1244 KB Time limit exceeded
27 Halted 0 ms 0 KB -