제출 #302316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302316		limabeans	Pinball (JOI14_pinball)	C++17	11 / 100	1045 ms	512 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


struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};


using ll = long long;

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


int m, n;
int l[maxn], r[maxn], x[maxn], c[maxn];


ll test(int mask) {
    vector<int> v;
    ll cost = 0;
    for (int i=0; i<m; i++) {
	if (mask>>i&1) {
	    v.push_back(i);
	    cost += c[i];
	}
    }
    int land = -1;
    for (int j=0; j<n; j++) {
	int at=j;
	for (int i: v) {
	    if (l[i]<=at && at<=r[i]) {
		at=x[i];
	    }
	}
	if (land==-1 || land==at) {
	    land=at;
	} else {
	    return inf;
	}
    }

    return cost;
}

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];
	l[i]--;
	r[i]--;
	x[i]--;
    }

    ll res = inf;

    for (int mask=0; mask<1<<m; mask++) {
	res = min(res, test(mask));
    }


    res = (res==inf ? -1: res);
    out(res);    
    return 0;
}

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