Submission #1304860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304860		icaijy	Pinball (JOI14_pinball)	C++20	29 / 100	1095 ms	976 KiB

pinball

#include <bits/stdc++.h>
#define int long long
using namespace std;

map<int,int> dpr; // r at
map<int,int> dpc; // c at
// increase(strict)
void insertr(int r,int cost){
    if (dpr.lower_bound(r)!=dpr.end()&&dpr.lower_bound(r)->second<=cost) return;
    dpr[r]=cost;
    auto it=dpr.find(r);
    while (it!=dpr.begin()){
        if (prev(it)->second>=cost) dpr.erase(prev(it));
        else break;
    }
}

void insertc(int c,int cost){
    if (dpc.lower_bound(c)!=dpc.end()&&dpc.lower_bound(c)->second<=cost) return;
    dpc[c]=cost;
    auto it=dpc.find(c);
    while (it!=dpc.begin()){
        if (prev(it)->second>=cost) dpc.erase(prev(it));
        else break;
    }
}

struct device{
    int l,r,c,d;
    bool operator<(const device &o)const{return l<o.l;}
};
signed main(){
    int n,m;
    cin>>n>>m;
    vector<device> v(n);
    for (auto &[l,r,c,d]:v) cin>>l>>r>>c>>d;
    int i=0,ans=1e18;
    for (int i=0;i<n;i++){
        map<pair<int,int>,int> dp; // l,r,cost
        dp[{v[i].l,v[i].r}]=v[i].d;
        for (int j=i-1;j>=0;j--){
            vector<array<int,3>> ok; 
            for (auto k:dp){
                if (v[j].c>k.first.second||v[j].c<k.first.first) continue;
                ok.push_back({k.first.first,k.first.second,k.second});
            }
            for (auto [l,r,cost]:ok){
                dp.insert({{min(v[j].l,l),max(v[j].r,r)},v[j].d+cost});
                dp[{min(v[j].l,l),max(v[j].r,r)}]=min(dp[{min(v[j].l,l),max(v[j].r,r)}],v[j].d+cost);
            }
        }
        if (dp.count({1,m})) ans=min(ans,dp[{1,m}]);
        // cerr<<ans<<endl;
    }
    if (ans!=1e18) cout<<ans;
    else cout<<-1;
}

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