#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int NMAX = 1e5 + 5;
vector <vector <ll> > DP(NMAX);
vector <vector <ll> > dp(NMAX);
vector <vector <ll> > p(NMAX);
vector <vector <ll> > pmax(NMAX);
vector <vector <ll> > smax(NMAX);
vector <vector <pll> > vec(NMAX);
vector <vector <int> > vec1(NMAX);
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
int n = N, m = M;
vector <int> x = X, y = Y, w = W;
for(int i = 0; i < m; i++){
vec[x[i] + 1].pb({y[i] + 1, w[i]});
vec1[x[i] + 1].pb(y[i] + 1);
}
for(int i = 1; i <= n; i++){
vec[i].pb({0, 0});
vec[i].pb({n + 1, 0});
vec1[i].pb(0);
vec1[i].pb(n + 1);
sort(vec1[i].begin(), vec1[i].end());
sort(vec[i].begin(), vec[i].end());
dp[i].resize(vec[i].size());
DP[i].resize(vec[i].size());
p[i].resize(vec[i].size());
pmax[i].resize(vec[i].size());
smax[i].resize(vec[i].size());
p[i][0] = 0;
for(int j = 1; j < vec[i].size(); j++) p[i][j] = p[i][j - 1] + vec[i][j].s;
}
ll ans = 0;
for(int i = 1; i <= n; i++){
if(i != 1){
for(int j = 0; j < vec[i].size(); j++){
int x = lower_bound(vec1[i - 1].begin(), vec1[i - 1].end(), vec1[i][j]) - vec1[i - 1].begin();
x--;
if(j > 0)DP[i][j] = pmax[i - 1][x] + p[i - 1][j - 1];
ans = max(ans, DP[i][j]);
}
DP[i][0] = max(DP[i][0], dp[i - 1][0]);
for(int j = 0; j < vec[i].size(); j++){
int x = upper_bound(vec1[i - 1].begin(), vec1[i - 1].end(), vec1[i][j]) - vec1[i -1].begin();
if(x < vec[i - 1].size()){
dp[i][j] = smax[i - 1][x] - p[i][j];
ans = max(ans, dp[i][j]);
}
}
}
pmax[i][0] = DP[i][0];
for(int j= 1; j < vec[i].size(); j++) pmax[i][j] = max(DP[i][j] - p[i][j - 1], pmax[i][j - 1]);
smax[i].back() = max(dp[i].back(), DP[i].back());
if(!vec[i + 1].empty()) {
int x = lower_bound(vec1[i + 1].begin(), vec1[i + 1].end(), vec1[i].back()) - vec1[i + 1].begin();
x--;
smax[i].back() += p[i + 1][x];
}
for(int j = smax[i].size() - 2; j >= 0; j--){
smax[i][j] = max(dp[i][j], DP[i][j]);
int x = lower_bound(vec1[i + 1].begin(), vec1[i + 1].end(), vec1[i][j]) - vec1[i + 1].begin();
x--;
if(x > 0){
smax[i][j] += p[i + 1][x];
}
smax[i][j] = max(smax[i][j], smax[i][j +1]);
}
}
return ans;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:26: 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]
44 | for(int j = 1; j < vec[i].size(); j++) p[i][j] = p[i][j - 1] + vec[i][j].s;
| ~~^~~~~~~~~~~~~~~
fish.cpp:49:30: 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]
49 | for(int j = 0; j < vec[i].size(); j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp:56:30: 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]
56 | for(int j = 0; j < vec[i].size(); j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp:58:22: 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]
58 | if(x < vec[i - 1].size()){
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:65:25: 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]
65 | for(int j= 1; j < vec[i].size(); j++) pmax[i][j] = max(DP[i][j] - p[i][j - 1], pmax[i][j - 1]);
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
46576 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
40216 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
40216 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
46576 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
