oj.uz

Submission #1118158

# Submission time Handle Problem Language Result Execution time Memory
1118158 2024-11-25T04:40:43 Z Pannda Bodyguard (JOI21_bodyguard) C++17
6 / 100
 2045 ms 1472412 KB 
#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 12001;
int n, q;
array<int, 4> a[maxn];
int dp[maxn][6002], up[maxn][6002], down[maxn][6002];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
        for (int j = 0; j < 3; j++)
            a[i][j] *= 2;
        a[i][3] /= 2;
        for (int j = a[i][1], timer = 0; j < a[i][2]; j++, timer++)
            up[a[i][0] + timer][j] = max(up[a[i][0] + timer][j], a[i][3]);
        for (int j = a[i][1], timer = 0; j > a[i][2]; j--, timer++)
            down[a[i][0] + timer][j] = max(down[a[i][0] + timer][j], a[i][3]);
    }
    memset(dp, -0x3f, sizeof dp);
    int oo = dp[0][0];
    memset(dp[maxn - 1], 0, sizeof dp[maxn - 1]);
    for (int i = maxn - 1; i >= 1; i--)
        for (int pos = 1; pos <= 6001; pos++) if (dp[i][pos] != oo)
        {
            dp[i - 1][pos] = max(dp[i - 1][pos], dp[i][pos]);
            if (pos > 1)
            {
                dp[i - 1][pos - 1] = max(dp[i - 1][pos - 1], dp[i][pos] + up[i - 1][pos - 1]);
            }
            if (pos < 6001)
            {
                dp[i - 1][pos + 1] = max(dp[i - 1][pos + 1], dp[i][pos] + down[i - 1][pos + 1]);
            }
        }
    while (q--)
    {
        int t, p; cin >> t >> p;
        cout << dp[t * 2][p * 2] << "\n";
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1809 ms 1465356 KB Output is correct
2 Correct 2045 ms 1472412 KB Output is correct
3 Correct 1195 ms 759604 KB Output is correct
4 Correct 1302 ms 683168 KB Output is correct
5 Correct 1365 ms 883460 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1809 ms 1465356 KB Output is correct
2 Correct 2045 ms 1472412 KB Output is correct
3 Correct 1195 ms 759604 KB Output is correct
4 Correct 1302 ms 683168 KB Output is correct
5 Correct 1365 ms 883460 KB Output is correct
6 Runtime error 77 ms 336 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -