oj.uz

Submission #295287

# Submission time Handle Problem Language Result Execution time Memory
295287 2020-09-09T15:05:04 Z 임성재(#5809) Treatment Project (JOI20_treatment) C++17
5 / 100
 161 ms 3192 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;


int n, m;
int t[100010];
int l[100010];
int r[100010];
int c[100010];

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<m; i++) {
		cin >> t[i] >> l[i] >> r[i] >> c[i];
	}

	ll ans = INF;

	for(int i=0; i<(1<<m); i++) {
		vector<int> v;
		vector<pii> I;
		ll cost = 0;
		for(int j=0; j<m; j++) {
			if(i & (1<<j)) {
				cost += c[j];
				v.eb(j);
			}
		}

		sort(all(v), [&] (int i, int j) {
			return t[i] < t[j];
		});

		int T = 0;
		for(auto j : v) {
			vector<pii> J;
			for(auto k : I) {
				if(k.fi > 1) k.fi += t[j] - T;
				if(k.se < n) k.se -= t[j] - T;
				if(k.fi <= k.se) J.eb(k);
			}
			J.eb(l[j], r[j]);
			sort(all(J));

			I.clear();
			for(auto k : J) {
				if(I.size() && k.fi <= I.back().se + 1) I.back().se = max(I.back().se, k.se);
				else I.eb(k);
			}


			T = t[j];
		}

		if(I == vector<pii> {mp(1, n)}) ans = min(ans, cost);
	}

	if(ans == INF) cout << -1;
	else cout << ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 105 ms 396 KB Output is correct
3 Correct 99 ms 384 KB Output is correct
4 Correct 79 ms 400 KB Output is correct
5 Correct 91 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 105 ms 400 KB Output is correct
8 Correct 125 ms 384 KB Output is correct
9 Correct 113 ms 384 KB Output is correct
10 Correct 113 ms 384 KB Output is correct
11 Correct 161 ms 384 KB Output is correct
12 Correct 93 ms 384 KB Output is correct
13 Correct 100 ms 384 KB Output is correct
14 Correct 92 ms 384 KB Output is correct
15 Correct 97 ms 396 KB Output is correct
16 Correct 121 ms 384 KB Output is correct
17 Correct 133 ms 384 KB Output is correct
18 Correct 104 ms 384 KB Output is correct
19 Correct 129 ms 384 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 105 ms 396 KB Output is correct
3 Correct 99 ms 384 KB Output is correct
4 Correct 79 ms 400 KB Output is correct
5 Correct 91 ms 384 KB Output is correct
6 Correct 100 ms 384 KB Output is correct
7 Correct 105 ms 400 KB Output is correct
8 Correct 125 ms 384 KB Output is correct
9 Correct 113 ms 384 KB Output is correct
10 Correct 113 ms 384 KB Output is correct
11 Correct 161 ms 384 KB Output is correct
12 Correct 93 ms 384 KB Output is correct
13 Correct 100 ms 384 KB Output is correct
14 Correct 92 ms 384 KB Output is correct
15 Correct 97 ms 396 KB Output is correct
16 Correct 121 ms 384 KB Output is correct
17 Correct 133 ms 384 KB Output is correct
18 Correct 104 ms 384 KB Output is correct
19 Correct 129 ms 384 KB Output is correct
20 Incorrect 58 ms 512 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -