oj.uz

Submission #583308

# Submission time Handle Problem Language Result Execution time Memory
583308 2022-06-25T08:25:16 Z AriaH Bodyguard (JOI21_bodyguard) C++17
22 / 100
 849 ms 827884 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 = 1e18;

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 494 ms 507968 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 305 ms 303320 KB Output is correct
2 Correct 326 ms 302612 KB Output is correct
3 Correct 311 ms 306488 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 298 ms 240628 KB Output is correct
6 Correct 262 ms 209996 KB Output is correct
7 Correct 292 ms 240304 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 303320 KB Output is correct
2 Correct 326 ms 302612 KB Output is correct
3 Correct 311 ms 306488 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 298 ms 240628 KB Output is correct
6 Correct 262 ms 209996 KB Output is correct
7 Correct 292 ms 240304 KB Output is correct
8 Correct 849 ms 827884 KB Output is correct
9 Correct 782 ms 826088 KB Output is correct
10 Correct 677 ms 681224 KB Output is correct
11 Correct 56 ms 44468 KB Output is correct
12 Correct 545 ms 397324 KB Output is correct
13 Correct 676 ms 568316 KB Output is correct
14 Correct 672 ms 521264 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 303320 KB Output is correct
2 Correct 326 ms 302612 KB Output is correct
3 Correct 311 ms 306488 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 298 ms 240628 KB Output is correct
6 Correct 262 ms 209996 KB Output is correct
7 Correct 292 ms 240304 KB Output is correct
8 Correct 849 ms 827884 KB Output is correct
9 Correct 782 ms 826088 KB Output is correct
10 Correct 677 ms 681224 KB Output is correct
11 Correct 56 ms 44468 KB Output is correct
12 Correct 545 ms 397324 KB Output is correct
13 Correct 676 ms 568316 KB Output is correct
14 Correct 672 ms 521264 KB Output is correct
15 Runtime error 43 ms 2632 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 494 ms 507968 KB Output isn't correct
2 Halted 0 ms 0 KB -