Submission #1199235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199235		alexander707070	Bulldozer (JOI17_bulldozer)	C++20	0 / 100	170 ms	444 KiB

bulldozer

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

const long double eps=0.000000001;

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

    inline friend bool operator < (point fr,point sc){
        if(fabs(fr.x-sc.x)<eps)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);
    }
}

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);

        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+=0.1;

        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-=0.2;

        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++){
        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