답안 #46843 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46843	2018-04-23T19:06:15 Z	qoo2p5	Bulldozer (JOI17_bulldozer)	C++17	5 / 100	6 ms	896 KB

bulldozer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6;
const ll LINF = (ll) 1e18 + 1e9;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; ++(i))
#define per(i, f, t) for (auto i = (f); i >= (t); --(i))

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

#define double long double

const int N = 1 << 11;
const double EPS = 1e-10;

struct P {
	ll x, y, c;
};

int n;
P p[N];

struct Ev {
	int a, b;
	double ang;
	
	Ev(int a, int b) : a(a), b(b) {
		if (p[a].x == p[b].x) {
			ang = 1e10;
		} else {
			ang = (double) (p[a].y - p[b].y) / (p[a].x - p[b].x);
		}
	}
};

bool operator<(const Ev &u, const Ev &v) {
	if (u.ang + EPS < v.ang) {
		return 1;
	}
	if (u.ang - EPS > v.ang) {
		return 0;
	}
	
	return mp(u.a, u.b) < mp(v.a, v.b);
}

struct Node {
	ll sum, res, left, right;
};

Node tree[2 * N + 13];

void upd(int i, ll val) {
	i += N;
	tree[i] = {val, max(0LL, val), max(0LL, val), max(0LL, val)};
	i /= 2;
	while (i > 0) {
		tree[i].sum = tree[2 * i].sum + tree[2 * i + 1].sum;
		tree[i].left = max(tree[2 * i].left, tree[2 * i].sum + tree[2 * i + 1].left);
		tree[i].right = max(tree[2 * i + 1].right, tree[2 * i + 1].sum + tree[2 * i].right);
		tree[i].res = max(tree[2 * i].right + tree[2 * i + 1].left, max(tree[2 * i].res, tree[2 * i + 1].res));
		i /= 2;
	}
}

ll get() {
	return tree[1].res;
}

int pos[N];

void make(const Ev &ev) {
	int a = pos[ev.a];
	int b = pos[ev.b];
	assert(a + 1 == b);
	swap(pos[ev.a], pos[ev.b]);
	ll va = tree[N + a].sum;
	ll vb = tree[N + b].sum;
	upd(a, vb);
	upd(b, va);
}

void run() {
	cin >> n;
	rep(i, 0, n) {
		cin >> p[i].x >> p[i].y >> p[i].c;
	}
	sort(p, p + n, [] (const auto &a, const auto &b) {
		return mp(a.x, a.y) < mp(b.x, b.y);
	});
	vector<Ev> events;
	events.reserve(n * (n - 1) / 2);
	rep(i, 0, n) {
		rep(j, i + 1, n) {
			events.pb(Ev(i, j));
		}
	}
	sort(all(events));
	
	ll ans = 0;
	rep(i, 0, n) {
		upd(i, p[i].c);
		pos[i] = i;
	}
	
	maxi(ans, get());
	
	rep(i, 0, sz(events)) {
		make(events[i]);
		int j = i;
		while (j + 1 < sz(events) && abs(events[j].ang - events[j + 1].ang) < EPS) {
			j++;
			make(events[j]);
		}
		
		maxi(ans, get());
		i = j;
	}
	
	cout << ans << "\n";
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	3 ms	560 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	4 ms	512 KB	Output is correct
8	Correct	4 ms	512 KB	Output is correct
9	Correct	4 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	512 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	4 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	4 ms	512 KB	Output is correct
22	Correct	4 ms	512 KB	Output is correct
23	Correct	3 ms	512 KB	Output is correct
24	Correct	4 ms	512 KB	Output is correct
25	Correct	4 ms	512 KB	Output is correct
26	Correct	4 ms	512 KB	Output is correct
27	Runtime error	4 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #3
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	512 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	4 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	4 ms	512 KB	Output is correct
22	Correct	4 ms	512 KB	Output is correct
23	Correct	3 ms	512 KB	Output is correct
24	Correct	4 ms	512 KB	Output is correct
25	Correct	4 ms	512 KB	Output is correct
26	Correct	4 ms	512 KB	Output is correct
27	Runtime error	4 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	512 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	4 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	4 ms	512 KB	Output is correct
22	Correct	4 ms	512 KB	Output is correct
23	Correct	3 ms	512 KB	Output is correct
24	Correct	4 ms	512 KB	Output is correct
25	Correct	4 ms	512 KB	Output is correct
26	Correct	4 ms	512 KB	Output is correct
27	Runtime error	4 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	3 ms	560 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	4 ms	512 KB	Output is correct
8	Correct	4 ms	512 KB	Output is correct
9	Correct	4 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	512 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	3 ms	640 KB	Output is correct
19	Correct	3 ms	512 KB	Output is correct
20	Correct	4 ms	512 KB	Output is correct
21	Correct	3 ms	512 KB	Output is correct
22	Correct	6 ms	512 KB	Output is correct
23	Correct	4 ms	512 KB	Output is correct
24	Correct	3 ms	512 KB	Output is correct
25	Correct	4 ms	512 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	2 ms	384 KB	Output is correct
28	Correct	3 ms	384 KB	Output is correct
29	Correct	2 ms	384 KB	Output is correct
30	Correct	2 ms	384 KB	Output is correct
31	Correct	2 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct
33	Correct	2 ms	384 KB	Output is correct
34	Correct	2 ms	384 KB	Output is correct
35	Correct	2 ms	384 KB	Output is correct
36	Correct	4 ms	512 KB	Output is correct
37	Correct	4 ms	512 KB	Output is correct
38	Correct	3 ms	512 KB	Output is correct
39	Correct	4 ms	512 KB	Output is correct
40	Correct	4 ms	512 KB	Output is correct
41	Correct	4 ms	512 KB	Output is correct
42	Runtime error	4 ms	896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Halted	0 ms	0 KB	-

답안 #46843

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 20.0

Subtask #3 0 / 35.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 20.0

Subtask #3
0 / 35.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0