oj.uz

Submission #386853

# Submission time Handle Problem Language Result Execution time Memory
386853 2021-04-07T13:39:54 Z keko37 Bodyguard (JOI21_bodyguard) C++14
42 / 100
 25000 ms 242596 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25058 ms 142348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 240492 KB Output is correct
2 Correct 283 ms 240208 KB Output is correct
3 Correct 283 ms 239084 KB Output is correct
4 Correct 26 ms 35052 KB Output is correct
5 Correct 284 ms 209260 KB Output is correct
6 Correct 237 ms 194028 KB Output is correct
7 Correct 282 ms 209260 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 240492 KB Output is correct
2 Correct 283 ms 240208 KB Output is correct
3 Correct 283 ms 239084 KB Output is correct
4 Correct 26 ms 35052 KB Output is correct
5 Correct 284 ms 209260 KB Output is correct
6 Correct 237 ms 194028 KB Output is correct
7 Correct 282 ms 209260 KB Output is correct
8 Correct 485 ms 240608 KB Output is correct
9 Correct 487 ms 240292 KB Output is correct
10 Correct 464 ms 238100 KB Output is correct
11 Correct 161 ms 35180 KB Output is correct
12 Correct 526 ms 209388 KB Output is correct
13 Correct 507 ms 194156 KB Output is correct
14 Correct 283 ms 209388 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 240492 KB Output is correct
2 Correct 283 ms 240208 KB Output is correct
3 Correct 283 ms 239084 KB Output is correct
4 Correct 26 ms 35052 KB Output is correct
5 Correct 284 ms 209260 KB Output is correct
6 Correct 237 ms 194028 KB Output is correct
7 Correct 282 ms 209260 KB Output is correct
8 Correct 485 ms 240608 KB Output is correct
9 Correct 487 ms 240292 KB Output is correct
10 Correct 464 ms 238100 KB Output is correct
11 Correct 161 ms 35180 KB Output is correct
12 Correct 526 ms 209388 KB Output is correct
13 Correct 507 ms 194156 KB Output is correct
14 Correct 283 ms 209388 KB Output is correct
15 Correct 3071 ms 242596 KB Output is correct
16 Correct 3134 ms 242284 KB Output is correct
17 Correct 2654 ms 240096 KB Output is correct
18 Correct 1314 ms 36232 KB Output is correct
19 Correct 3473 ms 210468 KB Output is correct
20 Correct 3805 ms 195356 KB Output is correct
21 Correct 294 ms 210284 KB Output is correct

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25058 ms 142348 KB Time limit exceeded
2 Halted 0 ms 0 KB -