oj.uz

Submission #427793

# Submission time Handle Problem Language Result Execution time Memory
427793 2021-06-14T23:01:25 Z CodePlatina Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 1110576 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("in.txt", "r", stdin);

    int n, T; cin >> n >> T;
    tiiii A[n];
    for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;

    vector<long long> prX, prY;
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            prX.push_back(1ll * a + b);
            prX.push_back(1ll * a - b + 2 * c);
            prY.push_back(1ll * a - b);
        }
        else
        {
            prX.push_back(1ll * a + b);
            prY.push_back(1ll * a + b - 2 * c);
            prY.push_back(1ll * a - b);
        }
    }
    prX.push_back((long long)4e9+7);
    prY.push_back((long long)4e9+7);
    sort(prX.begin(), prX.end());
    sort(prY.begin(), prY.end());
    prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
    prY.resize(unique(prY.begin(), prY.end()) - prY.begin());

    int N = prX.size(), M = prY.size();
    int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{};
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin();
            int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
            for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2);
        }
        else
        {
            int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
            int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c) - prY.begin();
            for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2);
        }
    }

    long long dp[N + 1][M + 1]{};
    for(int i = N; i >= 0; --i)
    {
        for(int j = M; j >= 0; --j)
        {
            if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i]));
            if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j]));
        }
    }

//    for(int i = 0; i <= N; ++i)
//    {
//        for(int j = 0; j <= M; ++j)
//            cout << dp[i][j] << ' ';
//        cout << endl;
//    }

    vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1];
    for(int i = 0; i < T; ++i)
    {
        int x, y; cin >> x >> y;
        int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin();
        int yi = lower_bound(prY.begin(), prY.end(), x - y) - prY.begin();
        lsX[xi][yi].push_back({prX[xi] - x - y, i});
        lsY[xi][yi].push_back({prY[yi] - x + y, i});
    }

    long long ans[T]{};
    for(int i = 0; i <= N; ++i)
    {
        for(int j = 0; j <= M; ++j)
        {
            for(auto [x, q] : lsX[i][j])
                for(int k = j; k <= M; ++k) ans[q] = max(ans[q], dp[i][k] + 1ll * x * (i ? CX[i - 1][k] : 0));
            for(auto [x, q] : lsY[i][j])
                for(int k = i; k <= N; ++k) ans[q] = max(ans[q], dp[k][j] + 1ll * x * (j ? CY[k][j - 1] : 0));
        }
    }

    for(auto i : ans) cout << i << '\n';
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 1106212 KB Output is correct
2 Correct 943 ms 1106440 KB Output is correct
3 Correct 905 ms 1091104 KB Output is correct
4 Correct 3 ms 1356 KB Output is correct
5 Correct 984 ms 1106272 KB Output is correct
6 Correct 925 ms 1106212 KB Output is correct
7 Correct 978 ms 1104580 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 1106212 KB Output is correct
2 Correct 943 ms 1106440 KB Output is correct
3 Correct 905 ms 1091104 KB Output is correct
4 Correct 3 ms 1356 KB Output is correct
5 Correct 984 ms 1106272 KB Output is correct
6 Correct 925 ms 1106212 KB Output is correct
7 Correct 978 ms 1104580 KB Output is correct
8 Correct 1261 ms 1106528 KB Output is correct
9 Correct 1247 ms 1106552 KB Output is correct
10 Correct 928 ms 1089352 KB Output is correct
11 Correct 11 ms 1612 KB Output is correct
12 Correct 1173 ms 1106624 KB Output is correct
13 Correct 1221 ms 1106624 KB Output is correct
14 Correct 1165 ms 1106516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 1106212 KB Output is correct
2 Correct 943 ms 1106440 KB Output is correct
3 Correct 905 ms 1091104 KB Output is correct
4 Correct 3 ms 1356 KB Output is correct
5 Correct 984 ms 1106272 KB Output is correct
6 Correct 925 ms 1106212 KB Output is correct
7 Correct 978 ms 1104580 KB Output is correct
8 Correct 1261 ms 1106528 KB Output is correct
9 Correct 1247 ms 1106552 KB Output is correct
10 Correct 928 ms 1089352 KB Output is correct
11 Correct 11 ms 1612 KB Output is correct
12 Correct 1173 ms 1106624 KB Output is correct
13 Correct 1221 ms 1106624 KB Output is correct
14 Correct 1165 ms 1106516 KB Output is correct
15 Correct 4899 ms 1110576 KB Output is correct
16 Correct 4936 ms 1110560 KB Output is correct
17 Correct 1432 ms 1096092 KB Output is correct
18 Correct 82 ms 4528 KB Output is correct
19 Correct 3535 ms 1109632 KB Output is correct
20 Correct 4708 ms 1109464 KB Output is correct
21 Correct 3594 ms 1108928 KB Output is correct

Subtask #5
0 / 52.0

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