Submission #1118158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118158		Pannda	Bodyguard (JOI21_bodyguard)	C++17	6 / 100	2045 ms	1472412 KiB

bodyguard

#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 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52