oj.uz

Submission #595762

# Submission time Handle Problem Language Result Execution time Memory
595762 2022-07-14T06:13:04 Z 반딧불(#8442) Bodyguard (JOI21_bodyguard) C++17
28 / 100
 2713 ms 827776 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, W, H;
ll sx[3002], sy[3002], ex[3002], ey[3002], w[3002];
ll qx[3000002], qy[3000002];
ll wx[9004][9004], wy[9004][9004]; /// x�� �ٲ� / y�� �ٲ�
ll dist[9004][9004];
vector<ll> xVec, yVec;

void input();
void operate();
void output();

int main(){
    input();
    operate();
    output();
}

void input(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        ll pt, pa, pb, pc, pl;
        scanf("%lld %lld %lld %lld", &pt, &pa, &pb, &pc);
        pt*=2, pa*=2, pb*=2, pc/=2;
        pl = pt+abs(pa-pb);
        sx[i] = (pt+pa)/2, sy[i] = (pt-pa)/2;
        ex[i] = (pl+pb)/2, ey[i] = (pl-pb)/2;
        w[i] = pc;
    }
    for(int i=1; i<=q; i++){
        ll pt, px;
        scanf("%lld %lld", &pt, &px);
        pt*=2, px*=2;
        qx[i] = (pt+px)/2, qy[i] = (pt-px)/2;
    }
}

void renumber(){
    xVec = yVec = vector<ll> (1, LLONG_MIN);
    for(int i=1; i<=n; i++){
        xVec.push_back(sx[i]), xVec.push_back(ex[i]);
        yVec.push_back(sy[i]), yVec.push_back(ey[i]);
    }
    for(int i=1; i<=q; i++){
        xVec.push_back(qx[i]);
        yVec.push_back(qy[i]);
    }
    sort(xVec.begin(), xVec.end()); xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
    sort(yVec.begin(), yVec.end()); yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end());
    for(int i=1; i<=n; i++){
        sx[i] = lower_bound(xVec.begin(), xVec.end(), sx[i]) - xVec.begin();
        sy[i] = lower_bound(yVec.begin(), yVec.end(), sy[i]) - yVec.begin();
        ex[i] = lower_bound(xVec.begin(), xVec.end(), ex[i]) - xVec.begin();
        ey[i] = lower_bound(yVec.begin(), yVec.end(), ey[i]) - yVec.begin();
//        printf("arr[i]: %lld %lld %lld %lld %lld\n", sx[i], sy[i], ex[i], ey[i], w[i]);
    }
    for(int i=1; i<=q; i++){
        qx[i] = lower_bound(xVec.begin(), xVec.end(), qx[i]) - xVec.begin();
        qy[i] = lower_bound(yVec.begin(), yVec.end(), qy[i]) - yVec.begin();
//        printf("query[i]: %lld %lld\n", qx[i], qy[i]);
    }
    W = (int)xVec.size(), H = (int)yVec.size();
}

void makeEdges(){
    for(int i=1; i<=n; i++){
        if(sx[i] == ex[i]){
            for(int y=sy[i]+1; y<=ey[i]; y++)
                wy[sx[i]][y] = max(wy[sx[i]][y], w[i] * (yVec[y] - yVec[y-1]));
        }
        else{
            for(int x=sx[i]+1; x<=ex[i]; x++)
                wx[x][sy[i]] = max(wx[x][sy[i]], w[i] * (xVec[x] - xVec[x-1]));
        }
    }
}

void findDist(){
    for(int x=W; x>0; x--){
        for(int y=H; y>0; y--){
//            printf("Dist %d %d: %lld\n", x, y, dist[x][y]);
            dist[x-1][y] = max(dist[x-1][y], dist[x][y] + wx[x][y]);
            dist[x][y-1] = max(dist[x][y-1], dist[x][y] + wy[x][y]);
        }
    }
}

void operate(){
    renumber();
    makeEdges();
    findDist();
}

void output(){
    for(int i=1; i<=q; i++){
        printf("%lld\n", dist[qx[i]][qy[i]]);
    }
}

Compilation message

bodyguard.cpp: In function 'void input()':
bodyguard.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bodyguard.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%lld %lld %lld %lld", &pt, &pa, &pb, &pc);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%lld %lld", &pt, &px);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2713 ms 681312 KB Output is correct
2 Correct 2636 ms 686064 KB Output is correct
3 Correct 2435 ms 504292 KB Output is correct
4 Correct 2444 ms 437656 KB Output is correct
5 Correct 2542 ms 659396 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 303548 KB Output is correct
2 Correct 289 ms 302680 KB Output is correct
3 Correct 268 ms 306792 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 323 ms 240772 KB Output is correct
6 Correct 240 ms 210084 KB Output is correct
7 Correct 280 ms 240368 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 303548 KB Output is correct
2 Correct 289 ms 302680 KB Output is correct
3 Correct 268 ms 306792 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 323 ms 240772 KB Output is correct
6 Correct 240 ms 210084 KB Output is correct
7 Correct 280 ms 240368 KB Output is correct
8 Correct 824 ms 827776 KB Output is correct
9 Correct 862 ms 826060 KB Output is correct
10 Correct 652 ms 681268 KB Output is correct
11 Correct 55 ms 44420 KB Output is correct
12 Correct 529 ms 397228 KB Output is correct
13 Correct 651 ms 568424 KB Output is correct
14 Correct 630 ms 521388 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 303548 KB Output is correct
2 Correct 289 ms 302680 KB Output is correct
3 Correct 268 ms 306792 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 323 ms 240772 KB Output is correct
6 Correct 240 ms 210084 KB Output is correct
7 Correct 280 ms 240368 KB Output is correct
8 Correct 824 ms 827776 KB Output is correct
9 Correct 862 ms 826060 KB Output is correct
10 Correct 652 ms 681268 KB Output is correct
11 Correct 55 ms 44420 KB Output is correct
12 Correct 529 ms 397228 KB Output is correct
13 Correct 651 ms 568424 KB Output is correct
14 Correct 630 ms 521388 KB Output is correct
15 Runtime error 69 ms 2888 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2713 ms 681312 KB Output is correct
2 Correct 2636 ms 686064 KB Output is correct
3 Correct 2435 ms 504292 KB Output is correct
4 Correct 2444 ms 437656 KB Output is correct
5 Correct 2542 ms 659396 KB Output is correct
6 Correct 299 ms 303548 KB Output is correct
7 Correct 289 ms 302680 KB Output is correct
8 Correct 268 ms 306792 KB Output is correct
9 Correct 3 ms 872 KB Output is correct
10 Correct 323 ms 240772 KB Output is correct
11 Correct 240 ms 210084 KB Output is correct
12 Correct 280 ms 240368 KB Output is correct
13 Correct 824 ms 827776 KB Output is correct
14 Correct 862 ms 826060 KB Output is correct
15 Correct 652 ms 681268 KB Output is correct
16 Correct 55 ms 44420 KB Output is correct
17 Correct 529 ms 397228 KB Output is correct
18 Correct 651 ms 568424 KB Output is correct
19 Correct 630 ms 521388 KB Output is correct
20 Runtime error 69 ms 2888 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -