oj.uz

Submission #595773

# Submission time Handle Problem Language Result Execution time Memory
595773 2022-07-14T06:24:52 Z 반딧불(#8442) Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 308928 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[6004][6004], wy[6004][6004]; /// x�� �ٲ� / y�� �ٲ�
ll dist[6004][6004];
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]);
    }
    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]);
    }
    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]);
        }
    }
}

ll ans[3000002];

void findAns(){
    for(int i=1; i<=q; i++){
        ll tx = lower_bound(xVec.begin(), xVec.end(), qx[i]) - xVec.begin();
        ll ty = lower_bound(yVec.begin(), yVec.end(), qy[i]) - yVec.begin();
        ans[i] = dist[tx][ty];
        for(int j=1; j<=n; j++){
            if(sx[j] != ex[j]){ /// x�� �����̴� ����
                if(sy[j] < ty || qx[i] < xVec[sx[j]] || qx[i] > xVec[ex[j]]) continue;
                ans[i] = max(ans[i], dist[tx][sy[j]] + w[j] * (xVec[tx] - qx[i]));
            }
            else{
                if(sx[j] < tx || qy[i] < yVec[sy[j]] || qy[i] > yVec[ey[j]]) continue;
                ans[i] = max(ans[i], dist[sx[j]][ty] + w[j] * (yVec[ty] - qy[i]));
            }
        }
    }
}

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

void output(){
    for(int i=1; i<=q; i++){
        printf("%lld\n", ans[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
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 302760 KB Output is correct
2 Correct 267 ms 302004 KB Output is correct
3 Correct 290 ms 306124 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 284 ms 240108 KB Output is correct
6 Correct 234 ms 209512 KB Output is correct
7 Correct 263 ms 239708 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 302760 KB Output is correct
2 Correct 267 ms 302004 KB Output is correct
3 Correct 290 ms 306124 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 284 ms 240108 KB Output is correct
6 Correct 234 ms 209512 KB Output is correct
7 Correct 263 ms 239708 KB Output is correct
8 Correct 388 ms 302444 KB Output is correct
9 Correct 397 ms 302244 KB Output is correct
10 Correct 423 ms 305084 KB Output is correct
11 Correct 35 ms 880 KB Output is correct
12 Correct 354 ms 240156 KB Output is correct
13 Correct 326 ms 209600 KB Output is correct
14 Correct 297 ms 240236 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 302760 KB Output is correct
2 Correct 267 ms 302004 KB Output is correct
3 Correct 290 ms 306124 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 284 ms 240108 KB Output is correct
6 Correct 234 ms 209512 KB Output is correct
7 Correct 263 ms 239708 KB Output is correct
8 Correct 388 ms 302444 KB Output is correct
9 Correct 397 ms 302244 KB Output is correct
10 Correct 423 ms 305084 KB Output is correct
11 Correct 35 ms 880 KB Output is correct
12 Correct 354 ms 240156 KB Output is correct
13 Correct 326 ms 209600 KB Output is correct
14 Correct 297 ms 240236 KB Output is correct
15 Correct 1695 ms 304212 KB Output is correct
16 Correct 1738 ms 305140 KB Output is correct
17 Correct 848 ms 308928 KB Output is correct
18 Correct 325 ms 2828 KB Output is correct
19 Correct 1043 ms 242116 KB Output is correct
20 Correct 1341 ms 211572 KB Output is correct
21 Correct 580 ms 242088 KB Output is correct

Subtask #5
0 / 52.0

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