oj.uz

답안 #426609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426609 2021-06-14T07:49:21 Z 반딧불(#7615) Bodyguard (JOI21_bodyguard) C++17
6 / 100
 3189 ms 1558556 KB 
#include <bits/stdc++.h>
#define LIM 3000

using namespace std;

typedef long long ll;

int n, q;
int t[LIM], a[LIM], b[LIM]; ll c[LIM];

ll mat[LIM*4+10][LIM*2+10][2];
ll DP[LIM*4+10][LIM*2+10];

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d %lld", &t[i], &a[i], &b[i], &c[i]);
        a[i] *= 2, b[i] *= 2, t[i] *= 2, c[i] /= 2;

        if(a[i] < b[i]){
            for(int x=a[i], y=t[i]; x<b[i]; x++, y++){
                mat[y][x][1] = max(mat[y][x][1], c[i]);
            }
        }
        else{
            for(int x=a[i], y=t[i]; x>b[i]; x--, y++){
                mat[y][x][0] = max(mat[y][x][0], c[i]);
            }
        }
    }

    for(int t=LIM*4; t>=1; t--){
        for(int i=1; i<=LIM*2; i++){
            DP[t-1][i-1] = max(DP[t-1][i-1], DP[t][i] + mat[t-1][i-1][1]);
            DP[t-1][i] = max(DP[t-1][i], DP[t][i]);
            DP[t-1][i+1] = max(DP[t-1][i+1], DP[t][i] + mat[t-1][i+1][0]);
        }
    }

    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%lld\n", DP[x*2][y*2]);
    }
}

Compilation message

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bodyguard.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d %d %d %lld", &t[i], &a[i], &b[i], &c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3044 ms 1558556 KB Output is correct
2 Correct 3189 ms 1543496 KB Output is correct
3 Correct 2652 ms 724472 KB Output is correct
4 Correct 2583 ms 651060 KB Output is correct
5 Correct 2883 ms 975464 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3044 ms 1558556 KB Output is correct
2 Correct 3189 ms 1543496 KB Output is correct
3 Correct 2652 ms 724472 KB Output is correct
4 Correct 2583 ms 651060 KB Output is correct
5 Correct 2883 ms 975464 KB Output is correct
6 Runtime error 76 ms 332 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -