oj.uz

Submission #401450

# Submission time Handle Problem Language Result Execution time Memory
401450 2021-05-10T09:34:40 Z doowey Bodyguard (JOI21_bodyguard) C++14
42 / 100
 25000 ms 307844 KB 
#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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25056 ms 168272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 302716 KB Output is correct
2 Correct 322 ms 301948 KB Output is correct
3 Correct 306 ms 305804 KB Output is correct
4 Correct 4 ms 728 KB Output is correct
5 Correct 336 ms 239668 KB Output is correct
6 Correct 271 ms 209040 KB Output is correct
7 Correct 316 ms 239572 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 302716 KB Output is correct
2 Correct 322 ms 301948 KB Output is correct
3 Correct 306 ms 305804 KB Output is correct
4 Correct 4 ms 728 KB Output is correct
5 Correct 336 ms 239668 KB Output is correct
6 Correct 271 ms 209040 KB Output is correct
7 Correct 316 ms 239572 KB Output is correct
8 Correct 509 ms 302400 KB Output is correct
9 Correct 516 ms 302112 KB Output is correct
10 Correct 334 ms 305040 KB Output is correct
11 Correct 13 ms 844 KB Output is correct
12 Correct 488 ms 239820 KB Output is correct
13 Correct 517 ms 209156 KB Output is correct
14 Correct 636 ms 240028 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 302716 KB Output is correct
2 Correct 322 ms 301948 KB Output is correct
3 Correct 306 ms 305804 KB Output is correct
4 Correct 4 ms 728 KB Output is correct
5 Correct 336 ms 239668 KB Output is correct
6 Correct 271 ms 209040 KB Output is correct
7 Correct 316 ms 239572 KB Output is correct
8 Correct 509 ms 302400 KB Output is correct
9 Correct 516 ms 302112 KB Output is correct
10 Correct 334 ms 305040 KB Output is correct
11 Correct 13 ms 844 KB Output is correct
12 Correct 488 ms 239820 KB Output is correct
13 Correct 517 ms 209156 KB Output is correct
14 Correct 636 ms 240028 KB Output is correct
15 Correct 2768 ms 303904 KB Output is correct
16 Correct 2715 ms 304004 KB Output is correct
17 Correct 646 ms 307844 KB Output is correct
18 Correct 35 ms 1732 KB Output is correct
19 Correct 2516 ms 241116 KB Output is correct
20 Correct 3588 ms 210448 KB Output is correct
21 Correct 4309 ms 240776 KB Output is correct

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25056 ms 168272 KB Time limit exceeded
2 Halted 0 ms 0 KB -