oj.uz

Submission #596029

# Submission time Handle Problem Language Result Execution time Memory
596029 2022-07-14T09:23:00 Z 이동현(#8445) Bodyguard (JOI21_bodyguard) C++17
6 / 100
 4446 ms 1553620 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

int sum[6004][12004][2];
int dp[6004][12004];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q; cin >> n >> q;
    for(int i = 0; i < n; ++i){
        int t, a, b, c; cin >> t >> a >> b >> c;
        t *= 2;
        c /= 2;
        a *= 2, b *= 2;
        int pos = a, now = t;
        while(pos != b){
            if(a < b){
                sum[pos][now][1] = max(sum[pos][now][1], c);
                ++pos; ++now;
            }
            else{
                sum[pos][now][0] = max(sum[pos][now][0], c);
                --pos; ++now;
            }
        }
    }
    for(int j = 12002; j >= 0; --j){
        for(int i = 0; i < 6004; ++i){
            dp[i][j] = dp[i][j + 1];
            if(i + 1 < 6004) dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + sum[i][j][1]);
            if(i) dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] + sum[i][j][0]);
        }
    }
    while(q--){
        int x, t; cin >> t >> x; x *= 2; t *= 2;
        cout << dp[x][t] << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4446 ms 1553620 KB Output is correct
2 Correct 4022 ms 1543344 KB Output is correct
3 Correct 3471 ms 730388 KB Output is correct
4 Correct 3497 ms 656204 KB Output is correct
5 Correct 3839 ms 991064 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 340 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 22 ms 340 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 22 ms 340 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 4446 ms 1553620 KB Output is correct
2 Correct 4022 ms 1543344 KB Output is correct
3 Correct 3471 ms 730388 KB Output is correct
4 Correct 3497 ms 656204 KB Output is correct
5 Correct 3839 ms 991064 KB Output is correct
6 Runtime error 22 ms 340 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -