oj.uz

Submission #514272

# Submission time Handle Problem Language Result Execution time Memory
514272 2022-01-18T06:02:44 Z amunduzbaev Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 66132 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

long double const eps = 1e-18;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 3>> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	} sort(a.begin(), a.end());
	
	vector<pair<long double, pair<int, int>>> tt;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(a[i][0] == a[j][0]) continue;
			double slop = (a[j][1] - a[i][1]) * 1. / (a[i][0] - a[j][0]);
			tt.push_back({slop, {i, j}});
		}
	}
	
	vector<long double> b(n);
	vector<int> p(n); iota(p.begin(), p.end(), 0);
	for(int i=0;i<n;i++){
		b[i] = a[i][1] * 1. - (a[i][0] * -2e9);
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (eps < b[j] - b[i]);
	});
	
	vector<int> pos(n);
	for(int i=0;i<n;i++) pos[p[i]] = i;

	int res = 0;
	sort(tt.begin(), tt.end());
	auto check = [&](){
		int pref = 0, mn = 0;
		for(int i=0;i<n;i++){
			pref += a[p[i]][2];
			res = max(res, pref - mn);
			mn = min(mn, pref);
		}
	};
	check();
	for(int l=0;l<(int)tt.size();){
		int k = l;
		while(k < (int)tt.size() && tt[k].first == tt[l].first){
			auto [i, j] = tt[k].second;
			swap(p[pos[i]], p[pos[j]]);
			swap(pos[i], pos[j]); k++;
		} l = k;
		
		check();
	}
	
	cout<<res<<"\n";
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:54:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |    auto [i, j] = tt[k].second;
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 688 KB Output is correct
11 Correct 0 ms 312 KB Output is correct
12 Correct 0 ms 296 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 716 KB Output is correct
25 Correct 2 ms 716 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 2 ms 716 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 3 ms 588 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 716 KB Output is correct
25 Correct 2 ms 716 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 2 ms 716 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 3 ms 588 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Execution timed out 2077 ms 66132 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 716 KB Output is correct
25 Correct 2 ms 716 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 2 ms 716 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 3 ms 588 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Execution timed out 2077 ms 66132 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 688 KB Output is correct
11 Correct 0 ms 312 KB Output is correct
12 Correct 0 ms 296 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 716 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 0 ms 204 KB Output is correct
28 Correct 0 ms 204 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 2 ms 716 KB Output is correct
37 Correct 2 ms 588 KB Output is correct
38 Correct 2 ms 588 KB Output is correct
39 Correct 2 ms 716 KB Output is correct
40 Correct 2 ms 716 KB Output is correct
41 Correct 2 ms 716 KB Output is correct
42 Correct 2 ms 716 KB Output is correct
43 Correct 2 ms 588 KB Output is correct
44 Correct 2 ms 716 KB Output is correct
45 Correct 3 ms 588 KB Output is correct
46 Correct 2 ms 588 KB Output is correct
47 Correct 2 ms 588 KB Output is correct
48 Execution timed out 2077 ms 66132 KB Time limit exceeded
49 Halted 0 ms 0 KB -