Submission #1183324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183324		vnedu	Bulldozer (JOI17_bulldozer)	C++20	25 / 100	25 ms	576 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 2e3 + 23;
int n;
struct Point
{
    int x,y,c;
    Point() {}
    void input()
    {
        cin>>x>>y>>c;
    }
} point[N];
struct line
{
    ll a,b,c;
    line() {}
    line(ll a, ll b, ll c) : a(a),b(b),c(c) {}
    ll getVal(const Point &x)
    {
        return a*x.x+b*x.y+c;
    }
    bool checksongsong(const line &S)
    {
        ll a1=a,b1=b,c1=c;
        ll a2=S.a,b2=S.b,c2=S.c;
        if (a1*b2-a2*b1!=0) return 0;
        if (-c1*b2+c2*b1==0 && -c1*a2+c2*a1==0) return 0;
        return 1;
    }
    double getDis(const Point &S)
    {
        ll x=S.x,y=S.y;
        return abs(a*x+b*y+c)/sqrt(a*a+b*b);
    }
};
line getPass(Point x, Point y)
{
    ll x1=x.x,y1=x.y;
    ll x2=y.x,y2=y.y;
    ll a=y2-y1;
    ll b=x1-x2;
    ll c=-(a*x1+b*y1);
    return line(a,b,c);
}
namespace sub1
{
    bool check()
    {
        if (n>100) return 0;
        for (int i=1; i<=n; ++i) if (point[i].y!=0) return 0;
        return 1;
    }
    bool cmp1(Point &x, Point &y)
    {
        return x.x<y.x;
    }
    void solve()
    {
        sort(point+1,point+1+n,cmp1);
        ll ans=0;
        for (int i=1; i<=n; ++i)
        {
            ll sum=0;
            for (int j=i; j<=n; ++j)
            {
                sum+=point[j].c;
                maximize(ans,sum);
            }
        }
        cout<<ans;
    }
}
namespace sub2
{
    const int N = 100 + 5;
    line m[N*N];
    bool check()
    {
        if (n>100) return 0;
        int ptr=0;
        for (int i=1; i<=n; ++i) for (int j=i+1; j<=n; ++j)
        {
            line gaugau=getPass(point[i],point[j]);
            int cnt=0;
            for (int k=1; k<=n; ++k) cnt+=(gaugau.getVal(point[k])==0);
            if(cnt!=2) return 0;
            m[++ptr]=gaugau;
        }
        for (int i=1; i<=ptr; ++i) for (int j=i+1; j<=ptr; ++j) if (m[i].checksongsong(m[j])) return 0;
        return 1;
    }
    pair<double,ll> left[N],right[N];
    int ptrLeft,ptrRight;
    void solve()
    {
        int ptr=0;
        ll ans=0;
        for (int i=1; i<=n; ++i) for (int j=i+1; j<=n; ++j)
        {
            line cm=m[++ptr];
            ptrLeft=ptrRight=0;
            for (int k=1; k<=n; ++k) if (k!=i && k!=j)
            {
                ll gogo=cm.getVal(point[k]);
                if (gogo<0)
                {
                    left[++ptrLeft]=make_pair(cm.getDis(point[k]),point[k].c);
                }
                else
                {
                    right[++ptrRight]=make_pair(cm.getDis(point[k]),point[k].c);
                }
            }
            sort(left+1,left+1+ptrLeft);
            sort(right+1,right+1+ptrRight);
            ll mx=0,curSum;
            curSum=0;
            for (int id=1; id<=ptrLeft; ++id)
            {
                curSum+=left[id].se;
                maximize(mx,curSum);
            }
            curSum=0;
            for (int id=1; id<=ptrRight; ++id)
            {
                curSum+=right[id].se;
                maximize(mx,curSum);
            }
            maximize(ans,mx+point[i].c+point[j].c-min({0,point[i].c,point[j].c}));
        }
        cout<<ans;
    }
}
void solve()
{
    cin>>n;
    for (int i=1; i<=n; ++i) point[i].input();
    if (sub1::check()) return void(sub1::solve());
    if (sub2::check()) return void(sub2::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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