Submission #955817

#	Time	Username	Problem	Language	Result	Execution time	Memory
955817		vjudge1	Pinball (JOI14_pinball)	C++17	0 / 100	0 ms	348 KiB

pinball

#include <bits/stdc++.h>

using namespace std;
typedef long long ull;

struct ured{
    int a,b,c;
    ull d;
};
int m,n;

map<pair<int,pair<int,int> >,ull> dp;
ull prosto(int L,int R,ull D,int i,ured arr[]){
    auto it=dp.find({i,{L,R}});
    if(it!=dp.end()){
        ull h= it->second;
        if(h<=-1)return -1;
        else return h+D;
    }
    if(i==-1){
        if(L!=1||R!=n)return -1;
        else return D;
    }
    if(arr[i].c>=L&&arr[i].c<=R){
        int h=prosto(L,R,D,i-1,arr);
        if(arr[i].a<L||arr[i].b>R){
            int k=prosto(min(arr[i].a,L),max(arr[i].b,R),D+arr[i].d,i-1,arr);
            if(k!=-1&&h!=-1)h=min(h,k);
            else h=max(h,k);
        }
        dp[{i,{L,R}}]=h-D;
        return h;
    }else{
        return prosto(L,R,D,i-1,arr);
    }
}




int main()
{
    cin>>m>>n;
    ured arr[m];

    for(int i=0;i<m;i++){
        cin>>arr[i].a>>arr[i].b>>arr[i].c>>arr[i].d;
    }
    ull rez=LLONG_MAX;
    for(int i=m-1;i>=0;i--){
        ull k=min(rez,prosto(arr[i].a,arr[i].b,arr[i].d,i-1,arr));
        if(k!=-1)rez=min(rez,k);
       // cout<<k<<endl;
    }
    if(rez==LLONG_MAX)cout<<-1;
    else cout<<rez;

    return 0;
}

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