oj.uz

Submission #426636

# Submission time Handle Problem Language Result Execution time Memory
426636 2021-06-14T08:25:13 Z 장태환(#7571) Bodyguard (JOI21_bodyguard) C++17
22 / 100
 858 ms 943564 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#define int long long
using namespace std;
int N,Q;
int T[3100],A[3100],B[3100],C[3100];
int P[3100],X[3100];
int dp[8400][8400];
int verc[8400][8400];
int horc[8400][8400];
vector<int>pl;
vector<int>ml;
signed  main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N>>Q;
    int i;
    for(i=0;i<N;i++)
    {
        cin >> T[i]>>A[i]>>B[i]>>C[i];
        if(A[i]>B[i])
        {
            ml.push_back(T[i]-A[i]);
            pl.push_back(T[i]+A[i]);
            ml.push_back(T[i]+A[i]-2*B[i]);
        }
        else
        {
            ml.push_back(T[i]-A[i]);
            pl.push_back(T[i]+A[i]);
            pl.push_back(T[i]+B[i]*2-A[i]);
        }
    }
    for(i=0;i<Q;i++)
    {
        cin >>P[i]>>X[i];
        ml.push_back(P[i]-X[i]);
        pl.push_back(P[i]+X[i]);
    }
    sort(ml.begin(),ml.end());
    sort(pl.begin(),pl.end());
    ml.erase(unique(ml.begin(),ml.end()),ml.end());
    pl.erase(unique(pl.begin(),pl.end()),pl.end());
    for(i=0;i<N;i++)
    {
        if(A[i]>B[i])
        {
            int s=lower_bound(ml.begin(),ml.end(),T[i]-A[i])-ml.begin();
            int c=lower_bound(pl.begin(),pl.end(),T[i]+A[i])-pl.begin();
            int e=lower_bound(ml.begin(),ml.end(),T[i]+A[i]-2*B[i])-ml.begin();
            int j;
            for(j=s;j<e;j++)
            {
                verc[j+1][c]+=C[i]*(ml[j+1]-ml[j])/2;
            }
        }
        else
        {
            int c=lower_bound(ml.begin(),ml.end(),T[i]-A[i])-ml.begin();
            int s=lower_bound(pl.begin(),pl.end(),T[i]+A[i])-pl.begin();
            int e=lower_bound(pl.begin(),pl.end(),T[i]-A[i]+2*B[i])-pl.begin();
            int j;
            for(j=s;j<e;j++)
            {
                horc[c][j+1]+=C[i]*(pl[j+1]-pl[j])/2;
            }
        }
    }
    memset(dp,-60,sizeof(dp));
    dp[ml.size()-1][pl.size()-1]=0;
    for(int i=ml.size()-1;i>=0;i--)
        {
        int j;
        for(j=pl.size()-1;j>=0;j--)
        {
                dp[i][j]=max(dp[i][j],dp[i+1][j]+verc[i+1][j]);
                dp[i][j]=max(dp[i][j],dp[i][j+1]+horc[i][j+1]);
            }        }


    for(i=0;i<Q;i++)
    {

        int s=lower_bound(ml.begin(),ml.end(),P[i]-X[i])-ml.begin();
        int e=lower_bound(pl.begin(),pl.end(),P[i]+X[i])-pl.begin();
        cout <<dp[s][e]<<'\n';
    }

}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 649 ms 744244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 699844 KB Output is correct
2 Correct 485 ms 699176 KB Output is correct
3 Correct 499 ms 696780 KB Output is correct
4 Correct 274 ms 575912 KB Output is correct
5 Correct 549 ms 637820 KB Output is correct
6 Correct 443 ms 606856 KB Output is correct
7 Correct 502 ms 637352 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 699844 KB Output is correct
2 Correct 485 ms 699176 KB Output is correct
3 Correct 499 ms 696780 KB Output is correct
4 Correct 274 ms 575912 KB Output is correct
5 Correct 549 ms 637820 KB Output is correct
6 Correct 443 ms 606856 KB Output is correct
7 Correct 502 ms 637352 KB Output is correct
8 Correct 850 ms 943564 KB Output is correct
9 Correct 858 ms 941256 KB Output is correct
10 Correct 840 ms 794484 KB Output is correct
11 Correct 300 ms 583568 KB Output is correct
12 Correct 639 ms 735956 KB Output is correct
13 Correct 800 ms 685632 KB Output is correct
14 Correct 737 ms 638640 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 699844 KB Output is correct
2 Correct 485 ms 699176 KB Output is correct
3 Correct 499 ms 696780 KB Output is correct
4 Correct 274 ms 575912 KB Output is correct
5 Correct 549 ms 637820 KB Output is correct
6 Correct 443 ms 606856 KB Output is correct
7 Correct 502 ms 637352 KB Output is correct
8 Correct 850 ms 943564 KB Output is correct
9 Correct 858 ms 941256 KB Output is correct
10 Correct 840 ms 794484 KB Output is correct
11 Correct 300 ms 583568 KB Output is correct
12 Correct 639 ms 735956 KB Output is correct
13 Correct 800 ms 685632 KB Output is correct
14 Correct 737 ms 638640 KB Output is correct
15 Runtime error 78 ms 1736 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 649 ms 744244 KB Output isn't correct
2 Halted 0 ms 0 KB -