#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++){
int len = vec[i].size();
if(i != 1){
for(int j = 0; j < len; j++){
int x = lower_bound(vec1[i - 1].begin(), vec1[i - 1].end(), vec1[i][j]) - vec1[i - 1].begin();
x--;
if(x > 0)DP[i][j] = pmax[i - 1][x] + p[i - 1][x];
ans = max(ans, DP[i][j]);
}
DP[i][0] = max(DP[i][0], dp[i - 1][0]);
ans = max(ans, dp[i - 1][0]);
DP[i].back() = max(DP[i].back(), DP[i - 1].back());
ans = max(ans, DP[i - 1].back());
for(int j = 0; j < len; j++){
int x = upper_bound(vec1[i - 1].begin(), vec1[i - 1].end(), vec1[i][j]) - vec1[i -1].begin();
if(j > 0)dp[i][j] = smax[i - 1][x] - p[i][j - 1];
else dp[i][j] = smax[i - 1][x];
ans = max(ans, dp[i][j]);
}
dp[i].back() = max(dp[i - 1].back(), DP[i - 1].back());
}
pmax[i][0] = DP[i][0];
for(int j= 1; j < len; 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 = len - 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]);
}
}
/*for(int i = 1; i <= n; i++){
for(int to : dp[i]) cout << to << ' ';
cout << "\n";
}
for(int i= 1; i <= n; i++){
for(int to : DP[i]) cout << to << ' ';
cout << "\n";
}*/
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;
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
114 ms |
45444 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '380620001783671' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '2', found: '80' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
40140 KB |
Output is correct |
| 2 |
Correct |
74 ms |
40140 KB |
Output is correct |
| 3 |
Incorrect |
117 ms |
41424 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '20790282846756' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '3', found: '80' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '3', found: '80' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
16724 KB |
1st lines differ - on the 1st token, expected: '3', found: '80' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
40140 KB |
Output is correct |
| 2 |
Correct |
74 ms |
40140 KB |
Output is correct |
| 3 |
Incorrect |
117 ms |
41424 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '20790282846756' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
114 ms |
45444 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '380620001783671' |
| 2 |
Halted |
0 ms |
0 KB |
- |
