| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037276 |
2024-07-28T12:22:30 Z |
Issa |
Catfish Farm (IOI22_fish) |
C++17 |
|
92 ms |
35112 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int maxn = 3e3 + 100;
const int maxl = 11;
int n;
vector<ll> dp[maxn][2];
vector<int> d[maxn];
vector<pll> a[maxn];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
n = N;
for(int i = 0; i < M; i++){
X[i]++; Y[i]++;
a[X[i]].push_back({Y[i], W[i]});
}
for(int i = 1; i <= n; i++){
for(auto [j, x]: a[i]){
d[i].push_back(j);
d[i].push_back(j-1);
}
for(auto [j, x]: a[i-1]) d[i].push_back(j);
for(auto [j, x]: a[i+1]) d[i].push_back(j);
sort(d[i].begin(), d[i].end());
d[i].resize(unique(d[i].begin(), d[i].end()) - d[i].begin());
dp[i][0] = dp[i][1] = vector<ll>(d[i].size(), -1e18 * (i > 1));
sort(a[i].begin(), a[i].end());
}
for(int i = 1; i < n; i++){
vector<tuple<int, int, int>> v;
for(auto [j, x]: a[i]) v.push_back({j, 0, x});
for(auto [j, x]: a[i+1]) v.push_back({j, 1, x});
for(int j = 0; j < d[i].size(); j++){
v.push_back({d[i][j], 2, j});
}
for(int j = 0; j < d[i+1].size(); j++){
v.push_back({d[i+1][j], 3, j});
}
sort(v.begin(), v.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
auto [a0, a1, a2] = a; auto [b0, b1, b2] = b;
if(a0 != b0) return a0 > b0;
return a1 < b1;
});
ll mx = -1e18;
for(auto [x, c, j]: v){
if(c == 1) mx += j;
else if(c == 2) mx = max({mx, dp[i][0][j], dp[i][1][j]});
else if(c == 3) dp[i+1][0][j] = max(dp[i+1][0][j], mx);
}
sort(v.begin(), v.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
auto [a0, a1, a2] = a; auto [b0, b1, b2] = b;
if(a0 != b0) return a0 < b0;
return a1 < b1;
});
mx = -1e18;
for(auto [x, c, j]: v){
if(c == 0) mx += j;
else if(c == 2) mx = max(mx, dp[i][1][j]);
else if(c == 3) dp[i+1][1][j] = max(dp[i+1][1][j], mx);
}
ll sum = 0, mx1 = -1e18; mx = -1e18;
for(int j = 0, k = 0; j < d[i-1].size(); j++){
while(k < a[i].size() && a[i][k].first <= d[i-1][j]){
sum += a[i][k++].second;
}
mx1 = max(mx1, max(dp[i-1][0][j], dp[i-1][1][j]) + sum);
mx = max(mx, max(dp[i-1][0][j], dp[i-1][1][j]));
}
for(int j = 0, k = 0; j < d[i+1].size(); j++){
while(k < a[i].size() && a[i][k].first <= d[i+1][j]){
mx += a[i][k++].second;
}
dp[i+1][0][j] = max({dp[i+1][0][j], mx, mx1});
dp[i+1][1][j] = max({dp[i+1][1][j], mx, mx1});
}
}
ll ans = 0;
for(int i = 1; i <= n; i++){
ans = max(ans, *max_element(dp[i][0].begin(), dp[i][0].end()));
ans = max(ans, *max_element(dp[i][1].begin(), dp[i][1].end()));
}
return ans;
}
// for(int i = 1; i < n; i++){
// for(int j = 0; j <= n; j++){
// for(int k = 0; k <= n; k++){
// if(k >= j) dp[i+1][k][1] = max(dp[i+1][k][1], dp[i][j][1] + a[i][k] - a[i][j]);
// if(k <= j) dp[i+1][k][0] = max(dp[i+1][k][0], max(dp[i][j][1], dp[i][j][0]) + a[i+1][j] - a[i+1][k]);
// if(i > 1){
// dp[i+1][k][0] = max(dp[i+1][k][0], max(dp[i-1][j][1], dp[i-1][j][0]) + a[i][max(j, k)]);
// dp[i+1][k][1] = max(dp[i+1][k][1], max(dp[i-1][j][1], dp[i-1][j][0]) + a[i][max(j, k)]);
// }
// }
// }
// }
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int j = 0; j < d[i].size(); j++){
| ~~^~~~~~~~~~~~~
fish.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int j = 0; j < d[i+1].size(); j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp:65:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int j = 0, k = 0; j < d[i-1].size(); j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while(k < a[i].size() && a[i][k].first <= d[i-1][j]){
| ~~^~~~~~~~~~~~~
fish.cpp:72:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j = 0, k = 0; j < d[i+1].size(); j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | while(k < a[i].size() && a[i][k].first <= d[i+1][j]){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
21956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Runtime error |
92 ms |
35112 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
21956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
