Submission #294217

#	Time	Username	Problem	Language	Result	Execution time	Memory
294217		patrikpavic2	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1915 ms	48104 KiB

bulldozer

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef pair < int, int > pt;
typedef long long ll;

const int N = 2e3 + 50;
const int M = N * N / 2LL;
const int OFF = (1 << 11);

bool par(pt A, pt B, pt C, pt D){
	return (ll)(A.X - B.X) * (C.Y - D.Y) == (ll)(C.X - D.X) * (A.Y - B.Y);
}

ll ccw(pt A, pt B, pt C){
	return (ll)A.X * (B.Y - C.Y) + (ll)B.X * (C.Y - A.Y) + (ll)C.X * (A.Y - B.Y);
}

pt sm[M], toc[N], ISH = {0, 0};
int pr[M], dr[M], pos[N], rd[N], duz[M], V[N];
int n, m;

inline bool cmp(int i, int j){
	return ccw(sm[i], ISH, sm[j]) < 0;
}

inline bool cmp2(int i, int j){
	if(toc[i].Y == toc[j].Y)
		return toc[i].X > toc[j].X;
	return toc[i].Y < toc[j].Y;
}

inline bool cmp3(int i, int j){
	return pos[i] < pos[j];
}

struct node{
	ll sol, L, R, sve;
	node(){
		sol = 0; L = 0; R = 0; sve = 0;
	}
	node(int x){
		sol = max(x, 0); L = sol; R = sol; sve = x;
	}
};

node T[2 * OFF];

inline node mrg(const node &A, const node &B){
	node C;
	C.sol = max(max(A.sol, B.sol), A.R + B.L);
	C.sve = A.sve + B.sve;
	C.L = max(A.L, A.sve + B.L);
	C.R = max(B.R, B.sve + A.R);
	return C;
};

void update(int i, int x){
	i += OFF;
	T[i] = node(x);
	for(i /= 2; i ; i /= 2)
		T[i] = mrg(T[2 * i], T[2 * i + 1]);
}

inline void obrni(int l, int r){
	for(;l < r;l++,r--){
		swap(rd[l], rd[r]);
		swap(pos[rd[l]], pos[rd[r]]);
		update(l, V[rd[l]]);
		update(r, V[rd[r]]);
	}
}

int main(){	
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d%d%d", &toc[i].X, &toc[i].Y, V + i);
		rd[i] = i;
	}
	sort(rd, rd + n, cmp2);
	for(int i = 0;i < n;i++){
		pos[rd[i]] = i;
		update(i, V[rd[i]]);
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < i;j++){
			pr[m] = rd[i];
			dr[m] = rd[j];
			sm[m] = {toc[pr[m]].X - toc[dr[m]].X, toc[pr[m]].Y - toc[dr[m]].Y};
			duz[m] = m; m++;
		}
	}
	sort(duz, duz + m, cmp);
	ll ans = T[1].sol;
	for(int i = 0;i < m;){
		int j = i;
		while(j < m && ccw(sm[duz[i]], ISH, sm[duz[j]]) == 0){
			//printf("sm[ %d ] = {%d %d}\n", duz[j], sm[duz[j]].X, sm[duz[j]].Y);
			j++;
		}
		//printf("[%d, %d> su paralelni\n", i, j);
		vector < int > pomak;
		for(int k = i;k < j;k++){
		//	printf("pravac %d %d\n", pr[duz[k]], dr[duz[k]]);
			pomak.PB(pos[pr[duz[k]]]);
			pomak.PB(pos[dr[duz[k]]]);
		}
		sort(pomak.begin(), pomak.end());
		int lst = -1;
		for(int k : pomak){
			if(k <= lst) continue;
			int en = k + 1;
			while(en + 1 < n && par(toc[rd[k]], toc[rd[k + 1]], toc[rd[en]], toc[rd[en + 1]]))
				en++;
		//	printf("obrcem %d %d\n", k, en);
			obrni(k, en); lst = en;
		}
		ans = max(ans, T[1].sol);
		i = j;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bulldozer.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   scanf("%d%d%d", &toc[i].X, &toc[i].Y, V + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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