Submission #1040530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040530		thangnguyen	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	694 ms	51884 KiB

bulldozer

#include <bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define TASKS "i."
#define fast ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define all(x) x.begin(),x.end()
#define FORU(i,a,b) for(int i = a, _b = b; i <= _b ; i++)
#define FORD(i,a,b) for(int i = a, _b = b; i >= _b ; i--)
#define endl "\n"

using namespace std;
const int maxn = 2000 ;
int n ;
struct mineinfo
{
    int x, y,z ;
    void inp() {cin >> x >> y >> z ; }
    bool operator < (const mineinfo &o)
    {
        if(x == o.x) return y > o.y ;
        return x < o.x ;
    }
} a[maxn+1];

struct lineinfo
{
    ll a,b; int id1, id2 ;
    bool operator < (const lineinfo &x)
    {
        if(x.a * a == 0)
        {
            if(a + x.a == 0) return make_pair(id1,id2) < make_pair(x.id1,x.id2) ;
            return (a == 0) ;
        }
        if(a == x.a && b == x.b) return make_pair(id1,id2) < make_pair(x.id1,x.id2) ;
        return x.a * b < a * x.b ;
    }
    void get(ii A, ii B, int i, int j)
    {
        a = B.fi - A.fi , b = B.se - A.se ;
        int c = abs(__gcd(a,b)) ;
        a/=c, b/= c ;
        id1 = i, id2 = j ;
    }
} ;
vector<lineinfo> line ;
int id[maxn+1] ;
bool kt[maxn+1] ;

struct nodeinfo
{
    ll sum, mx, mxl, mxr ;
} ;

struct SegmentTree
{
    nodeinfo val[maxn*4] ;
    void cal(nodeinfo &x, nodeinfo c1, nodeinfo c2)
    {
        x.sum = c1.sum + c2.sum ;
        x.mxl = max(c1.mxl, c1.sum + c2.mxl) ;
        x.mxr = max(c2.mxr, c2.sum + c1.mxr) ;
        x.mx = max({c1.mx,c2.mx,c1.mxr + c2.mxl}) ;
    }
    void update(int id, int v)
    {
        int x = 1, L = 1, R = n ;
        while(L < R)
        {
            int mid = (L+R)>>1;
            if(id <= mid) x = x<<1,R = mid ;
            else x = x<<1|1,L = mid + 1 ;
        }
        val[x].sum = v , val[x].mxl = v, val[x].mxr = v ;
        if(v > 0) val[x].mx = v;
        x>>=1 ;
        while(x)
        {
            cal(val[x],val[x<<1],val[x<<1|1])  ;
            x>>=1 ;
        }
        return ;
    }
    ll getans()
    {
        return val[1].mx ;
    }
}tree;

int main()
{
    fast ;
//    freopen(TASKS"INP","r",stdin) ;
//    freopen(TASKS"OUT","w",stdout) ;
    cin >> n ;
    FORU(i,1,n) a[i].inp();
    sort(&a[1],&a[n+1])  ;

    FORU(i,1,n)
    {
        tree.update(i,a[i].z) ;
        ii A = {a[i].x,a[i].y} , B ;
        id[i] = i ;
        lineinfo l ;
        FORU(j,i+1,n)
        {
            B = {a[j].x,a[j].y} ;
            l.get(A,B,i,j) ;
            line.push_back(l) ;
        }
    }
    sort(all(line)) ;
    ll ans = tree.getans() ;
    FORU(i,0,line.size() - 1)
    {
        if(i == 7)
            int tor = 1;
        lineinfo l = line[i];
        tree.update(id[l.id2],a[l.id1].z) ;
        tree.update(id[l.id1],a[l.id2].z) ;
        swap(id[l.id1],id[l.id2]) ;
//        FORU(i,1,n) cout << id[i] << ' ' ;
//        cout << endl ;
        if(i + 1 < line.size() && (line[i+1].a == l.a && line[i+1].b ==l.b))
        {
            continue ;
        }
        ans = max(ans,tree.getans()) ;
    }
    cout << ans;
    return 0 ;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:119:17: warning: unused variable 'tor' [-Wunused-variable]
  119 |             int tor = 1;
      |                 ^~~
bulldozer.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<lineinfo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         if(i + 1 < line.size() && (line[i+1].a == l.a && line[i+1].b ==l.b))
      |            ~~~~~~^~~~~~~~~~~~~

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