Submission #837929

#TimeUsernameProblemLanguageResultExecution timeMemory
837929joylintpCatfish Farm (IOI22_fish)C++17
0 / 100
852 ms2097152 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { vector<vector<pair<int, int>>> fish(N); for (int i = 0; i < M; i++) fish[X[i]].push_back(make_pair(Y[i], W[i])); for (int i = 0; i < N; i++) sort(fish[i].begin(), fish[i].end()); vector<vector<vector<long long>>> dp(N, vector<vector<long long>>(N + 1, vector<long long>(N + 1))); for (int x = 0; x <= N; x++) { int fid = 0; for (int y = 1; y <= N; y++) { dp[0][x][y] = dp[0][x][y - 1]; if (fid < fish[0].size() && fish[0][fid].first + 1 == y) { if (fish[0][fid].first >= x) dp[0][x][y] += fish[0][fid].second; fid++; } } } for (int i = 1; i < N - 1; i++) for (int x = 0; x <= N; x++) { for (int j = 0; j <= N; j++) dp[i][x][0] = max(dp[i][x][0], dp[i - 1][j][x]); int fid = 0; for (int y = 1; y <= N; y++) { dp[i][x][y] = dp[i][x][y - 1]; if (fid < fish[i].size() && fish[i][fid].first + 1) { if (fish[i][fid].first >= x) dp[i][x][y] += fish[i][fid].second; fid++; } } } long long ret = 0; for (int x = 0; x <= N; x++) { long long now = 0; for (auto &p : fish[N - 1]) if (p.first >= x) break; else now += p.second; int fid = 0; for (int y = 0; y <= N; y++) { if (fid < fish[N - 1].size() && fish[N - 1][fid].first + 1 == y && y < x + 1) now -= fish[N - 1][fid].second; ret = max(ret, dp[N - 2][x][y] + now); } } return ret; }

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |             if (fid < fish[0].size() && fish[0][fid].first + 1 == y)
      |                 ~~~~^~~~~~~~~~~~~~~~
fish.cpp:39:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 if (fid < fish[i].size() && fish[i][fid].first + 1)
      |                     ~~~~^~~~~~~~~~~~~~~~
fish.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             if (fid < fish[N - 1].size() && fish[N - 1][fid].first + 1 == y && y < x + 1)
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~
#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...