제출 #154605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154605		Mercenary	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	4 ms	760 KiB

bulldozer

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;

const int maxn = 2e3 + 5;

int n;
struct point{
    int x , y , c;
}a[maxn];
struct line{
    int x , y , ii , jj;
};
struct node{
    ll res , pre , sum , suf;
    node(){};
    node(ll sum , ll res , ll pre , ll suf):sum(sum) , res(res) , pre(pre) , suf(suf){}
    node operator + (const node & other){
        return node(
                sum + other.sum,
                max({res , other.res , suf + other.pre}),
                max({pre , sum + other.pre}),
                max({other.suf , other.sum + suf})
                    );
    }
}s[maxn * 4];

void Build(int x , int l , int r){
    if(l == r){
        s[x] = node(a[l].c , a[l].c , a[l].c , a[l].c);
        return;
    }
    int mid = l + r >> 1;
    Build(x * 2 , l , mid);
    Build(x * 2 + 1 , mid + 1 , r);
    s[x] = s[x * 2] + s[x * 2 + 1];
}

void update(int x , int l , int r , int pos , int val){
    if(l == r){
        s[x] = node(val , val , val ,val);
        return;
    }
    int mid = l + r >> 1;
    if(mid >= pos)update(x * 2 , l , mid , pos , val);
    else update(x * 2  + 1 , mid + 1 , r , pos , val);
    s[x] = s[x * 2] + s[x * 2 + 1];
}
int cur[maxn];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP", "r",stdin);
        freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i].x >> a[i].y >> a[i].c;
        cur[i] = i;
    }
    sort(a + 1 , a + n + 1 , [&](const point & x , const point & y){
            if(x.x == y.x)return x.y < y.y;
            return x.x < y.x;
         });
    vector<line> v;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = i + 1 ; j <= n ; ++j){
            v.pb({a[i].x - a[j].x , a[i].y - a[j].y , i , j});
        }
    }
    stable_sort(v.begin(),v.end(),[&](const line & a , const line & b){
            return (ll)a.x * b.y - (ll)a.y * b.x > 0;
                });
    int j = 0;
    ll ans = 0;
    for(int i = 0 ; i < (int)v.size() ; ){
        while(j < (int)v.size() && (ll)v[i].x * v[j].y == (ll)v[i].y * v[j].x){
            swap(cur[v[j].ii] , cur[v[j].jj]);
            update(1 , 1 , n , cur[v[j].ii] , a[v[j].ii].c);
            update(1 , 1 , n , cur[v[j].jj] , a[v[j].jj].c);
            ++j;
        }
        ans = max(ans , s[1].res);
        i = j;
    }
    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In constructor 'node::node(ll, ll, ll, ll)':
bulldozer.cpp:22:20: warning: 'node::sum' will be initialized after [-Wreorder]
     ll res , pre , sum , suf;
                    ^~~
bulldozer.cpp:22:8: warning:   'll node::res' [-Wreorder]
     ll res , pre , sum , suf;
        ^~~
bulldozer.cpp:24:5: warning:   when initialized here [-Wreorder]
     node(ll sum , ll res , ll pre , ll suf):sum(sum) , res(res) , pre(pre) , suf(suf){}
     ^~~~
bulldozer.cpp: In function 'void Build(int, int, int)':
bulldozer.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
bulldozer.cpp: In function 'void update(int, int, int, int, int)':
bulldozer.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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