| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 337435 |
2020-12-20T18:55:20 Z |
YJU |
Bulldozer (JOI17_bulldozer) |
C++14 |
|
4 ms |
1008 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e3+5;
const ld pi=acos(-1);
const ll INF=(1LL<<30);
const ld zero=1e-12;
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll n,x[N],y[N],c[N],pos[N],ans,ma[4*N],lma[4*N],rma[4*N],sum[4*N];
vector<ll> lis;
vector<pair<ld,pll> > event;
void mod(ll nda,ll ndb){
ld cel=asin((y[nda]-y[ndb])/sqrt(SQ(y[nda]-y[ndb])+SQ(x[nda]-x[ndb])));
cel=(cel+pi/2>2*pi?cel+pi/2-2*pi:cel+pi/2);
//cout<<nda<<" "<<ndb<<" "<<cel/pi<<"\n";
event.pb(mp(cel,mp(nda,ndb)));
cel=(cel+pi>2*pi?cel-pi:cel+pi);
event.pb(mp(cel,mp(nda,ndb)));
}
void upd(ll id,ll l,ll r,ll to){
if(l==r-1){ma[id]=lma[id]=rma[id]=max(0LL,c[lis[l]]);sum[id]=c[lis[l]];return ;}
ll mid=(l+r)>>1;
if(to<mid)upd(id*2,l,mid,to);
else upd(id*2+1,mid,r,to);
sum[id]=sum[id*2]+sum[id*2+1];
lma[id]=max(lma[id*2],lma[id*2+1]+sum[id*2]);
rma[id]=max(rma[id*2]+sum[id*2+1],rma[id*2+1]);
ma[id]=max(max(ma[id*2],ma[id*2+1]),lma[id*2+1]+rma[id*2]);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
REP(i,n){
cin>>x[i]>>y[i]>>c[i];
lis.pb(i);
}
sort(lis.begin(),lis.end(),[](ll A,ll B){
if(x[A]!=x[B])return (x[A]<x[B]);
return (y[A]>y[B]);
});
REP(i,n)pos[lis[i]]=i;
REP(i,n)upd(1,0,n,i);
ans=ma[1];
REP(i,n){
for(int j=i+1;j<n;j++){
mod(lis[i],lis[j]);
}
}
sort(event.begin(),event.end());
//for(auto i:event)cout<<i.Y.X<<" "<<i.Y.Y<<"\n";
REP(i,SZ(event)){
if(i&&abs(event[i].X-event[i-1].X)<zero)ans=max(ans,ma[1]);
//cout<<fixed<<setprecision(12)<<event[i].X<<" "<<event[i].Y.X<<" "<<event[i].Y.Y<<"\n";
//REP(j,n)cout<<lis[j]<<(j==n-1?"\n":" ");
//cout<<ma[1]<<"\n";
ll nx=event[i].Y.X,ny=event[i].Y.Y;
swap(lis[pos[nx]],lis[pos[ny]]);
upd(1,0,n,pos[nx]);
upd(1,0,n,pos[ny]);
swap(pos[nx],pos[ny]);
}
cout<<ans<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
