oj.uz

Submission #955817

# Submission time Handle Problem Language Result Execution time Memory
955817 2024-03-31T12:55:15 Z vjudge1 Pinball (JOI14_pinball) C++17
0 / 100
 0 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -