Submission #500880

#	Time	Username	Problem	Language	Result	Execution time	Memory
500880		n00bie_1004	Pinball (JOI14_pinball)	C++17	51 / 100	1027 ms	1244 KiB

pinball

#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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49