80pts WA #5 #10 求调
  • 板块P1493 分梨子
  • 楼主zhanglh
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/23 12:23
  • 上次更新2024/11/23 15:11:47
查看原帖
80pts WA #5 #10 求调
726862
zhanglh楼主2024/11/23 12:23

O(n2logn)O(n^2 \log n) 做法,WA on #5 #10,80pts。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll c1, c2, c3;
struct Pear {
    ll a, b;
    bool operator <(const Pear &W)const {
        return c1 * a + c2 * b < c1 * W.a + c2 * W.b;
    }
}p[2010], pp[2010];

bool cmpA(const Pear &A, const Pear &B) { return A.a < B.a; }
bool cmpB(const Pear &A, const Pear &B) { return A.b > B.b; }

bool check(ll ai, ll a0, ll bi, ll b0) {
    return c1 * (ai - a0) + c2 * (bi - b0) <= c3;
}

int main() {
    scanf("%d%lld%lld%lld", &n, &c1, &c2, &c3);
    for (int i = 1; i <= n; i++) {
        ll j, k;
        scanf("%lld%lld", &j, &k);
        p[i] = {j, k};
    }
    sort(p + 1, p + n + 1, cmpA);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) pp[j] = p[j];
        sort(pp + i + 1, pp + n + 1, cmpB);
        priority_queue<Pear, vector<Pear>, less<Pear> > q;
        for (int j = i + 1; j <= n; j++) {
        	ll t = min(pp[j].b, p[i].b);
            if (!check(pp[j].a, p[i].a, pp[j].b, t)) continue;
            q.push({pp[j].a, pp[j].b});
            while(q.size() && !check(q.top().a, p[i].a, q.top().b, t)) q.pop();
            ll cnt = q.size() + 1;
            ans = max(ans, cnt);
        }
    }
    printf("%lld\n", ans);
    return 0;
}
2024/11/23 12:23
加载中...