oj.uz

Submission #953189

# Submission time Handle Problem Language Result Execution time Memory
953189 2024-03-25T16:31:49 Z groshi Bodyguard (JOI21_bodyguard) C++17
6 / 100
 1150 ms 556200 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct dat{
    int x,d,w;
    dat(){}
    dat(int x,int d,int w):x(x),d(d),w(w){}
};
int n,q;
int pt[3002],pa[3002],pb[3002],pc[3002];
int qt[3000002], qx[3000002];
int dp[2][6002];
vector<dat> Q[12002];
vector<int> zap[12002];
int wynik[3000002];
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>pt[i]>>pa[i]>>pb[i]>>pc[i];
        pt[i]*=2,pa[i]*=2,pb[i]*=2,pc[i]/=2;
        int mam;
        if(pa[i]>pb[i])
            mam=1;
        else mam=-1;
        for(int j=abs(pb[i]-pa[i]);j>0;j--)
            Q[pt[i]+j].push_back(dat(pa[i]-mam*j,mam,pc[i]));
    }
    for(int i=1; i<=q; i++)
    {
        cin>>qt[i]>>qx[i];
        qt[i]*=2,qx[i]*=2;
        zap[qt[i]].push_back(i);
    }
    for(int t=12000;t>0;t--)
    {
        int b=t%2;
        for(int p:zap[t])
            wynik[p]=dp[b][qx[p]];
        for(int i=1;i<=6000;i++)
            dp[!b][i]=max({dp[b][i-1],dp[b][i],dp[b][i+1]});
        for(dat p:Q[t])
            dp[!b][p.x+p.d]=max(dp[!b][p.x+p.d],dp[b][p.x]+p.w);
    }
    for(int i=1;i<=q;i++)
        cout<<wynik[i]<<"\n";
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 335700 KB Output is correct
2 Correct 922 ms 337276 KB Output is correct
3 Correct 768 ms 217984 KB Output is correct
4 Correct 705 ms 172388 KB Output is correct
5 Correct 1150 ms 556200 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4700 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 4 ms 4700 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 4 ms 4700 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 961 ms 335700 KB Output is correct
2 Correct 922 ms 337276 KB Output is correct
3 Correct 768 ms 217984 KB Output is correct
4 Correct 705 ms 172388 KB Output is correct
5 Correct 1150 ms 556200 KB Output is correct
6 Runtime error 4 ms 4700 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -