oj.uz

Submission #514268

# Submission time Handle Problem Language Result Execution time Memory
514268 2022-01-18T06:00:54 Z amunduzbaev Bulldozer (JOI17_bulldozer) C++14
20 / 100
 2000 ms 66144 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(auto s : tt){
		auto [i, j] = s.second;
		
		assert(abs(pos[i] - pos[j]) == 1);
		swap(p[pos[i]], p[pos[j]]);
		swap(pos[i], pos[j]);
		check();
	}
	
	cout<<res<<"\n";
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 308 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 312 KB Output is correct
18 Correct 1 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 700 KB Output is correct
22 Correct 3 ms 716 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 696 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 2 ms 588 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 716 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 308 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 312 KB Output is correct
18 Correct 1 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 700 KB Output is correct
22 Correct 3 ms 716 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 696 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 2 ms 588 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 716 KB Output is correct
33 Execution timed out 2086 ms 66144 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 308 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 312 KB Output is correct
18 Correct 1 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 700 KB Output is correct
22 Correct 3 ms 716 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 696 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 2 ms 588 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 716 KB Output is correct
33 Execution timed out 2086 ms 66144 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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