oj.uz

Submission #709411

# Submission time Handle Problem Language Result Execution time Memory
709411 2023-03-13T14:13:43 Z Antekb Bulldozer (JOI17_bulldozer) C++17
20 / 100
 2000 ms 66260 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t))cerr<<", ";
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int N=(1<<11), INF=1e9+5;
int wei[N], gdzie[N], gdzie2[N];
ll val[N+N], pref[N+N], suf[N+N], res[N+N];
vector<pii> V2;
ll ans=0;
int n;
void dodaj(int v, int c){
	val[v+N]+=c;
	pref[v+N]=max(val[v+N], 0ll);
	suf[v+N]=max(val[v+N], 0ll);
	res[v+N]=max(val[v+N], 0ll);
	v+=N;
	v/=2;
	while(v){
		int l=v+v, r=l+1;
		res[v]=max(res[l], res[r]);
		pref[v]=max(pref[l], val[l]+pref[r]);
		suf[v]=max(suf[r], val[r]+suf[l]);
		val[v]=val[l]+val[r];
		res[v]=max(res[v], pref[r]+suf[l]);
		v/=2;
	}
}
ll get_ans(){
	/*ll dp=0, res=0;
	for(int i=n-1; i>=0; i--){
		dp=max(dp+val[i+N], 0ll);
		res=max(res, dp);
	}
	deb(res);*/
	return res[1];
}
/*void zmien(vector<int> V){
	/*sort(all(V), [](int a, int b){return gdzie[a]<gdzie[b];});
	//assert(V.size()==2);
	int c=gdzie[V[0]];
	ans=max(ans, get_ans());
	for(int i=V.size()-1; i>0;i--){
		dodaj(c, wei[V[i]]);
		dodaj(gdzie[V[i]], -wei[V[i]]);
	}
	ans=max(ans, get_ans());
	for(int i=V.size()-1; i>=0; i--){
		if(i<=V.size()-1-i)break;
		swap(gdzie[V[i]], gdzie[V[V.size()-i-1]]);
	}
	reverse(all(V));
	for(int i=V.size()-1; i>0;i--){
		dodaj(c, -wei[V[i]]);
		dodaj(gdzie[V[i]], wei[V[i]]);
	}
	ans=max(ans, get_ans());
	//for(int i=0; i<n; i++)cout<<gdzie[i]<<" ";cout<<"\n";
	//assert(abs(gdzie[V[0]]-gdzie[V[1]])==1);
	//deb(V[0], V[1], gdzie[V[0]], gdzie[V[1]]);
	ans=max(ans, get_ans());
	dodaj(gdzie[V[0]], wei[V[1]]);
	dodaj(gdzie[V[1]], -wei[V[1]]);
	ans=max(ans, get_ans());
	//deb(val[N], val[N+1], val[N+2], val[N+3]);
	dodaj(gdzie[V[0]], -wei[V[0]]);
	dodaj(gdzie[V[1]], wei[V[0]]);
	swap(gdzie[V[0]], gdzie[V[1]]);
	ans=max(ans, get_ans());
}*/
vector<int> co[N];
void upd(vector<pii> V){
	map<int, int> M;
	for(pii i:V){
		M[i.st]=gdzie[i.st];
		M[i.nd]=gdzie[i.nd];
	}
	for(pii i:V){
		M[i.nd]=min(M[i.nd], gdzie[i.st]);
		M[i.st]=min(M[i.st], gdzie[i.nd]);
	}
	vi waz;
	for(auto i:M){
		co[i.nd].pb(i.st);
		dodaj(gdzie[i.st], -wei[i.st]);
		dodaj(i.nd, wei[i.st]);
		if(i.nd==gdzie[i.st])waz.pb(i.nd);
	}
	ans=max(ans, get_ans());
	for(int i:waz){
		for(int j:co[i]){
			gdzie[j]=co[i].size()-1+2*i-gdzie[j];
		}
	}
	for(auto i:M){
		dodaj(gdzie[i.st], wei[i.st]);
		dodaj(i.nd, -wei[i.st]);
	}
	ans=max(ans, get_ans());
	for(auto i:waz){
		co[i].clear();
	}
}
int main(){
	cin>>n;
	V2.resize(n);
	for(int i=0; i<n; i++)cin>>V2[i].st>>V2[i].nd>>wei[i], gdzie2[i]=i;
	sort(gdzie2, gdzie2+n, [](int a, int b){if(V2[a].st==V2[b].st)return V2[a].nd>V2[b].nd;return V2[a].st<V2[b].st;});
	for(int i=0; i<n; i++)gdzie[gdzie2[i]]=i;
	for(int i=0; i<n; i++)dodaj(gdzie[i], wei[i]);
	vector<pair<ld, pii> > V;
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			int x=V2[i].st-V2[j].st, y=V2[i].nd-V2[j].nd;
			if(x>0)y=-y, x=-x;
			if(x==0 && y<0)y=-y;
			ld kat=-atan2(x, y);
			//deb(kat, x, y, i, j);
			V.eb(kat, mp(i, j));
		}
	}
	sort(all(V));
	vector<pii> todo;
	ans=max(ans, get_ans());
	for(int i=0; i<V.size(); i++){
		todo.pb(V[i].nd);
		if(i==n-1 || V[i].st!=V[i+1].st){
			upd(todo);
			todo.clear();
		}
		//zmien({V[i].nd.st, V[i].nd.nd});
	}
	cout<<ans;
}

Compilation message

bulldozer.cpp:56:2: warning: "/*" within comment [-Wcomment]
   56 |  /*sort(all(V), [](int a, int b){return gdzie[a]<gdzie[b];});
      |   
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:142:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 8 ms 744 KB Output is correct
5 Correct 7 ms 744 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 7 ms 744 KB Output is correct
8 Correct 7 ms 748 KB Output is correct
9 Correct 7 ms 724 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 360 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 360 KB Output is correct
21 Correct 7 ms 724 KB Output is correct
22 Correct 7 ms 724 KB Output is correct
23 Correct 6 ms 744 KB Output is correct
24 Correct 7 ms 724 KB Output is correct
25 Correct 7 ms 740 KB Output is correct
26 Correct 7 ms 724 KB Output is correct
27 Correct 8 ms 740 KB Output is correct
28 Correct 7 ms 724 KB Output is correct
29 Correct 9 ms 724 KB Output is correct
30 Correct 7 ms 724 KB Output is correct
31 Correct 7 ms 724 KB Output is correct
32 Correct 7 ms 724 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 8 ms 744 KB Output is correct
5 Correct 7 ms 744 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 7 ms 744 KB Output is correct
8 Correct 7 ms 748 KB Output is correct
9 Correct 7 ms 724 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 360 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 360 KB Output is correct
21 Correct 7 ms 724 KB Output is correct
22 Correct 7 ms 724 KB Output is correct
23 Correct 6 ms 744 KB Output is correct
24 Correct 7 ms 724 KB Output is correct
25 Correct 7 ms 740 KB Output is correct
26 Correct 7 ms 724 KB Output is correct
27 Correct 8 ms 740 KB Output is correct
28 Correct 7 ms 724 KB Output is correct
29 Correct 9 ms 724 KB Output is correct
30 Correct 7 ms 724 KB Output is correct
31 Correct 7 ms 724 KB Output is correct
32 Correct 7 ms 724 KB Output is correct
33 Execution timed out 2079 ms 66260 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 8 ms 744 KB Output is correct
5 Correct 7 ms 744 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 7 ms 744 KB Output is correct
8 Correct 7 ms 748 KB Output is correct
9 Correct 7 ms 724 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 360 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 360 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 360 KB Output is correct
21 Correct 7 ms 724 KB Output is correct
22 Correct 7 ms 724 KB Output is correct
23 Correct 6 ms 744 KB Output is correct
24 Correct 7 ms 724 KB Output is correct
25 Correct 7 ms 740 KB Output is correct
26 Correct 7 ms 724 KB Output is correct
27 Correct 8 ms 740 KB Output is correct
28 Correct 7 ms 724 KB Output is correct
29 Correct 9 ms 724 KB Output is correct
30 Correct 7 ms 724 KB Output is correct
31 Correct 7 ms 724 KB Output is correct
32 Correct 7 ms 724 KB Output is correct
33 Execution timed out 2079 ms 66260 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -