oj.uz

Submission #136166

# Submission time Handle Problem Language Result Execution time Memory
136166 2019-07-24T21:02:01 Z MetB Bulldozer (JOI17_bulldozer) C++14
0 / 100
 4 ms 760 KB 
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <bitset>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
typedef long long ll;
typedef long double ld;
 
const ll MOD = 1e9 + 7, INF = 1e18 + 1;
 
using namespace std;

ll p[1000000], to[10000], n;

struct SegTree
{
	ll t[80000][4], start;
 
	ll operator[] (const int& i)
	{
		return t[i][0];
	}
 
	void build (ll n)
	{
		start = 1;
 
		while (start < n) start <<= 1;
 
		for (ll i = 2 * start - 1; i; i--)
			merge (i);
	}
 
	void merge (ll node)
	{
		if (node >= start) 
		{
			t[node][3] = p[node - start];
			t[node][2] = max (0LL, p[node - start]);
			t[node][1] = max (0LL, p[node - start]);
			t[node][0] = max (0LL, p[node - start]);
		}
		else
		{
			t[node][3] = t[2 * node][3] + t[2 * node + 1][3];
			t[node][2] = max (t[2 * node][3] + t[2 * node + 1][2], t[2 * node][2]);
			t[node][1] = max (t[2 * node][1] + t[2 * node + 1][3], t[2 * node + 1][1]);
			t[node][0] = max (max (t[2 * node][0], t[2 * node + 1][0]), t[2 * node][1] + t[2 * node + 1][2]);
		}
	}
 
	void update (ll x, ll d)
	{
		p[x] = d;
		x += start;
 
		while (x)
		{
			merge (x);
			x /= 2;
		}
	}
} t;

struct point
{
	ll x, y, c;

	bool operator < (const point& b) const
	{
		return (y == b.y ? x < b.x : y > b.y);
	}

} a[2000];

struct fraction
{
	ll a, b;

	ll p1, p2;

	bool operator < (const fraction& d) const
	{
		if (!d.b && !b) return a < d.a;
		if (!d.b) return true;
		if (!b) return false;
		return (a * d.b) < (b * d.a);
	}

	bool operator == (const fraction& d) const
	{
		if (!b && !d.b) return true;
		if (!b || !d.b) return false;
		return (a * d.b) == (b * d.a);
	}
};

vector <fraction> d;

int main ()
{
	cin >> n;

	for (ll i = 0; i < n; i++)
		scanf ("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].c);

	sort (a, a + n);

	for (ll i = 0; i < n; i++)
		for (ll j = i + 1; j < n; j++)
		{
			ll A = a[i].y - a[j].y;
			ll B = a[i].x - a[j].x;

			d.push_back ({-B, A, i, j});

			to[i] = i;
			to[j] = j;

			p[i] = a[i].c;
			p[j] = a[j].c;
		}

	sort (d.begin(), d.end());

	t.build (n);

	ll ans = t[1];

	
	for (ll i = 0; i < d.size ();)
	{
		int k = 0;
		while (i + k < d.size () && d[i + k] == d[i])
		{
			ll l = d[i + k].p1, r = d[i + k].p2, p_l = p[to[l]], p_r = p[to[r]];
	 
			t.update (to[r], p_l);
			t.update (to[l], p_r);
		 
			swap (to[l], to[r]);

			/*for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if (to[i] == j)
						cout << "(" << a[j].x << ", " << a[j].y << ") ";
			cout << endl;*/

			k++;
		}

		i += k;

		ans = max (ans, t[1]);
	}

	cout << ans;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:139:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (ll i = 0; i < d.size ();)
                 ~~^~~~~~~~~~~
bulldozer.cpp:142:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (i + k < d.size () && d[i + k] == d[i])
          ~~~~~~^~~~~~~~~~~
bulldozer.cpp:113:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Incorrect 2 ms 256 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Incorrect 2 ms 256 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 4 ms 760 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Incorrect 2 ms 256 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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