Submission #908827

#	Time	Username	Problem	Language	Result	Execution time	Memory
908827		vjudge1	Pinball (JOI14_pinball)	C++17	51 / 100	1020 ms	2592 KiB

pinball

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll inf=1e18;

struct device{
    ll i, a, b, c, d;
    ll dp[2]={inf, inf};
    bool operator<(const device B)const{
        return b<B.b;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin>>n>>m;
    vector<device> devs(n);
    for(int i=0; i<n; i++){
        cin>>devs[i].a>>devs[i].b>>devs[i].c>>devs[i].d;
        devs[i].i=i;
    }
    sort(devs.begin(),devs.end());
    ll ans=inf;
    for(int i=0; i<n; i++){
        if(devs[i].a==1) devs[i].dp[0]=devs[i].dp[1]=devs[i].d;
        for(int j=0; j<n; j++){
            if(devs[i].i>devs[j].i && devs[i].a<=devs[j].c && devs[j].c<=devs[i].b){
                devs[i].dp[0]=min(devs[i].dp[0],devs[j].dp[0]+devs[i].d);
            }else if(devs[j].i>devs[i].i && devs[j].a<=devs[i].c && devs[i].c<=devs[j].b){
                devs[i].dp[1]=min(devs[i].dp[1],min(devs[j].dp[0]+devs[i].d,devs[j].dp[1]+devs[i].d));
            }
        }
        if(devs[i].b==m){
            ans=min(ans,min(devs[i].dp[0],devs[i].dp[1]));
        }
    }
    if(ans==inf) cout<<-1<<endl;
    else cout<<ans<<endl;
}

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