Submission #1118171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118171		pemguimn	Bodyguard (JOI21_bodyguard)	C++14	6 / 100	1070 ms	454728 KiB

bodyguard

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2805, Q = 3e6 + 5;

int n, q;

int t[N], a[N], b[N], c[N];
int p[Q], x[Q];

inline int sign(int x){
    if(x < 0) return -1;
    if(x == 0) return 0;
    return +1;
}

namespace sub1{
    const int M = 3e3 + 5;
    int f[2 * M][M], r[2 * M][M];
    int dp[2 * M][M];
    void solve(){
        for(int i = 1; i <= n; i++){
            int tim = t[i];

            if(a[i] < b[i]){
                for(int j = a[i]; j != b[i]; j++){
                    f[tim][j] = max(f[tim][j], c[i]);
                    tim++;
                }
            } else{
                for(int j = a[i]; j != b[i]; j--){
                    r[tim][j] = max(r[tim][j], c[i]);
                    tim++;
                }
            }
        }
        for(int i = 2 * M - 1; i >= 0; i--){
            for(int j = M - 1; j >= 0; j--){
                dp[i][j] = max(f[i][j], r[i][j]);
                if(i + 1 < 2 * M){
                    dp[i][j] = dp[i + 1][j];

                    if(j > 0){
                        dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + r[i][j]);
                        dp[i][j] = max(dp[i][j], dp[i + 1][j] + (r[i][j] + f[i][j - 1]) / 2);
                    }
                    if(j < M - 1){
                        dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + f[i][j]);
                        dp[i][j] = max(dp[i][j], dp[i + 1][j] + (f[i][j] + r[i][j + 1]) / 2);
                    }
                }
            }
        }
        for(int i = 1; i <= q; i++){
            cout << dp[p[i]][x[i]] << '\n';
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> t[i] >> a[i] >> b[i] >> c[i];
    }

    for(int i = 1; i <= q; i++){
        cin >> p[i] >> x[i];
    }

    sub1::solve();
    return 0;
}

/*
2 2
1 2 1 4
3 1 3 2
1 2
3 3

3 2
3 1 5 2
1 4 1 4
4 2 4 4
2 2
6 3
*/

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52