oj.uz

답안 #149962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149962 2019-09-01T07:28:34 Z rkm0959(#3623, jun6873, babo) 최적의 팀 구성 (FXCUP4_squad) C++17
0 / 100
 422 ms 14388 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

using lint = long long;

struct Data {
    Data() {}
    Data(lint x, lint y, lint i) : x(x), y(y), i(i) {}

    lint x, y, i;
    lint f(lint a, lint b) { return a*x + b*y; }
    bool operator<(const Data b) const { return x < b.x or (x == b.x and y > b.y); }
};

int ccw(Data a, Data b, Data c) {
    lint k = a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;
    if (k>0) return 1;
    if (k<0) return -1;
    return 0;
}

struct cht {
    vector<Data> v;
    void add(Data p) {
        while (v.size() >= 2 and ccw(v[v.size()-2], v[v.size()-1], p) >= 0) v.pop_back();
        v.push_back(p);
    }

    Data find(lint a, lint b) {
        int l = -1, r = v.size()-1;
        while (l+1<r) {
            int m = (l+r) / 2;
            if (b * (v[m+1].y - v[m].y) >= - a * (v[m+1].x - v[m].x)) l = m;
            else r = m;
        }
        return v[r];
    }

    lint second(lint a, lint b) {
        int l = -1, r = v.size()-1;
        while (l+1<r) {
            int m = (l+r) / 2;
            if (b * (v[m+1].y - v[m].y) >= - a * (v[m+1].x - v[m].x)) l = m;
            else r = m;
        }
        lint ans = -1e18;
        if (r > 0) ans = max(ans, v[r-1].f(a, b));
        if (r < v.size()-1) ans = max(ans, v[r+1].f(a, b));
        return ans;
    }
} a1, a2, d1, d2;

int n;
struct human {
    int a, d, p, i;
} a[300004];

void Init(vector<int> A, vector<int> D, vector<int> P){
    n = A.size();
    for (int i=0; i<n; i++) a[i] = (human) { A[i], D[i], P[i], i };

    sort(a, a+n, [](human x, human y) { return x.a < y.a or (x.a == y.a and x.p > y.p); });
    
    for (int i=0; i<n; i++) a1.add(Data(a[i].a, a[i].p, a[i].i));
    for (int i=0; i<n; i++) if (!binary_search(a1.v.begin(), a1.v.end(), Data(a[i].a, a[i].p, a[i].i))) a2.add(Data(a[i].a, a[i].p, a[i].i));
    
    sort(a, a+n, [](human x, human y) { return x.d < y.d or (x.d == y.d and x.p > y.p); });
    
    for (int i=0; i<n; i++) d1.add(Data(a[i].d, a[i].p, a[i].i));
    for (int i=0; i<n; i++) if (!binary_search(d1.v.begin(), d1.v.end(), Data(a[i].d, a[i].p, a[i].i))) d2.add(Data(a[i].d, a[i].p, a[i].i));
}

long long BestSquad(int X, int Y){
    Data a = a1.find(X, Y), d = d1.find(X, Y);
    if (a.i != d.i) {
        return a.f(X, Y) + d.f(X, Y);
    } else {
        lint aa = max(a1.second(X, Y), a2.find(X, Y).f(X, Y)), dd = max(d1.second(X, Y), d2.find(X, Y).f(X, Y));
        return max(a.f(X, Y) + dd, d.f(X, Y) + aa);
    }
}

Compilation message

squad.cpp: In member function 'lint cht::second(lint, lint)':
squad.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (r < v.size()-1) ans = max(ans, v[r+1].f(a, b));
             ~~^~~~~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 274 ms 12152 KB Output is correct
4 Correct 278 ms 12152 KB Output is correct
5 Runtime error 22 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 9 ms 512 KB Output is correct
3 Correct 422 ms 14260 KB Output is correct
4 Correct 418 ms 14388 KB Output is correct
5 Runtime error 19 ms 1404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 274 ms 12152 KB Output is correct
4 Correct 278 ms 12152 KB Output is correct
5 Runtime error 22 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -