Submission #632031

#TimeUsernameProblemLanguageResultExecution timeMemory
632031timreizinCatfish Farm (IOI22_fish)C++17
100 / 100
171 ms29288 KiB
#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]); } dp1[i] = dp0[i]; 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 (stderr)

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)
      |                        ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...