Submission #101137

#	Time	Username	Problem	Language	Result	Execution time	Memory
101137		jasony123123	Bulldozer (JOI17_bulldozer)	C++11	25 / 100	2049 ms	49892 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
#define mp make_pair
typedef long long ll;
typedef pair<int, int > pii;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/****************************************************************/
const int MAXN = 2000;
int N, x[2000], y[2000], w[2000], pos[2000];
int treearray[2000];

struct Seg {
	int data[2000];

	void set(int x, int val) {
		data[x] = val;
	}
	void build() {

	}
	void update(int x, int val) {
		data[x] = val;
	}
	ll query() {
		//	cout << "Query: ";
		//	FOR(i, 0, N) cout << data[i] << " ";
		ll best = 0;
		FOR(i, 0, N) FOR(j, i, N) {
			ll tmp = 0;
			FORE(x, i, j) tmp += data[x];
			maxx(best, tmp);
		}
		//	cout << ":: " << best << "\n";
		return best;
	}
} tree;

struct upd {
	ll vx, vy;
	int ia, ib;
	upd(ll _vx, ll _vy, int _a, int _b) : vx(_vx), vy(_vy), ia(_a), ib(_b) {}
};
v<upd> lines;

void perform_swap(int i, int j) {
	//	cout << "Swapping " << i << " " << j << "\n";
	swap(pos[i], pos[j]);
	tree.update(pos[i], w[i]);
	tree.update(pos[j], w[j]);
}

void setup() {
	cin >> N;
	v<int> pnts(N);
	FOR(i, 0, N) {
		cin >> x[i] >> y[i] >> w[i];
		pnts[i] = i;
	}
	sort(all(pnts), [](int &i, int &j) {
		return mp(x[i], y[i]) < mp(x[j], y[j]);
	});
	FOR(i, 0, N) {
		pos[pnts[i]] = i;
		tree.set(i, w[pnts[i]]);
	}
	tree.build();
}

int main() {
	io();
	setup();
	FOR(i, 0, N) FOR(j, 0, N) if (x[i] < x[j])
		lines.push_back(upd(x[j] - x[i], y[j] - y[i], i, j));

	sort(all(lines), [](upd &a, upd &b) {
		if (a.vy*b.vx == b.vy*a.vx)
			return mp(x[a.ia], x[a.ib]) < mp(x[b.ia], x[b.ib]);
		return a.vy*b.vx > b.vy*a.vx;
	});

	ll best = tree.query();
	for (int i = 0; i < lines.size(); ) {
		ll curx = lines[i].vx, cury = lines[i].vy;
		while (i < lines.size() && cury*lines[i].vx == curx*lines[i].vy) {
			perform_swap(lines[i].ia, lines[i].ib);
			i++;
		}
		maxx(best, tree.query());
	}
	cout << best << "\n";
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < lines.size(); ) {
                  ~~^~~~~~~~~~~~~~
bulldozer.cpp:97:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (i < lines.size() && cury*lines[i].vx == curx*lines[i].vy) {
          ~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20