Submission #386853

#	Time	Username	Problem	Language	Result	Execution time	Memory
386853		keko37	Bodyguard (JOI21_bodyguard)	C++14	42 / 100	25058 ms	242596 KiB

bodyguard

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 2805;

int n, q;
int cost[MAXN];
pi pa[MAXN], pb[MAXN];
int upp[MAXN*3][MAXN*3], rig[MAXN*3][MAXN*3];
llint dp[MAXN*3][MAXN*3];
vector <llint> vx, vy;

void precompute () {
    for (int i = 1; i <= n; i++) {
        vx.push_back(pa[i].first); vy.push_back(pa[i].second);
        vx.push_back(pb[i].first); vy.push_back(pb[i].second);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());

    for (int i = 1; i <= n; i++) {
        int ix = lower_bound(vx.begin(), vx.end(), pa[i].first) - vx.begin();
        int iy = lower_bound(vy.begin(), vy.end(), pa[i].second) - vy.begin();
        int jx = lower_bound(vx.begin(), vx.end(), pb[i].first) - vx.begin();
        int jy = lower_bound(vy.begin(), vy.end(), pb[i].second) - vy.begin();
        if (iy == jy) {
            for (int k = ix; k < jx; k++) {
                rig[k][iy] = max(rig[k][iy], cost[i]);
            }
        } else {
            for (int k = iy; k < jy; k++) {
                upp[ix][k] = max(upp[ix][k], cost[i]);
            }
        }
    }

    for (int i = (int)vx.size() - 1; i >= 0; i--) {
        for (int j = (int) vy.size() - 1; j >= 0; j--) {
            llint res = 0;
            if (i + 1 < vx.size()) res = max(res, dp[i + 1][j] + rig[i][j] * (vx[i + 1] - vx[i]));
            if (j + 1 < vy.size()) res = max(res, dp[i][j + 1] + upp[i][j] * (vy[j + 1] - vy[j]));
            dp[i][j] = res;
        }
    }
}

llint upit (llint x, llint y) {
    //cout << "upit " << x << " " << y << endl;
    int i = lower_bound(vx.begin(), vx.end(), x) - vx.begin();
    int j = lower_bound(vy.begin(), vy.end(), y) - vy.begin();
    llint res = dp[i][j];
    if (j - 1 >= 0 && y != vy[j]) {
        for (int k = i; k < vx.size(); k++) {
            res = max(res, dp[k][j] + upp[k][j - 1] * (vy[j] - y));
        }
    }
    if (i - 1 >= 0 && x != vx[i]) {
        for (int k = j; k < vy.size(); k++) {
            res = max(res, dp[i][k] + rig[i - 1][k] * (vx[i] - x));
        }
    }
    return res;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int t, a, b;
        cin >> t >> a >> b >> cost[i];
        cost[i] /= 2;

        llint x = t, y = a;
        pa[i] = {x - y, x + y};
        x = t + abs(a - b), y = b;
        pb[i] = {x - y, x + y};

        //cout << "bla " << pa[i].first << " " << pa[i].second << "  " << pb[i].first << " " << pb[i].second << "  " << cost[i] << endl;
    }
    precompute();
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << upit(x - y, x + y) << '\n';
    }
    return 0;
}

Compilation message (stderr)

bodyguard.cpp: In function 'void precompute()':
bodyguard.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             if (i + 1 < vx.size()) res = max(res, dp[i + 1][j] + rig[i][j] * (vx[i + 1] - vx[i]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             if (j + 1 < vy.size()) res = max(res, dp[i][j + 1] + upp[i][j] * (vy[j + 1] - vy[j]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp: In function 'llint upit(llint, llint)':
bodyguard.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int k = i; k < vx.size(); k++) {
      |                         ~~^~~~~~~~~~~
bodyguard.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int k = j; k < vy.size(); k++) {
      |                         ~~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 53