제출 #1041403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041403		wibulord	Bulldozer (JOI17_bulldozer)	C++14	75 / 100	527 ms	51924 KiB

bulldozer

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define ii pair<int, int>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define sz(s) (int)((s).size())
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using namespace std;

template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}

const int MOD = (int)1e9 + 7;
const int mod = 998244353;
const int N = 2e3 + 10, M = 14;
const long long INF = (long long)4e18 + 11;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/

int n;
struct Pt{
    int x, y, w;
    Pt(){}
    Pt(int _x, int _y, int _w){
        x = _x, y = _y, w = _w;
    }
    bool operator < (const Pt &p) const{
        return x != p.x ? x < p.x : y < p.y;
    }
}A[N];

struct Line{
    long long A, B;
    int id1, id2;
    Line(){}
    Line(long long _A, long long _B, int _id1, int _id2){
        A = _A, B = _B, id1 = _id1, id2 = _id2;
    }
    bool operator < (const Line &p) const{
        return A * p.B < B * p.A;
    }
};
vector<Line> Slope;

int pos[N];
struct Node{
    long long sum, L, R, mx;
    Node(){
        sum = 0;
        L = R = mx = -INF;
    }
}st[MASK(M)];

void update(int i, int l, int r, int p, long long d){
    while(l < r){
        int m = (l + r) >> 1;
        if(p <= m) r = m, i = i<<1;
        else l = m+1, i = i<<1|1;
    }
    st[i].sum = st[i].L = st[i].R = st[i].mx = d;
    while(i > 1){
        i >>= 1;
        st[i].sum = st[i<<1].sum + st[i<<1|1].sum;
        st[i].L = max(st[i<<1].L, st[i<<1].sum + st[i<<1|1].L);
        st[i].R = max(st[i<<1|1].R, st[i<<1|1].sum + st[i<<1].R);
        st[i].mx = max({st[i<<1].mx, st[i<<1|1].mx, st[i<<1].R + st[i<<1|1].L});
    }
}


void sol(void){
    cin >> n;
    FOR(i, 1, n){
        int x, y, w; cin >> x >> y >> w;
        A[i] = Pt(x, y, w);
    }
    sort(A+1,A+n+1);
    FOR(i, 1, n) FOR(j, i+1, n){
        Line tmp = Line(A[j].x - A[i].x, A[j].y - A[i].y, i, j);
        Slope.push_back(tmp);
    }
    sort(all(Slope));
    FOR(i, 1, n){
        pos[i] = i;
        update(1, 1, n, i, A[i].w);
    }
    long long ans = max(0LL, st[1].mx);

    int m = sz(Slope) - 1, j = 0;
    for(int i = 0; i <= m; i++){
        while(j <= m && Slope[i].A * Slope[j].B == Slope[i].B * Slope[j].A){
            update(1, 1, n, pos[Slope[j].id1], A[Slope[j].id2].w);
            update(1, 1, n, pos[Slope[j].id2], A[Slope[j].id1].w);
            swap(pos[Slope[j].id1], pos[Slope[j].id2]);
            ++j;
        }
        i = j - 1;
        ans = max(ans, st[1].mx);
    }
    cout << ans << '\n';
}

signed main(void){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
//    cin >> t;
    while(t--) sol();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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