제출 #93197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93197		Alexa2001	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	768 ms	33612 KiB

bulldozer

#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

const int Nmax = 2005;
typedef long long ll;

ll ans = 0;
int n, i, j, where[Nmax], ord[Nmax];


class SegTree
{
    ll best[Nmax<<2], pref[Nmax<<2], suff[Nmax<<2], s[Nmax<<2];
public:
    void update(int node, int st, int dr, int pos, int val)
    {
        if(st== dr)
        {
            best[node] = pref[node] = suff[node] = max(0, val);
            s[node] = val;
            return;
        }

        if(pos <= mid) update(left_son, st, mid, pos, val);
            else update(right_son, mid+1, dr, pos, val);

        s[node] = s[left_son] + s[right_son];
        pref[node] = max(pref[left_son], s[left_son] + pref[right_son]);
        suff[node] = max(suff[right_son], s[right_son] + suff[left_son]);

        best[node] = max(best[left_son], best[right_son]);
        best[node] = max(best[node], suff[left_son] + pref[right_son]);
    }

    ll query()
    {
        return best[1];
    }
} aint;


struct point
{
    int x, y, p;
    bool operator < (const point &other) const
    {
        if(x == other.x) return y > other.y;
        return x > other.x;
    }
};
point a[Nmax];

struct intr
{
    int x, y, id1, id2;
    bool operator < (const intr &other) const
    {
        if((ll) x * other.y == (ll) y * other.x) return (make_pair(id1, id2) < make_pair(other.id1, other.id2));
        return (ll) x * other.y < (ll) y * other.x;
    }

    bool operator == (const intr &other) const
    {
        return (ll) x * other.y == (ll) y * other.x;
    }
};
vector<intr> intersect;

void apply(intr A)
{
    int p1 = where[A.id1], p2 = where[A.id2];
    assert(p1 + 1 == p2);

    aint.update(1, 1, n, p2, a[A.id1].p);
    aint.update(1, 1, n, p1, a[A.id2].p);

    swap(where[A.id1], where[A.id2]);
    swap(ord[p1], ord[p2]);
}

ll eval()
{
    return aint.query();
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i) cin >> a[i].x >> a[i].y >> a[i].p;

    sort(a+1, a+n+1);

    for(i=1; i<=n; ++i) ord[i] = i, where[i] = i;

    for(i=1; i<=n; ++i) aint.update(1, 1, n, i, a[i].p);
    ans = eval();

    for(i=1; i<=n; ++i)
        for(j=i+1; j<=n; ++j)
            if(a[i].x != a[j].x)
                intersect.push_back({a[i].y - a[j].y, a[i].x - a[j].x, i, j});
    sort(intersect.begin(), intersect.end());

    for(i=0; i<intersect.size(); ++i)
    {
        j = i;
        while(j<intersect.size() && intersect[i] == intersect[j])
            apply(intersect[j++]);
        i = j - 1;

        ans = max(ans, eval());
    }

    cout << ans << '\n';
    return 0;
}

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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:111:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<intersect.size(); ++i)
              ~^~~~~~~~~~~~~~~~~
bulldozer.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j<intersect.size() && intersect[i] == intersect[j])
               ~^~~~~~~~~~~~~~~~~

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