oj.uz

Submission #302316

# Submission time Handle Problem Language Result Execution time Memory
302316 2020-09-18T15:34:08 Z limabeans Pinball (JOI14_pinball) C++17
11 / 100
 1000 ms 512 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 416 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 8 ms 416 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 416 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 8 ms 416 KB Output is correct
9 Execution timed out 1045 ms 384 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 416 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 8 ms 416 KB Output is correct
9 Execution timed out 1045 ms 384 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 416 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 8 ms 416 KB Output is correct
9 Execution timed out 1045 ms 384 KB Time limit exceeded
10 Halted 0 ms 0 KB -