oj.uz

Submission #583329

# Submission time Handle Problem Language Result Execution time Memory
583329 2022-06-25T08:44:41 Z AriaH Bodyguard (JOI21_bodyguard) C++17
28 / 100
 2617 ms 827936 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 M = 3e3 + 10;
const int N = 9e3 + 10;
const int N2 = 3e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 4e9;

int n, q, T[M], T2[M], fir[M], sec[M], Qa[N2], Qb[N2], C[M], 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] /= 2;
        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());
    assert(SZ(cmx) < N);
    assert(SZ(cmy) < N);
    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2461 ms 681428 KB Output is correct
2 Correct 2464 ms 687020 KB Output is correct
3 Correct 2337 ms 504876 KB Output is correct
4 Correct 2414 ms 438412 KB Output is correct
5 Correct 2617 ms 659716 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 303396 KB Output is correct
2 Correct 290 ms 302552 KB Output is correct
3 Correct 272 ms 306424 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 280 ms 240620 KB Output is correct
6 Correct 283 ms 210116 KB Output is correct
7 Correct 272 ms 240184 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 303396 KB Output is correct
2 Correct 290 ms 302552 KB Output is correct
3 Correct 272 ms 306424 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 280 ms 240620 KB Output is correct
6 Correct 283 ms 210116 KB Output is correct
7 Correct 272 ms 240184 KB Output is correct
8 Correct 763 ms 827936 KB Output is correct
9 Correct 743 ms 826080 KB Output is correct
10 Correct 665 ms 681108 KB Output is correct
11 Correct 65 ms 44352 KB Output is correct
12 Correct 505 ms 397400 KB Output is correct
13 Correct 670 ms 568296 KB Output is correct
14 Correct 639 ms 521264 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 303396 KB Output is correct
2 Correct 290 ms 302552 KB Output is correct
3 Correct 272 ms 306424 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 280 ms 240620 KB Output is correct
6 Correct 283 ms 210116 KB Output is correct
7 Correct 272 ms 240184 KB Output is correct
8 Correct 763 ms 827936 KB Output is correct
9 Correct 743 ms 826080 KB Output is correct
10 Correct 665 ms 681108 KB Output is correct
11 Correct 65 ms 44352 KB Output is correct
12 Correct 505 ms 397400 KB Output is correct
13 Correct 670 ms 568296 KB Output is correct
14 Correct 639 ms 521264 KB Output is correct
15 Runtime error 46 ms 2332 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2461 ms 681428 KB Output is correct
2 Correct 2464 ms 687020 KB Output is correct
3 Correct 2337 ms 504876 KB Output is correct
4 Correct 2414 ms 438412 KB Output is correct
5 Correct 2617 ms 659716 KB Output is correct
6 Correct 298 ms 303396 KB Output is correct
7 Correct 290 ms 302552 KB Output is correct
8 Correct 272 ms 306424 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 280 ms 240620 KB Output is correct
11 Correct 283 ms 210116 KB Output is correct
12 Correct 272 ms 240184 KB Output is correct
13 Correct 763 ms 827936 KB Output is correct
14 Correct 743 ms 826080 KB Output is correct
15 Correct 665 ms 681108 KB Output is correct
16 Correct 65 ms 44352 KB Output is correct
17 Correct 505 ms 397400 KB Output is correct
18 Correct 670 ms 568296 KB Output is correct
19 Correct 639 ms 521264 KB Output is correct
20 Runtime error 46 ms 2332 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -