Submission #148720

#	Time	Username	Problem	Language	Result	Execution time	Memory
148720		mit한의대지망생 (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	100 / 100	937 ms	54568 KiB

squad

#include "squad.h"
#include <algorithm>
#include <vector>
#include <set>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

int ccw(pll a, pll b, pll c) {
    llong x1 = b.fs - a.fs, y1 = b.se - a.se;
    llong x2 = c.fs - b.fs, y2 = c.se - b.se;
    llong val = x1 * y2 - x2 * y1;
    if (val > 0) return 1;
    if (val < 0) return -1;
    return 0;
}

struct convex_hull {
    vector<pair<pll, int>> ps;
    void add(llong x, llong y, int i) {
        ps.emplace_back(pll(x, y), i);
    }
    void init() {
        sort(ps.begin(), ps.end());
        vector<pair<pll, int>> tp;
        for (auto i : ps) {
            while (!tp.empty() && tp.back().fs.se <= i.fs.se)
                tp.pop_back();
            tp.push_back(i);
        }
        ps.clear();
        for (auto i : tp) {
            int sz;
            while ((sz = ps.size()) > 1 && ccw(ps[sz - 2].fs, ps[sz - 1].fs, i.fs) >= 0)
                ps.pop_back();
            ps.push_back(i);
        }
    }
    vector<pair<pll, int>> get(llong x, llong y) {
        vector<pair<pll, int>> ret;
        int s = 0, e = (int)ps.size() - 1;
        while (s < e) {
            int m = (s + e) / 2;
            llong L = ps[m].fs.fs * x + ps[m].fs.se * y;
            llong R = ps[m + 1].fs.fs * x + ps[m + 1].fs.se * y;
            if (L < R) s = m + 1;
            else e = m;
        }
        for (int i = max(0, s - 1); i <= e + 1 && i < ps.size(); ++i) ret.push_back(ps[i]);
        return ret;
    }
} as1, as2, ds1, ds2;

int usedA[300000];
int usedD[300000];
void Init(vector<int> A, vector<int> D, vector<int> P) {
    int n = A.size();
    for (int i = 0; i < n; ++i) {
        as1.add(A[i], P[i], i);
        ds1.add(D[i], P[i], i);
    }
    as1.init();
    ds1.init();
    for (auto i : as1.ps) usedA[i.se] = 1;
    for (auto i : ds1.ps) usedD[i.se] = 1;
    for (int i = 0; i < n; ++i) {
        if (!usedA[i]) as2.add(A[i], P[i], i);
        if (!usedD[i]) ds2.add(D[i], P[i], i);
    }
    as2.init();
    ds2.init();
}

llong BestSquad(int x, int y) {
    auto a1 = as1.get(x, y);
    auto a2 = as2.get(x, y);
    for (auto i : a2) a1.push_back(i);
    auto d1 = ds1.get(x, y);
    auto d2 = ds2.get(x, y);
    for (auto i : d2) d1.push_back(i);
    llong ans = 0;
    for (auto i : a1) for (auto j : d1) {
        if (i.se == j.se) continue;
        llong A = i.fs.fs * x + i.fs.se * y;
        llong D = j.fs.fs * x + j.fs.se * y;
        ans = max(ans, A + D);
    }
    return ans;
}

Compilation message (stderr)

squad.cpp: In member function 'std::vector<std::pair<std::pair<long long int, long long int>, int> > convex_hull::get(llong, llong)':
squad.cpp:52:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = max(0, s - 1); i <= e + 1 && i < ps.size(); ++i) ret.push_back(ps[i]);
                                                   ~~^~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53