제출 #656338

#제출 시각아이디문제언어결과실행 시간메모리
656338LoboCatfish Farm (IOI22_fish)C++17
81 / 100
1096 ms250520 KiB
#include "fish.h" #include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define fr first #define sc second #define all(x) x.begin(),x.end() const int maxn = 1e5+10; const int maxqh = 12; const int inf = 1e18+10; int n, m; vector<vector<int>> dp[maxn]; map<int,int> pf[maxn], pfmx0[maxn], pfmx1[maxn], sfmx0[maxn]; vector<pair<int,int>> fish[maxn]; // fishs from column i vector<int> hr[maxn]; // important heights from column i, the ones that can be chosen long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) { n = N; m = M; for(int i = 0; i < m; i++) { fish[X[i]+1].pb(mp(Y[i]+1,W[i])); hr[X[i]+1].pb(Y[i]); } for(int i = 0; i <= n; i++) { hr[i].pb(0); hr[i].pb(n); sort(all(hr[i])); sort(all(fish[i])); hr[i].erase(unique(all(hr[i])),hr[i].end()); // Store only the relevant heights for(int j = 0; j < hr[i].size(); j++) { dp[i].pb({0,0}); } } for(int i = 1; i <= n; i++) { for(auto j : hr[i-1]) pf[i][j] = 0; for(auto j : hr[i]) pf[i][j] = 0; for(auto j : hr[i+1]) pf[i][j] = 0; for(auto aux : fish[i]) { int y = aux.fr; int w = aux.sc; pf[i][y]+= w; } // Do a prefix sum on the weight of the fishs pf[i][0] = 0; for(auto it = next(pf[i].begin()); it != pf[i].end(); it++) { it->sc+= prev(it)->sc; } } // dp[i][h0][0/1] = until i, with h[i] = hr[i][h0] // and it's greater/smaller tha the previous // dp[1][h0][0/1] = 0 for(int h0 = 0; h0 < hr[1].size(); h0++) { dp[1][h0][0] = 0; dp[1][h0][1] = 0; pfmx0[1][hr[1][h0]] = max(pfmx0[1][hr[1][h0]],dp[1][h0][0]-pf[1][hr[1][h0]]); sfmx0[1][hr[1][h0]] = max(sfmx0[1][hr[1][h0]],dp[1][h0][0]+pf[1+1][hr[1][h0]]); sfmx0[1][hr[1][h0]] = max(sfmx0[1][hr[1][h0]],dp[1][h0][1]+pf[1+1][hr[1][h0]]); } for(auto j : hr[2]) { pfmx0[1][j] = max(pfmx0[1][j],0LL); } for(auto it = next(pfmx0[1].begin()); it != pfmx0[1].end(); it++) { it->sc = max(it->sc,prev(it)->sc); } for(auto j : hr[2]) { sfmx0[1][j] = max(sfmx0[1][j],0LL); } auto it = prev(prev(sfmx0[1].end())); while(true) { it->sc = max(it->sc,next(it)->sc); if(it == sfmx0[1].begin()) break; it = prev(it); } for(int i = 2; i <= n; i++) { for(int h0 = 0; h0 < hr[i].size(); h0++) { // It's greater than the previous dp[i][h0][0] = 0; dp[i][h0][0] = max(dp[i][h0][0], pfmx0[i-1][hr[i][h0]] + pf[i-1][hr[i][h0]]); if(i != 2) { dp[i][h0][0] = max(dp[i][h0][0],pfmx1[i-2][hr[i][h0]] + pf[i-1][hr[i][h0]]); } // It's smaller than the previous dp[i][h0][1] = 0; // for(int h1 = 0; h1 < hr[i-1].size(); h1++) { // if(hr[i-1][h1] < hr[i][h0]) continue; // dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][0]+pf[i][hr[i-1][h1]] - pf[i][hr[i][h0]]); // dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][1]+pf[i][hr[i-1][h1]] - pf[i][hr[i][h0]]); // } dp[i][h0][1] = max(dp[i][h0][1], sfmx0[i-1][hr[i][h0]] - pf[i][hr[i][h0]]); pfmx0[i][hr[i][h0]] = max(pfmx0[i][hr[i][h0]],dp[i][h0][0]-pf[i][hr[i][h0]]); pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],dp[i][h0][1]); pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],dp[i][h0][0]); sfmx0[i][hr[i][h0]] = max(sfmx0[i][hr[i][h0]],dp[i][h0][0]+pf[i+1][hr[i][h0]]); sfmx0[i][hr[i][h0]] = max(sfmx0[i][hr[i][h0]],dp[i][h0][1]+pf[i+1][hr[i][h0]]); } for(auto j : hr[i+1]) { pfmx0[i][j] = max(pfmx0[i][j],0LL); } for(auto it = next(pfmx0[i].begin()); it != pfmx0[i].end(); it++) { it->sc = max(it->sc,prev(it)->sc); } for(auto j : hr[i+2]) { pfmx1[i][j] = max(pfmx1[i][j],0LL); } for(auto it = next(pfmx1[i].begin()); it != pfmx1[i].end(); it++) { it->sc = max(it->sc,prev(it)->sc); } for(auto j : hr[i+1]) { sfmx0[i][j] = max(sfmx0[i][j],0LL); } auto it = prev(prev(sfmx0[i].end())); while(true) { it->sc = max(it->sc,next(it)->sc); if(it == sfmx0[i].begin()) break; it = prev(it); } } int ans = 0; for(int h0 = 0; h0 < hr[n].size(); h0++) { ans = max(ans, dp[n][h0][0]); ans = max(ans, dp[n][h0][1]); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:38:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:64:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int h0 = 0; h0 < hr[1].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
fish.cpp:90:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:143:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
#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...