# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
625798 |
2022-08-10T19:39:26 Z |
Hazem |
Catfish Farm (IOI22_fish) |
C++17 |
|
1000 ms |
46468 KB |
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#ifdef B01
#include "deb.h"
#else
#define deb(...)
#endif
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<pair<int, int>>> g(n);
vector<vector<long long>> L(n);
vector<vector<long long>> R(n);
vector<vector<long long>> in(n);
vector<vector<long long>> dp(n);
for (int i = 0; i < m; i++) {
g[x[i]].emplace_back(y[i], w[i]);
}
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end());
g[i].emplace_back(n, 0);
int z = g[i].size();
dp[i].resize(z);
L[i].resize(z);
R[i].resize(z);
in[i].resize(z);
for (int j = 0; j < z - 1; j++) {
in[i][j + 1] = in[i][j] + g[i][j].second;
}
}
long long ans = 0;
for (int i = 0; i < n; i++) {
long long ls = 0, rs = 0;
int l = 0, r = 0;
for (int j = 0; j < (int) dp[i].size(); j++) {
if (i > 0) {
while (l < (int) g[i - 1].size() && g[i - 1][l].first < g[i][j].first) {
ls += g[i - 1][l++].second;
}
}
if (i + 1 < n) {
while (r < (int) g[i + 1].size() && g[i + 1][r].first < g[i][j].first) {
rs += g[i + 1][r++].second;
}
}
L[i][j] = ls;
R[i][j] = rs;
ans = max(ans, max(ls, rs));
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < (int) dp[i].size(); j++) {
for (int k = 0; k < (int) dp[i - 1].size(); k++) {
if (g[i - 1][k].first < g[i][j].first) {
dp[i][j] = max(dp[i][j], dp[i - 1][k] - in[i - 1][k]);
} else {
dp[i][j] = max(dp[i][j], dp[i - 1][k] - L[i][j]);
}
}
dp[i][j] += L[i][j];
ans = max(ans, dp[i][j] + R[i][j]);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
30024 KB |
Output is correct |
2 |
Correct |
86 ms |
33988 KB |
Output is correct |
3 |
Correct |
53 ms |
27604 KB |
Output is correct |
4 |
Correct |
46 ms |
27604 KB |
Output is correct |
5 |
Correct |
157 ms |
46468 KB |
Output is correct |
6 |
Correct |
224 ms |
44748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
1074 ms |
35060 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
27604 KB |
Output is correct |
2 |
Correct |
49 ms |
27588 KB |
Output is correct |
3 |
Incorrect |
79 ms |
26148 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
27604 KB |
Output is correct |
2 |
Correct |
49 ms |
27588 KB |
Output is correct |
3 |
Incorrect |
79 ms |
26148 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
30024 KB |
Output is correct |
2 |
Correct |
86 ms |
33988 KB |
Output is correct |
3 |
Correct |
53 ms |
27604 KB |
Output is correct |
4 |
Correct |
46 ms |
27604 KB |
Output is correct |
5 |
Correct |
157 ms |
46468 KB |
Output is correct |
6 |
Correct |
224 ms |
44748 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Execution timed out |
1074 ms |
35060 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |