#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
#define ll long long
vector<vector<int>> v = {{-1}};
ll ans = 0;
int prev_index = -1;
int prev_limit = -1;
ll max_weights (int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<int>> v2 = {{-1}};
if (v == v2) {
vector<vector<int>> v3(n, vector<int>(n, 0));
v = v3;
for (int i = 0; i < m; i++)
v[x[i]][y[i]] = w[i];
}
// base case
int count = 0;
for (int i = 0; i < n; i++)
if (v[i].size() > n) count++;
// cout << count << endl;
if (count >= n-1) {
return ans;
}
// output variables
// ll ans = 0;
// prosess input
// get max weight column
vector<pair<int, int>> mxs(n);
for (int i = 0; i < n; i++) {
if (v[i].size() == n)
mxs[i] = make_pair(accumulate(v[i].begin(), v[i].end(), 0), i);
else
mxs[i] = make_pair(-1, -1);
}
auto mx_pair = max_element(mxs.begin(), mxs.end());
auto mx = mx_pair->second; // index
ll mx_sum = mx_pair->first; // sum
// assign pier column to the min weight column from the two adjacents ones
int mn; // index
if (0 <= mx+1 && mx+1 < n && 0 <= mx-1 && mx-1 < n) {
mn = min(mxs[mx-1], mxs[mx+1]).second;
if (mxs[mx-1].second == -1 && mxs[mx+1].second == -1) {
v[mx].push_back(0);
prev_index = -1;
prev_limit = -1;
return max_weights(n, m, x, y, w);
} else if (mxs[mx-1].second == -1) {
mn = mxs[mx+1].second;
} else if (mxs[mx+1].second == -1) {
mn = mxs[mx-1].second;
} else {
mn = min(mxs[mx+1], mxs[mx-1]).second;
}
} else if (0 <= mx+1 && mx+1 < n) {
if (mxs[mx+1].second == -1) {
v[mx].push_back(0);
prev_index = -1;
prev_limit = -1;
return max_weights(n, m, x, y, w);
}
mn = mxs[mx+1].second;
} else {
if (mxs[mx-1].second == -1) {
v[mx].push_back(0);
prev_index = -1;
prev_limit = -1;
return max_weights(n, m, x, y, w);
}
mn = mxs[mx-1].second;
}
int other = -1; // index
int other_sum = 0; // sum
if (mn-1 == mx && 0 <= mn+1 && mn+1 < n) {
other_sum = accumulate(v[mn+1].begin(), v[mn+1].end(), 0);
other = mn+1;
} else if (mn+1 == mx && 0 <= mn-1 && mn-1 < n) {
other_sum = accumulate(v[mn-1].begin(), v[mn-1].end(), 0);
other = mn-1;
}
int limit = 0;
for (int i = n-1; i >= 0; i--) {
if (other != -1) {
if (v[mx][i] > 0 || v[other][i] > 0) {
limit = i+1;
break;
}
} else {
if (v[mx][i] > 0) {
limit = i+1;
break;
}
}
}
// turn max weight column and pier column into zeros
if (prev_index == mn && prev_limit != -1 && prev_limit != -1) {
if (prev_limit <= limit) {
v[mn].push_back(0);
return max_weights(n, m, x, y, w);
}
}
ans += mx_sum;
ans += other_sum;
fill(v[mn].begin(), v[mn].begin()+limit-1, 0);
v[mn].push_back(0);
fill(v[mx].begin(), v[mx].end(), 0);
if (other != -1) fill(v[other].begin(), v[other].end(), 0);
// go to the next max column
return max_weights(n, m, x, y, w);
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
26 | if (v[i].size() > n) count++;
| ~~~~~~~~~~~~^~~
fish.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | if (v[i].size() == n)
| ~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
2097152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
832 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
779 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
1 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 |
0 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 |
1 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 |
0 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 |
1 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 |
Runtime error |
779 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
2097152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
