Submission #1199263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199263		alexander707070	Bulldozer (JOI17_bulldozer)	C++20	0 / 100	139 ms	616 KiB

bulldozer

#include<bits/stdc++.h>
#define pi M_PI
#define MAXN 2007
using namespace std;

const long double eps=0.000000000001;

struct point{
    long double x,y;
    int cost;

    inline friend bool operator < (point fr,point sc){
        if(fr.x!=sc.x)return fr.y<sc.y;
        return fr.x<sc.x;
    }

}p[MAXN],t[MAXN];

int n,m;
long long a[MAXN],ans;

void solve_ver(){
    sort(t+1,t+n+1);
    
    m=0;
    for(int i=1;i<=n;i++){
        if(i>1 and fabs(t[i].x-t[i-1].x)<eps){
            a[m]+=t[i].cost;
        }else{
            m++; a[m]=t[i].cost;
        }
    }

    long long sum=0;
    for(int i=1;i<=m;i++){
        sum+=a[i];
        if(sum<0)sum=0;
        ans=max(ans,sum);
    }
}

int k;
long double angles[MAXN*MAXN];

void lines(point s){
    for(int i=1;i<=n;i++){
        p[i].x-=s.x; p[i].y-=s.y;
    }

    for(int i=1;i<=n;i++){
        if(p[i].x==0 and p[i].y==0)continue;

        double angle=pi/2 - atan2(p[i].y,p[i].x);
        angles[++k]=angle;
    }

    for(int i=1;i<=n;i++){
        p[i].x+=s.x; p[i].y+=s.y;
    }
}

long double nxt(long double x){
    int l=0,r=k+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(angles[tt]>x){
            r=tt;
        }else{
            l=tt;
        }
    }

    if(r==k+1)return x + (2*pi-(x-angles[1]))/2.0;
    return (angles[r]+angles[r-1])/2.0;
}

long double pr(long double x){
    int l=0,r=k+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(angles[tt]<x){
            l=tt;
        }else{
            r=tt;
        }
    }

    if(l==0)return x - (2*pi-(angles[k]-x))/2.0;
    return (angles[l]+angles[l+1])/2.0;
}

void solve(point s){
    for(int i=1;i<=n;i++){
        p[i].x-=s.x; p[i].y-=s.y;
    }

    for(int i=1;i<=n;i++){
        if(p[i].x==0 and p[i].y==0)continue;

        double angle=pi/2 - atan2(p[i].y,p[i].x),curr=angle;

        for(int f=1;f<=n;f++){
            t[f]={p[f].x*cos(angle) + p[f].y*sin(angle) , -p[f].x*sin(angle) + p[f].y*cos(angle),p[f].cost};
        }
        solve_ver();

        angle=nxt(curr);

        for(int f=1;f<=n;f++){
            t[f]={p[f].x*cos(angle) + p[f].y*sin(angle) , -p[f].x*sin(angle) + p[f].y*cos(angle),p[f].cost};
        }
        solve_ver();

        angle=pr(curr);

        for(int f=1;f<=n;f++){
            t[f]={p[f].x*cos(angle) + p[f].y*sin(angle) , -p[f].x*sin(angle) + p[f].y*cos(angle),p[f].cost};
        }
        solve_ver();
    }

    for(int i=1;i<=n;i++){
        p[i].x+=s.x; p[i].y+=s.y;
    }
}

int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y>>p[i].cost;
    }

    for(int i=1;i<=n;i++)lines(p[i]);
    sort(angles+1,angles+k+1);

    for(int i=1;i<=n;i++){
        solve(p[i]);
    }

    cout<<ans<<"\n";

    return 0;
}

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