Submission #150344

#	Time	Username	Problem	Language	Result	Execution time	Memory
150344		Cafe Maru (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	6 ms	384 KiB

squad

#include "squad.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct Line {
    Line(ll a, ll b, ll idx) : a(a), b(b), idx(idx) {}
    long long a, b, idx;
    pair<ll,ll> y(pair<ll,ll> x) const { return {a * x.first + b * x.second, idx}; }
};

struct CHTLinear {
    vector<Line> stk;
    int qpt;
    CHTLinear() : qpt(0) { }
    // when you need maximum :  (previous l).a < (now l).a
    // when you need minimum :  (previous l).a > (now l).a
    void pushLine(const Line& l) {
        while (stk.size() > 1) {
            Line& l0 = stk[stk.size() - 1];
            Line& l1 = stk[stk.size() - 2];
            if ((l0.b - l.b) * (l0.a - l1.a) > (l1.b - l0.b) * (l.a - l0.a)) break;
            stk.pop_back();
        }
        stk.push_back(l);
    }
    // (previous x) <= (current x)
    // it calculates max/min at x
    pair<ll, ll> query(pair<ll,ll> x) {
        while (qpt + 1 < stk.size()) {
            Line& l0 = stk[qpt];
            Line& l1 = stk[qpt + 1];
            if (l1.a - l0.a > 0 && (l0.b - l1.b) * x.second > x.first * (l1.a - l0.a)) break;
            if (l1.a - l0.a < 0 && (l0.b - l1.b) * x.second < x.first * (l1.a - l0.a)) break;
            ++qpt;
        }
        return stk[qpt].y(x);
    }
};

CHTLinear cht;
pair<ll, ll> pr[2];

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	int N = A.size();
    for(int i=0;i<N;i++) {
        cht.pushLine(Line(P[i], A[i], i));
        if (P[i] > pr[0].first) {
            pr[1] = pr[0];
            pr[0] = {P[i], i};
        } else if (P[i] > pr[1].first) {
            pr[1] = {P[i], i};
        }
    }
}

long long BestSquad(int X, int Y) {
    auto ret = cht.query({Y,X});
    if(ret.second == pr[0].second) {
        return ret.first + X + Y*pr[1].first;
    }
    return ret.first + X + Y*pr[0].first;
}

Compilation message (stderr)

squad.cpp: In member function 'std::pair<long long int, long long int> CHTLinear::query(std::pair<long long int, long long int>)':
squad.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (qpt + 1 < stk.size()) {
                ~~~~~~~~^~~~~~~~~~~~

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