Submission #1118163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118163		Pannda	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	81 ms	336 KiB

bulldozer

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "TRUFFLE"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
struct point{
    ll x,y,w;
    bool operator < (const point &other){
        if(x!=other.x) return x<other.x;
        return y<other.y;
    }
};
inline ll dir(point a,point b,point c){
    b.x-=a.x;
    c.x-=a.x;
    b.y-=a.y;
    c.y-=a.y;
    ll diff=b.x*c.y-c.x*b.y;
    if(diff<0) return -1;
    else if(diff==0) return 0;
    else return 1;
}
point arr[2001];
ll n;
void sub1(){
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int u=i-1;u;u--){
                ll curr=0;
                point ao={arr[u].x+arr[j].x-arr[i].x,arr[u].y+arr[j].y-arr[i].y,0};
                for(int v=1;v<=n;v++){
                    if(dir(arr[i],arr[j],arr[v])!=dir(arr[u],ao,arr[v])){
                        curr+=arr[v].w;
                    }
                }
                ans=max(ans,curr);
            }
            for(int u=j+1;u<=n;u++){
                ll curr=0;
                point ao={arr[u].x+arr[j].x-arr[i].x,arr[u].y+arr[j].y-arr[i].y,0};
                for(int v=1;v<=n;v++){
                    if(dir(arr[i],arr[j],arr[v])!=dir(arr[u],ao,arr[v])){
                        curr+=arr[v].w;
                    }
                }
                ans=max(ans,curr);
            }
        }
    }
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x,y,w;
        cin>>x>>y>>w;
        arr[i]={x,y,w};
    }
    sort(arr+1,arr+n+1);
    sub1();
    //else sub2();
}

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