oj.uz

Submission #369523

# Submission time Handle Problem Language Result Execution time Memory
369523 2021-02-21T19:52:57 Z kostia244 Pinball (JOI14_pinball) C++17
29 / 100
 97 ms 6912 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 605;
int n, m;
ll can[maxn][maxn], nw[maxn][maxn];
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	const ll inf = 1ll<<56;
	vector<array<int, 4>> f(n);
	vector<int> comp {1, m};
	for(auto &[c, l, r, d] : f) cin >> l >> r >> c >> d, comp.push_back(l), comp.push_back(r), comp.push_back(c);
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for(auto &[c, l, r, d] : f) l = lower_bound(comp.begin(), comp.end(), l) - comp.begin()+1;
	for(auto &[c, l, r, d] : f) r = lower_bound(comp.begin(), comp.end(), r) - comp.begin()+1;
	for(auto &[c, l, r, d] : f) c = lower_bound(comp.begin(), comp.end(), c) - comp.begin()+1;
	m = comp.size();
	for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) can[i][j] = inf;
	for(int i = 1; i <= m; i++) can[i][i] = 0;
	reverse(f.begin(), f.end());
	for(auto [c, l, r, d] : f) {
		for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) nw[i][j] = can[i][j];
		//cout << l << " " << r << endl;
		//cout << can[c][c] << endl;
		#define minq(a, b) a = min(a, b)
		for(int x = 1; x <= c; x++)
			for(int y = c; y <= m; y++) if(can[x][y] < inf) {
				minq(nw[min(x, l)][max(y, r)], can[x][y] + d);
			}
		for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) {
			can[i][j] = nw[i][j];
		}
	}
	if(can[1][m] == inf) can[1][m] = -1;
	cout << can[1][m] << endl;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 12 ms 2284 KB Output is correct
11 Correct 20 ms 2924 KB Output is correct
12 Correct 92 ms 5996 KB Output is correct
13 Correct 95 ms 6124 KB Output is correct
14 Correct 97 ms 5996 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 12 ms 2284 KB Output is correct
11 Correct 20 ms 2924 KB Output is correct
12 Correct 92 ms 5996 KB Output is correct
13 Correct 95 ms 6124 KB Output is correct
14 Correct 97 ms 5996 KB Output is correct
15 Correct 3 ms 1132 KB Output is correct
16 Runtime error 7 ms 6912 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 12 ms 2284 KB Output is correct
11 Correct 20 ms 2924 KB Output is correct
12 Correct 92 ms 5996 KB Output is correct
13 Correct 95 ms 6124 KB Output is correct
14 Correct 97 ms 5996 KB Output is correct
15 Correct 3 ms 1132 KB Output is correct
16 Runtime error 7 ms 6912 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -