Submission #953189

#	Time	Username	Problem	Language	Result	Execution time	Memory
953189		groshi	Bodyguard (JOI21_bodyguard)	C++17	6 / 100	1150 ms	556200 KiB

bodyguard

#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 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52