oj.uz

Submission #1118171

# Submission time Handle Problem Language Result Execution time Memory
1118171 2024-11-25T04:49:37 Z pemguimn Bodyguard (JOI21_bodyguard) C++14
6 / 100
 1070 ms 454728 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 454728 KB Output is correct
2 Correct 1070 ms 452608 KB Output is correct
3 Correct 927 ms 271924 KB Output is correct
4 Correct 838 ms 242288 KB Output is correct
5 Correct 682 ms 307236 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 9040 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 28 ms 9040 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 28 ms 9040 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 1060 ms 454728 KB Output is correct
2 Correct 1070 ms 452608 KB Output is correct
3 Correct 927 ms 271924 KB Output is correct
4 Correct 838 ms 242288 KB Output is correct
5 Correct 682 ms 307236 KB Output is correct
6 Runtime error 28 ms 9040 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -