Submission #302437

#	Time	Username	Problem	Language	Result	Execution time	Memory
302437		limabeans	Pinball (JOI14_pinball)	C++17	0 / 100	1 ms	384 KiB

pinball

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;
const ll inf = 1e18;

int m, n;

int l[maxn], r[maxn], x[maxn];
ll c[maxn];
int N;
vector<int> ord;


void print() {
    for (int i=0; i<m; i++) {
    	cout<<l[i]<<" "<<r[i]<<" "<<x[i]<<endl;
    }
    cout<<endl;
}


void relax(ll &x, ll y) {
    x=min(x,y);
}


// [a,b]
//   [l,r]
bool isect(int a, int b, int l, int r) {
    return max(a,l)<=min(b,r);
}

ll solve(int d) {
    vector<vector<ll>> dp(N, vector<ll>(N, inf));
    dp[d][d]=0;
    int lo = d;
    int hi = d;
    for (int i=m-1; i>=0; i--) {
	if (lo<=x[i] && x[i]<=hi) {
	    // lo....x[i]....hi
	    ll cur=dp[lo][hi];
	    int nlo=min(lo,l[i]);
	    int nhi=max(hi,r[i]);

	    //O(n^2)
	    for (int a=nlo; a<=nhi; a++) {
		for (int b=a; b<=nhi; b++) {
		    if (isect(lo,hi,nlo,nhi)) {
			relax(dp[a][b],cur+c[i]);
		    }
		}
	    }

	    lo=nlo;
	    hi=nhi;
	    //cout<<lo<<" "<<hi<<endl;
	}
    }
    return dp[0][N-1];
}


vector<int> dest;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>m>>n;
    for (int i=0; i<m; i++) {
	cin>>l[i]>>r[i]>>x[i]>>c[i];
	ord.push_back(l[i]);
	ord.push_back(r[i]);
	ord.push_back(x[i]);
    }

    ord.push_back(1);
    ord.push_back(n);

    sort(ord.begin(),ord.end());
    ord.erase(std::unique(ord.begin(),ord.end()),ord.end());
    N = ord.size();

    for (int i=0; i<m; i++) {
	l[i]=lower_bound(ord.begin(),ord.end(),l[i])-ord.begin();
	r[i]=lower_bound(ord.begin(),ord.end(),r[i])-ord.begin();
	x[i]=lower_bound(ord.begin(),ord.end(),x[i])-ord.begin();
	dest.push_back(x[i]);
    }

    
    sort(dest.begin(),dest.end());
    dest.erase(std::unique(dest.begin(),dest.end()),dest.end());



    ll res=inf;
    for (int d: dest) {
	ll cur=solve(d);
	//cout<<d<<": "<<cur<<endl;
	res=min(res,cur);
    }


    res=(res==inf?-1:res);
    cout<<res<<endl;
    
    return 0;
}

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