oj.uz

Submission #595740

# Submission time Handle Problem Language Result Execution time Memory
595740 2022-07-14T05:18:15 Z 반딧불(#8442) Bodyguard (JOI21_bodyguard) C++17
6 / 100
 1390 ms 539856 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    ll x, d, w;
    dat(){}
    dat(ll x, ll d, ll w): x(x), d(d), w(w){}
};

int n, q;
ll pt[3002], pa[3002], pb[3002], pc[3002];
ll qt[3000002], qx[3000002];
ll maxScore[2][6002];
vector<dat> edges[12002];
vector<int> queryList[12002];
ll ans[3000002];

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld %lld", &pt[i], &pa[i], &pb[i], &pc[i]);
        pt[i] *= 2, pa[i] *= 2, pb[i] *= 2, pc[i] /= 2;
        int sign = (pa[i] > pb[i]) ? 1 : -1;
        for(int j=abs(pb[i]-pa[i]); j>0; j--){
            edges[pt[i]+j].push_back(dat(pa[i]-sign*j, sign, pc[i]));
        }
    }
    for(int i=1; i<=q; i++){
        scanf("%lld %lld", &qt[i], &qx[i]);
        qt[i]*=2, qx[i]*=2;
        queryList[qt[i]].push_back(i);
    }
    for(int t=12000; t>0; t--){
        int b=t%2;
        for(int p: queryList[t]) ans[p] = maxScore[b][qx[p]];
        for(int i=1; i<=6000; i++) maxScore[!b][i] = max({maxScore[b][i-1], maxScore[b][i], maxScore[b][i+1]});
        for(dat p: edges[t]) maxScore[!b][p.x+p.d] = max(maxScore[!b][p.x+p.d], maxScore[b][p.x] + p.w);
    }
    for(int i=1; i<=q; i++){
        printf("%lld\n", ans[i]);
    }
}

Compilation message

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bodyguard.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%lld %lld %lld %lld", &pt[i], &pa[i], &pb[i], &pc[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%lld %lld", &qt[i], &qx[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 319820 KB Output is correct
2 Correct 1237 ms 321944 KB Output is correct
3 Correct 1101 ms 202788 KB Output is correct
4 Correct 1073 ms 157180 KB Output is correct
5 Correct 1390 ms 539856 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1620 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 3 ms 1620 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 3 ms 1620 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 1223 ms 319820 KB Output is correct
2 Correct 1237 ms 321944 KB Output is correct
3 Correct 1101 ms 202788 KB Output is correct
4 Correct 1073 ms 157180 KB Output is correct
5 Correct 1390 ms 539856 KB Output is correct
6 Runtime error 3 ms 1620 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -