oj.uz

Submission #969941

# Submission time Handle Problem Language Result Execution time Memory
969941 2024-04-25T23:34:27 Z maksim1744 Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 17492 KB 
/*
    author:  Maksim1744
    created: 26.04.2024 01:52:26
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

const ll inf = 1e18;

ll max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    int sz = maxe(Y) + 1;
    vector<ll> dp1(sz + 1, -inf);
    vector<ll> dp2(sz + 1, -inf);
    vector<vector<pair<int, int>>> atx(n);
    for (int i = 0; i < m; ++i) {
        atx[X[i]].eb(Y[i], W[i]);
    }
    for (auto& v : atx)
        sort(v.begin(), v.end());
    dp1[0] = dp2[0] = 0;
    for (int i = 0; i < n; ++i) {
        vector<ll> next_dp1(sz + 1, 0);
        vector<ll> next_dp2(sz + 1, 0);

        int ind1 = 0;
        ll cur1 = 0;
        for (int h = 0; h <= sz; ++h) {
            if (i) {
                cur1 = max(cur1, dp1[h]);
                next_dp2[h] = max(next_dp2[h], cur1);
                next_dp1[h] = max(next_dp1[h], cur1);
                if (ind1 < atx[i - 1].size() && atx[i - 1][ind1].first == h) {
                    cur1 += atx[i - 1][ind1].second;
                    ++ind1;
                }
            }
        }

        int ind2 = (int)atx[i].size() - 1;
        ll cur2 = -inf;
        for (int h = sz; h >= 0; --h) {
            if (ind2 >= 0 && atx[i][ind2].first == h) {
                cur2 += atx[i][ind2].second;
                --ind2;
            }
            cur2 = max(cur2, dp2[h]);
            next_dp2[h] = max(next_dp2[h], cur2);
        }

        int ind3 = 0;
        ll cur3 = 0;
        for (int h = 0; h <= sz; ++h) {
            next_dp1[h] = max(next_dp1[h], dp2[h] + cur3);
            if (ind3 < atx[i].size() && atx[i][ind3].first == h) {
                cur3 += atx[i][ind3].second;
                ++ind3;
            }
        }

        swap(dp1, next_dp1);
        swap(dp2, next_dp2);
    }

    return max(maxe(dp1), maxe(dp2));
}


#ifdef HOUSE
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> x(m), y(m), w(m);
    for (int i = 0; i < m; ++i) {
        cin >> x[i] >> y[i] >> w[i];
    }
    cout << max_weights(n, m, x, y, w) << '\n';

    return 0;
}
#endif

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                 if (ind1 < atx[i - 1].size() && atx[i - 1][ind1].first == h) {
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             if (ind3 < atx[i].size() && atx[i][ind3].first == h) {
      |                 ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1045 ms 10652 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2648 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 21 ms 5432 KB Output is correct
4 Correct 16 ms 4696 KB Output is correct
5 Correct 34 ms 8228 KB Output is correct
6 Correct 41 ms 8524 KB Output is correct
7 Correct 33 ms 8028 KB Output is correct
8 Correct 34 ms 8024 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 13 ms 2008 KB Output is correct
18 Correct 13 ms 3004 KB Output is correct
19 Correct 13 ms 2744 KB Output is correct
20 Correct 16 ms 2880 KB Output is correct
21 Correct 12 ms 2908 KB Output is correct
22 Correct 25 ms 5468 KB Output is correct
23 Correct 3 ms 860 KB Output is correct
24 Correct 9 ms 2012 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 3 ms 860 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 13 ms 2008 KB Output is correct
18 Correct 13 ms 3004 KB Output is correct
19 Correct 13 ms 2744 KB Output is correct
20 Correct 16 ms 2880 KB Output is correct
21 Correct 12 ms 2908 KB Output is correct
22 Correct 25 ms 5468 KB Output is correct
23 Correct 3 ms 860 KB Output is correct
24 Correct 9 ms 2012 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 40 ms 856 KB Output is correct
28 Correct 71 ms 12536 KB Output is correct
29 Correct 126 ms 16856 KB Output is correct
30 Correct 134 ms 16468 KB Output is correct
31 Correct 150 ms 16468 KB Output is correct
32 Correct 86 ms 17492 KB Output is correct
33 Correct 129 ms 16620 KB Output is correct
34 Correct 128 ms 16464 KB Output is correct
35 Correct 36 ms 6736 KB Output is correct
36 Correct 126 ms 17420 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2648 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 21 ms 5432 KB Output is correct
4 Correct 16 ms 4696 KB Output is correct
5 Correct 34 ms 8228 KB Output is correct
6 Correct 41 ms 8524 KB Output is correct
7 Correct 33 ms 8028 KB Output is correct
8 Correct 34 ms 8024 KB Output is correct
9 Execution timed out 1047 ms 11752 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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