oj.uz

답안 #632028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632028 2022-08-19T10:24:54 Z timreizin 메기 농장 (IOI22_fish) C++17
0 / 100
 35 ms 10564 KB 
#include "fish.h"

#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;

ll solve(vector<vector<pair<int, ll>>> &fish, int n)
{
    ll res = 0;
    vector<vector<ll>> dp0(fish.size()), dp1(fish.size());
    for (int i = 0; i < fish.size(); ++i)
    {
        fish[i].emplace_back(n, 0);
        dp0[i].resize(fish[i].size());
        ll mx = 0;
        if (i != 0)
        {
            for (int j = 0; j < fish[i - 1].size(); ++j)
            {
                mx = max(mx, dp1[i - 1][j]);
            }
            fill(dp0[i].begin(), dp0[i].end(), mx);
            mx = 0;
        }
        for (int j = 0, k = 0; j < fish[i].size(); ++j)
        {
            if (i != 0)
            {
                while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
                {
                    mx = max(mx, dp0[i - 1][k]);
                    mx += fish[i - 1][k].second;
                    ++k;
                }
            }
            dp0[i][j] = max(mx, dp0[i][j]);
        }
        dp0 = dp1;
        if (i != 0)
        {
            ll mx = 0;
            for (int j = (int)fish[i].size() - 1, k = (int)fish[i - 1].size() - 1; j >= 0; --j)
            {
                while (k >= 0 && fish[i - 1][k].first > fish[i][j].first)
                {
                    mx = max(mx, dp1[i - 1][k]);
                    --k;
                }
                mx += fish[i][j].second;
                dp1[i][j] = max(dp1[i][j], mx);
                res = max(dp1[i][j], res);
            }
        }
    }
    return res;
}

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W)
{
    vector<tuple<int, int, ll>> xyw(m);
    for (int i = 0; i < m; ++i) xyw[i] = {X[i], Y[i], W[i]};
    sort(xyw.begin(), xyw.end());
    ll res = 0;
    vector<vector<pair<int, ll>>> tos;
    int prevX = -1;
    for (auto [x, y, w] : xyw)
    {
        if (x > prevX + 1)
        {
            tos.push_back(vector<pair<int, ll>>());
            res += solve(tos, n);
            tos.clear();
            tos.push_back(vector<pair<int, ll>>());
            prevX = x - 1;
        }
        if (x == prevX + 1)
        {
            tos.push_back(vector<pair<int, ll>>());
        }
        tos.back().emplace_back(y, w);
        prevX = x;
    }
    if (prevX != n - 1) tos.push_back(vector<pair<int, ll>>());
    res += solve(tos, n);
    return res;
}

Compilation message

fish.cpp: In function 'll solve(std::vector<std::vector<std::pair<int, long long int> > >&, int)':
fish.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < fish.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
fish.cpp:21:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             for (int j = 0; j < fish[i - 1].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:28:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int j = 0, k = 0; j < fish[i].size(); ++j)
      |                                ~~^~~~~~~~~~~~~~~~
fish.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                 while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
      |                        ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 35 ms 10564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 35 ms 10564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -