oj.uz

Submission #709379

# Submission time Handle Problem Language Result Execution time Memory
709379 2023-03-13T13:52:03 Z Antekb Bulldozer (JOI17_bulldozer) C++17
0 / 100
 266 ms 1444 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];
vector<pii> V2;
ll ans=0;
int n;
void dodaj(int v, int c){
	val[v+N]+=c;
}
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;
}
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());
}
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;
	for(int i=0; i<V.size(); i++){
		zmien({V[i].nd.st, V[i].nd.nd});
	}
	cout<<ans;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:94: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]
   94 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 1272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 1444 KB Output is correct
2 Correct 264 ms 1344 KB Output is correct
3 Correct 210 ms 1360 KB Output is correct
4 Correct 215 ms 1368 KB Output is correct
5 Correct 224 ms 1364 KB Output is correct
6 Correct 232 ms 1312 KB Output is correct
7 Correct 231 ms 1324 KB Output is correct
8 Correct 266 ms 1396 KB Output is correct
9 Correct 238 ms 1384 KB Output is correct
10 Correct 241 ms 1300 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Incorrect 1 ms 316 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 1444 KB Output is correct
2 Correct 264 ms 1344 KB Output is correct
3 Correct 210 ms 1360 KB Output is correct
4 Correct 215 ms 1368 KB Output is correct
5 Correct 224 ms 1364 KB Output is correct
6 Correct 232 ms 1312 KB Output is correct
7 Correct 231 ms 1324 KB Output is correct
8 Correct 266 ms 1396 KB Output is correct
9 Correct 238 ms 1384 KB Output is correct
10 Correct 241 ms 1300 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Incorrect 1 ms 316 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 1444 KB Output is correct
2 Correct 264 ms 1344 KB Output is correct
3 Correct 210 ms 1360 KB Output is correct
4 Correct 215 ms 1368 KB Output is correct
5 Correct 224 ms 1364 KB Output is correct
6 Correct 232 ms 1312 KB Output is correct
7 Correct 231 ms 1324 KB Output is correct
8 Correct 266 ms 1396 KB Output is correct
9 Correct 238 ms 1384 KB Output is correct
10 Correct 241 ms 1300 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Incorrect 1 ms 316 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 1272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -