Submission #401450

#	Time	Username	Problem	Language	Result	Execution time	Memory
401450		doowey	Bodyguard (JOI21_bodyguard)	C++14	42 / 100	25056 ms	307844 KiB

bodyguard

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 2810;
const int M = N * 2;
ll X[N], Y[N];
ll XX[N], YY[N];
ll val[N];
vector<ll> xc, yc;
ll XI[M][M];
ll YI[M][M];
ll dp[M][M];


int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, q;
    cin >> n >> q;
    ll start, en, tim;

    for(int i = 1; i <= n; i ++ ){
        cin >> tim >> start >> en >> val[i];
        start *= 2ll;
        tim *= 2ll;
        en *= 2ll;
        X[i] = tim + start;
        Y[i] = tim - start;
        tim += abs(en - start);
        XX[i] = tim + en;
        YY[i] = tim - en;
        xc.push_back(X[i]);
        yc.push_back(Y[i]);
        xc.push_back(XX[i]);
        yc.push_back(YY[i]);
    }
    sort(xc.begin(), xc.end());
    sort(yc.begin(), yc.end());
    xc.resize(unique(xc.begin(), xc.end()) - xc.begin());
    yc.resize(unique(yc.begin(), yc.end()) - yc.begin());
    int nn = xc.size();
    int mm = yc.size();
    int iq;
    for(int i = 1; i <= n; i ++ ){
        X[i] = lower_bound(xc.begin(), xc.end(), X[i]) - xc.begin();
        Y[i] = lower_bound(yc.begin(), yc.end(), Y[i]) - yc.begin();
        XX[i]= lower_bound(xc.begin(), xc.end(), XX[i]) - xc.begin();
        YY[i] = lower_bound(yc.begin(), yc.end(), YY[i]) - yc.begin();
        if(X[i] == XX[i]){
            for(int j = Y[i] + 1; j <= YY[i]; j ++ ){
                YI[X[i]][j] = max(YI[X[i]][j], val[i]);
            }
        }
        else{
            for(int j = X[i] + 1; j <= XX[i]; j ++ ){
                XI[j][Y[i]] = max(XI[j][Y[i]], val[i]);
            }
        }
    }
    for(int x = nn - 1; x >= 0 ; x -- ){
        for(int y = mm - 1; y >= 0; y -- ){
            if(x + 1 < nn)
                dp[x][y] = max(dp[x][y], dp[x + 1][y] + (xc[x + 1] - xc[x]) * 1ll * XI[x + 1][y]);
            if(y + 1 < mm)
                dp[x][y] = max(dp[x][y], dp[x][y + 1] + (yc[y + 1] - yc[y]) * 1ll * YI[x][y + 1]);
        }
    }
    ll xa, ya;
    int xlow, ylow;
    ll big;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> tim >> start;
        tim *= 2ll;
        start *= 2ll;
        xa = tim + start;
        ya = tim - start;
        xlow = lower_bound(xc.begin(), xc.end(), xa) - xc.begin();
        ylow = lower_bound(yc.begin(), yc.end(), ya) - yc.begin();
        if(xlow == nn || ylow == mm){
            cout << "0\n";
            continue;
        }
        big = 0;
        for(int j = xlow; j < nn; j ++ ){
            big = max(big, dp[j][ylow] + (yc[ylow] - ya) * 1ll * YI[j][ylow]);
        }
        for(int j = ylow; j < mm ; j ++ ){
            big = max(big, dp[xlow][j] + (xc[xlow] - xa) * 1ll * XI[xlow][j]);
        }
        cout << big/4ll << "\n";
    }
    return 0;
}

Compilation message (stderr)

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:52:9: warning: unused variable 'iq' [-Wunused-variable]
   52 |     int iq;
      |         ^~

• Subtask 1: 0 / 5
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 53