oj.uz

답안 #969940

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969940 2024-04-25T23:17:37 Z maksim1744 메기 농장 (IOI22_fish) C++17
23 / 100
 1000 ms 13288 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]);
    }
    dp1[0] = dp2[0] = 0;
    for (int i = 0; i < n; ++i) {
        vector<ll> next_dp1(sz + 1, -inf);
        vector<ll> next_dp2(sz + 1, -inf);

        for (int h = 0; h <= sz; ++h) {
            for (int h2 = 0; h2 <= sz; ++h2) {
                {
                    ll cur = 0;
                    if (i > 0 && h2 < h) {
                        for (const auto& [y, w] : atx[i - 1]) {
                            if (h2 <= y && y < h) {
                                cur += w;
                            }
                        }
                    }
                    cur += dp1[h2];
                    next_dp2[h] = max(next_dp2[h], cur);
                    next_dp1[h] = max(next_dp1[h], cur);
                }
                {
                    ll cur = 0;
                    if (h2 > h) {
                        for (const auto& [y, w] : atx[i]) {
                            if (h2 > y && y >= h) {
                                cur += w;
                            }
                        }
                    }
                    cur += dp2[h2];
                    next_dp1[h2] = max(next_dp1[h2], cur);
                    next_dp2[h] = max(next_dp2[h], cur);
                }
            }
            next_dp2[h] = max(next_dp2[h], maxe(dp2));
        }

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

        show(dp1, 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

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1047 ms 9672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1041 ms 13288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2648 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 21 ms 6356 KB Output is correct
4 Correct 16 ms 5344 KB Output is correct
5 Correct 39 ms 9660 KB Output is correct
6 Correct 31 ms 9052 KB Output is correct
7 Correct 35 ms 9560 KB Output is correct
8 Correct 34 ms 9668 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 376 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 600 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 444 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 376 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 600 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 444 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 140 ms 348 KB Output is correct
16 Correct 23 ms 344 KB Output is correct
17 Execution timed out 1004 ms 2648 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 376 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 600 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 444 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 140 ms 348 KB Output is correct
16 Correct 23 ms 344 KB Output is correct
17 Execution timed out 1004 ms 2648 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2648 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 21 ms 6356 KB Output is correct
4 Correct 16 ms 5344 KB Output is correct
5 Correct 39 ms 9660 KB Output is correct
6 Correct 31 ms 9052 KB Output is correct
7 Correct 35 ms 9560 KB Output is correct
8 Correct 34 ms 9668 KB Output is correct
9 Execution timed out 1006 ms 12740 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1047 ms 9672 KB Time limit exceeded
2 Halted 0 ms 0 KB -