Submission #625748

#TimeUsernameProblemLanguageResultExecution timeMemory
625748flashmtCatfish Farm (IOI22_fish)C++17
0 / 100
45 ms4000 KiB
#include <bits/stdc++.h> using namespace std; const long long oo = 1LL << 60; long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) { if (n > 3000) return 0; for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++) if (make_pair(x[i], y[i]) > make_pair(x[j], y[j])) { swap(x[i], x[j]); swap(y[i], y[j]); swap(w[i], w[j]); } // f: left, g: right vector<long long> f(m, -oo), g(m, -oo); long long ans = 0; for (int i = 0; i < m;) { int ii = i + 1; while (ii < m && x[ii] == x[i]) ii++; for (int j = i; j < ii; j++) if (x[j] < n - 1) { g[j] = w[j]; for (int jj = 0; jj < i; jj++) if (x[jj] + 1 < x[j]) g[j] = max(g[j], max(f[jj], g[jj]) + w[j]); else if (y[jj] < y[j]) g[j] = max(g[j], g[jj] + w[j]); for (int jj = i; jj < j; jj++) g[j] = max(g[j], g[jj] + w[j]); } for (int j = ii - 1; j >= i; j--) if (x[j]) { f[j] = w[j]; for (int jj = 0; jj < i; jj++) if (x[jj] + 1 < x[j]) f[j] = max(f[j], max(f[jj], g[jj]) + w[j]); else if (y[jj] > y[j]) f[j] = max(f[j], f[jj] + w[j]); for (int jj = j + 1; jj < ii; jj++) f[j] = max(f[j], f[jj] + w[j]); } ans = max({ans, f[i], g[i]}); i = ii; } return ans; }
#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...