oj.uz

Submission #1118177

# Submission time Handle Problem Language Result Execution time Memory
1118177 2024-11-25T04:58:07 Z who Bodyguard (JOI21_bodyguard) C++17
6 / 100
 1775 ms 1094472 KB 
#include <bits/stdc++.h>

using namespace std;

#define task "motor"
#define etr "\n"
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pli pair<long long,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define bg begin
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define lwb lower_bound
#define upb upper_bound
#define range(x, l, r) x+l, x+1+r
#define all(x) (x).bg(), (x).end()
#define compact(x) x.resize(unique(all(x)) - (x).bg())
#define sq(x) ((x)*(x))

auto start = chrono::high_resolution_clock::now();

void start_timer()
{
    start = chrono::high_resolution_clock::now();
}

ld elapsed()
{
    auto current = chrono::high_resolution_clock::now();
    ld duration = chrono::duration_cast<chrono::nanoseconds>(current - start).count();
    return duration / 1e9;
}
void freop()
{
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}

template<class U, class V> istream& operator >> (istream& in, pair<U, V>& p)
{
    in >> p.fi >> p.se;
    return in;
}

template<class U, class V> ostream& operator << (ostream& out, pair<U, V> p)
{
    out << "{" << p.fi << ' ' << p.se << "}";
    return out;
}

template<class T> ostream& operator << (ostream& out, vector<T>& v)
{
    out << "{";
    for (int i=0; i<v.size(); i++)
    {
        out << v[i];
        if (i != v.size() - 1) out << ", ";
    }

    out << "}";
    return out;
}

const int N=2800, M=3e6, mod=1e9+7;

int n, q;
array<int, 4> a[M+5];
pii p[M+5];

namespace Sub1
{
    const int S = 6e3;

    bool check()
    {
        for (int i=1; i<=n; i++)
        {
            for (int j=0; j<3; j++)
            {
                if (a[i][j] > S) return false;
            }
        }

        for (int i=1; i<=q; i++)
        {
            if (p[i].fi > S || p[i].se > S) return false;
        }

        return true;
    }

    int f[S*2+5][S+5], b[S*2+5][S+5];
    ll dp[S*2+5][S+5];


    void solve()
    {
        for (int i=1; i<=n; i++)
        {
            if (a[i][1] <= a[i][2])
            {
                for (int j=0; j < a[i][2] - a[i][1]; j++)
                {
                    f[j + a[i][0]][a[i][1] + j] = max(f[j + a[i][0]][a[i][1] + j], a[i][3]);
                }
            } else
            {
                for (int j=0; j < a[i][1] - a[i][2]; j++)
                {
                    b[j + a[i][0]][a[i][1] - j] = max(b[j + a[i][0]][a[i][1] - j], a[i][3]);
                }
            }
        }

        //cout << f[6][6] << "!" << endl;

        for (int i=S*2; i>=1; i--)
        {
            for (int j=1; j<=S; j++)
            {
                dp[i][j] = max({dp[i+1][j], dp[i+1][j-1] + b[i][j], dp[i+1][j+1] + f[i][j]});
            }
        }

        for (int i=1; i<=q; i++)
        {
            cout << dp[p[i].fi][p[i].se] << etr;
        }
    }
}

void process()
{
    cin >> n >> q;
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<4; j++) cin >> a[i][j];
        a[i][3] >>= 1;
        a[i][0] <<= 1;
        a[i][1] <<= 1;
        a[i][2] <<= 1;
    }

    for (int i=1; i<=q; i++) cin >> p[i], p[i].fi *= 2, p[i].se *= 2;

    Sub1::solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freop();

    int t=1; //cin >> t;
    while (t--) process();

    return 0;
}

Compilation message

bodyguard.cpp: In function 'void freop()':
bodyguard.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1775 ms 1077856 KB Output is correct
2 Correct 1502 ms 1094472 KB Output is correct
3 Correct 1352 ms 750416 KB Output is correct
4 Correct 1306 ms 698772 KB Output is correct
5 Correct 1324 ms 808396 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 4688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1775 ms 1077856 KB Output is correct
2 Correct 1502 ms 1094472 KB Output is correct
3 Correct 1352 ms 750416 KB Output is correct
4 Correct 1306 ms 698772 KB Output is correct
5 Correct 1324 ms 808396 KB Output is correct
6 Runtime error 51 ms 4688 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -