oj.uz

Submission #1118152

# Submission time Handle Problem Language Result Execution time Memory
1118152 2024-11-25T04:38:14 Z pemguimn Bodyguard (JOI21_bodyguard) C++14
0 / 100
 1057 ms 451684 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2805, Q = 3e6;

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;
}
bool csub1(){
    for(int i = 1; i <= n; i++){
        if(t[i] > 3000) return false;
        if(a[i] > 3000) return false;
        if(b[i] > 3000) return false;
    }
    for(int i = 1; i <= n; i++){
        if(x[i] > 3000 || p[i] > 3000) return false;
    }
    return true;
}
namespace sub1{
    const int M = 3e3 + 1;
    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 < 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];
    }
    return sub1::solve(), 0;
    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1057 ms 451684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 9084 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 30 ms 9084 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 30 ms 9084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 1057 ms 451684 KB Output isn't correct
2 Halted 0 ms 0 KB -