oj.uz

Submission #583318

# Submission time Handle Problem Language Result Execution time Memory
583318 2022-06-25T08:33:24 Z AriaH Bodyguard (JOI21_bodyguard) C++17
22 / 100
 784 ms 827896 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int ll

const int N = 9e3 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 2e9;

int n, q, T[N], T2[N], fir[N], sec[N], Qa[N], Qb[N], C[N], dp[N][N], R[N][N], U[N][N];

vector < int > cmx, cmy;

void Add(int a, int b)
{
    cmx.push_back(a);
    cmy.push_back(b);
}

inline int lwrx(int a) { return lower_bound(all(cmx), a) - cmx.begin(); }

inline int lwry(int a) { return lower_bound(all(cmy), a) - cmy.begin(); }

signed main()
{
    fast_io;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++)
    {
        cin >> T[i] >> fir[i] >> sec[i] >> C[i];
        T2[i] = T[i] + abs(fir[i] - sec[i]);
        C[i] >>= 1;
        Add(T[i] + fir[i], T[i] - fir[i]);
        Add(T2[i] + sec[i], T2[i] - sec[i]);
    }
    for(int i = 1; i <= q; i ++)
    {
        cin >> Qa[i] >> Qb[i];
        Add(Qa[i] + Qb[i], Qa[i] - Qb[i]);
    }
    Add(inf, inf);
    sort(all(cmx));
    sort(all(cmy));
    cmx.resize(unique(all(cmx)) - cmx.begin());
    cmy.resize(unique(all(cmy)) - cmy.begin());
    int sz1 = SZ(cmx), sz2 = SZ(cmy);
    for(int i = 1; i <= n; i ++)
    {
        if(fir[i] < sec[i]) /// going up
        {
            int y = lwry(T[i] - fir[i]);
            int l = lwrx(T[i] + fir[i]), r = lwrx(T2[i] + sec[i]);
            for(int j = l; j < r; j ++)
            {
                U[j][y] = max(U[j][y], C[i]);
            }
        }
        else /// going right
        {
            int x = lwrx(T[i] + fir[i]);
            int l = lwry(T[i] - fir[i]), r = lwry(T2[i] - sec[i]);
            for(int j = l; j < r; j ++)
            {
                R[x][j] = max(R[x][j], C[i]);
            }
        }
    }
    for(int i = sz1 - 1; ~i; i --)
    {
        for(int j = sz2 - 1; ~j; j --)
        {
            if(i + 1 < sz1)
            {
                dp[i][j] = max(dp[i][j], dp[i + 1][j] + U[i][j] * (cmx[i + 1] - cmx[i]));
            }
            if(j + 1 < sz2)
            {
                dp[i][j] = max(dp[i][j], dp[i][j + 1] + R[i][j] * (cmy[j + 1] - cmy[j]));
            }
        }
    }
    for(int i = 1; i <= q; i ++)
    {
        cout << dp[lwrx(Qa[i] + Qb[i])][lwry(Qa[i] - Qb[i])] << endl;
    }
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 508 ms 507964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 303424 KB Output is correct
2 Correct 303 ms 302564 KB Output is correct
3 Correct 261 ms 306436 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 301 ms 240520 KB Output is correct
6 Correct 255 ms 210064 KB Output is correct
7 Correct 289 ms 240288 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 303424 KB Output is correct
2 Correct 303 ms 302564 KB Output is correct
3 Correct 261 ms 306436 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 301 ms 240520 KB Output is correct
6 Correct 255 ms 210064 KB Output is correct
7 Correct 289 ms 240288 KB Output is correct
8 Correct 784 ms 827896 KB Output is correct
9 Correct 769 ms 825948 KB Output is correct
10 Correct 694 ms 680976 KB Output is correct
11 Correct 66 ms 44280 KB Output is correct
12 Correct 532 ms 397248 KB Output is correct
13 Correct 715 ms 568372 KB Output is correct
14 Correct 714 ms 521192 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 303424 KB Output is correct
2 Correct 303 ms 302564 KB Output is correct
3 Correct 261 ms 306436 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 301 ms 240520 KB Output is correct
6 Correct 255 ms 210064 KB Output is correct
7 Correct 289 ms 240288 KB Output is correct
8 Correct 784 ms 827896 KB Output is correct
9 Correct 769 ms 825948 KB Output is correct
10 Correct 694 ms 680976 KB Output is correct
11 Correct 66 ms 44280 KB Output is correct
12 Correct 532 ms 397248 KB Output is correct
13 Correct 715 ms 568372 KB Output is correct
14 Correct 714 ms 521192 KB Output is correct
15 Runtime error 51 ms 1736 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 508 ms 507964 KB Output isn't correct
2 Halted 0 ms 0 KB -