Submission #1079444

#TimeUsernameProblemLanguageResultExecution timeMemory
1079444asdasdqwerCatfish Farm (IOI22_fish)C++17
53 / 100
1071 ms2097152 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { // first subtask bool s1 = true, s2=true, s3 = true; for (int i=0;i<M;i++) { if (X[i] % 2 != 0) s1=false; if (X[i] > 1) s2=false; if (Y[i] != 0) s3 = false; } if (s1) { long long sm = 0; for (int i=0;i<M;i++) sm += W[i]; return sm; } if (s2) { long long sm1=0,sm2=0; for (int i=0;i<M;i++) { if (X[i] == 0) sm1 += W[i]; else sm2 += W[i]; } if (N == 2) return max(sm1, sm2); vector<long long> p(N, 0), s(N, 0); for (int i=0;i<M;i++) { if (X[i] == 0) p[Y[i]] += W[i]; else s[Y[i]] += W[i]; } for (int i=1;i<N;i++) p[i]+=p[i-1]; for (int i=N-2;i>=0;i--) s[i] += s[i+1]; long long mx = max(p[N-1], s[0]); for (int i=1;i<N;i++) { mx = max(mx, p[i-1]+s[i]); } return mx; } if (s3) { vector<int> w(N,0); for (int i=0;i<M;i++) { w[X[i]] = W[i]; } vector<long long> dp1(N, 0), dp2(N, 0), dp3(N, 0); dp1[0] = dp2[0] = dp3[0] = 0; for (int i=1;i<N;i++) { // build smt dp1[i] = max(dp1[i-1], max(dp2[i-1], dp3[i-1] + w[i-1])); dp2[i] = max(dp1[i-1] + w[i], max(dp2[i-1], dp3[i-1])); dp3[i] = max(dp3[i-1], dp2[i-1]); } return max(dp1.back(), max(dp2.back(), dp3.back())); } vector<vector<long long>> dp1(N, vector<long long>(N+1, 0)), dp2(N, vector<long long>(N+1, 0)); // dp1[i][j] : maximum number of fish such that row i has pier with height j // dp2[i][j] : maximum number of fish such that row i has pier with height j and row i-1 has pier with height no greater than j vector<vector<long long>> s(N, vector<long long>(N+1, 0)); for (int i=0;i<M;i++) { s[X[i]][Y[i]+1] = W[i]; } for (int i=N-1;i>=0;i--) { for (int j=N-1;j>=0;j--) { s[i][j] += s[i][j+1]; } } long long mx = 0; for (int i=1;i<N;i++) { for (int j=0;j<=N;j++) { long long sub = (j == N ? 0 : s[i-1][j+1]); for (int k=0;k<=j;k++) { dp1[i][j] = max(dp1[i][j], max(dp2[i-1][k] + (k == N ? 0 : s[i-1][k+1]) - sub, dp1[i-1][k])); } dp2[i][j] = dp1[i][j]; sub = (j == N ? 0 : s[i][j+1]); for (int k=j+1;k<=N;k++) { dp1[i][j] = max(dp1[i][j], max(dp1[i-1][k], dp2[i-1][k]) + sub - (k == N ? 0 : s[i][k+1])); } mx = max(mx, max(dp1[i][j], dp2[i][j])); } } return mx; }
#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...