Submission #580273

#	Time	Username	Problem	Language	Result	Execution time	Memory
580273		lkh3happy	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1090 ms	17112 KiB

bulldozer

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct st{
    long long lmx=-1e18, rmx=-1e18, mx=-1e18, sum=0;
}t[8001];

struct st1{
    long long first, second, c;
}A[2001], now[2001];

st operator + (st a, st b){
    return {max(a.lmx, a.sum+b.lmx), max(a.rmx+b.sum, b.rmx), max(max(a.mx, b.mx), a.rmx+b.lmx), a.sum+b.sum};
}

bool operator < (st1 a, st1 b){
    if(a.first==b.first) return a.second<b.second;
    return a.first<b.first;
}

vector<pair<int, int> > v;
int pos[2001];

void upd(int l, int r, int n, int x, int y){
    if(x<l || r<x) return;
    if(l==r){
        t[n].lmx=t[n].rmx=t[n].mx=max(0, y);
        t[n].sum=y;
        return;
    }
    int m=l+r>>1;
    upd(l, m, n*2, x, y); upd(m+1, r, n*2+1, x, y);
    t[n]=t[n*2]+t[n*2+1];
    return;
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%lld %lld %lld\n", &A[i].first, &A[i].second, &A[i].c);
    sort(A+1, A+n+1);
    for(int i=1;i<=n;i++) pos[i]=i, now[i]=A[i], upd(1, n, 1, i, A[i].c);
    for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(A[i].first^A[j].first) v.push_back({i, j});
    sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b){
        if((A[a.second].second-A[a.first].second)*(A[b.second].first-A[b.first].first)==(A[b.second].second-A[b.first].second)*(A[a.second].first-A[a.first].first)){
            if(a.first==b.first) return A[a.second]<A[b.second];
            return A[a.first]<A[b.first];
        }
        return ((A[a.second].second-A[a.first].second)*(A[b.second].first-A[b.first].first)<(A[b.second].second-A[b.first].second)*(A[a.second].first-A[a.first].first));
    });
    long long mx=max(0LL, t[1].mx);
    for(int a=0, b=0;a<v.size();a=b){
        while(b<v.size() && (A[v[a].second].second-A[v[a].first].second)*(A[v[b].second].first-A[v[b].first].first)==(A[v[b].second].second-A[v[b].first].second)*(A[v[a].second].first-A[v[a].first].first)) b++;
        for(int k=a;k<b;k++){
            int i=v[k].first, j=v[k].second;
            swap(now[pos[i]], now[pos[j]]);
            swap(pos[i], pos[j]);
            upd(1, n, 1, pos[i], now[pos[i]].c);
            upd(1, n, 1, pos[j], now[pos[j]].c);
        }
        mx=max(mx, t[1].mx);
    }
    printf("%lld\n", mx);
    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'void upd(int, int, int, int, int)':
bulldozer.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int m=l+r>>1;
      |           ~^~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int a=0, b=0;a<v.size();a=b){
      |                      ~^~~~~~~~~
bulldozer.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while(b<v.size() && (A[v[a].second].second-A[v[a].first].second)*(A[v[b].second].first-A[v[b].first].first)==(A[v[b].second].second-A[v[b].first].second)*(A[v[a].second].first-A[v[a].first].first)) b++;
      |               ~^~~~~~~~~
bulldozer.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
bulldozer.cpp:42:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for(int i=1;i<=n;i++) scanf("%lld %lld %lld\n", &A[i].first, &A[i].second, &A[i].c);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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