#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define f first
#define s second
const int N=3e5+4;
int n,m;
vector<pair<int,int>> fish[N];
vector<ll> dp[N], dp1[N], inc[N];
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
for(int i=0; i<m; i++){
fish[X[i]+1].push_back({Y[i], W[i]});
}
for(int i=1; i<=n; i++){
fish[i].push_back({0, 0});
fish[i].push_back({n, 0});
sort(fish[i].begin(), fish[i].end());
}
int i=0;
fish[i].push_back({0, 0});
dp[i].resize(2);
dp1[i].resize(2);
inc[i].resize(2);
for(int i=1; i<=n; i++){
int p=fish[i].size();
if(p>1 && fish[i][1].f==fish[i][0].f) fish[i].erase(fish[i].begin());
dp[i].resize(p+1, -1e18);
dp1[i].resize(p+1, -1e18);
inc[i].resize(p+1, -1e18);
ll sum=0;
pair<int, ll> nxt, prv;
for(int j=0; j<p; j++){
auto fi=fish[i][j];
int y=fi.f, w=fi.s;
while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){
nxt.s+=fish[i+1][nxt.f].s;
nxt.f++;
}
while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){
prv.s+=fish[i-1][prv.f].s;
prv.f++;
}
int k=upper_bound(fish[i-1].begin(), fish[i-1].end(), make_pair(y, 0))-fish[i-1].begin();
dp[i][j]=max(dp1[i-1][k]-sum, fish[i-1][k-1].f?prv.s+inc[i-1][k-1]:0);
// cout << "inc " << prv.s+(fish[i-1][k-1].f?inc[i-1][k-1]:0) << "\n";
int k2;
if(i>=2){
k2=upper_bound(fish[i-2].begin(), fish[i-2].end(), make_pair(y, 0))-fish[i-2].begin();
dp[i][j]=max({dp[i][j], dp1[i-2][k2], (k2?dp[i-2][k2-1]:0)+prv.s});
}
inc[i][j]=max(
j?inc[i][j-1]:0,
-sum + max(fish[i-1][k-1].f?prv.s+inc[i-1][k-1]:0, i>=2?max(dp1[i-2][k2], dp[i-2][k2-1]+prv.s):0));
sum+=w;
// cout << "inc[" << i << "][" << j << "] " << inc[i][j] << "\n";
// cout << "dp[" << i << "][" << j << "] " << dp[i][j] << "\n";
dp1[i][j]=dp[i][j]+nxt.s;
}
for(int j=p-1; j>=0; j--){
dp1[i][j]=max(dp1[i][j+1], dp1[i][j]);
}
}
return dp1[n][0];
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){
| ~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){
| ~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
78 ms |
45520 KB |
Output is correct |
2 |
Correct |
87 ms |
48188 KB |
Output is correct |
3 |
Correct |
49 ms |
40932 KB |
Output is correct |
4 |
Correct |
46 ms |
40920 KB |
Output is correct |
5 |
Correct |
174 ms |
63728 KB |
Output is correct |
6 |
Correct |
246 ms |
66056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
17 ms |
28440 KB |
1st lines differ - on the 1st token, expected: '2', found: '50' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
40896 KB |
Output is correct |
2 |
Correct |
47 ms |
40956 KB |
Output is correct |
3 |
Correct |
70 ms |
45352 KB |
Output is correct |
4 |
Correct |
87 ms |
44472 KB |
Output is correct |
5 |
Incorrect |
109 ms |
50620 KB |
1st lines differ - on the 1st token, expected: '1673106170551', found: '1673106170600' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
28372 KB |
1st lines differ - on the 1st token, expected: '3', found: '51' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
28372 KB |
1st lines differ - on the 1st token, expected: '3', found: '51' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
16 ms |
28372 KB |
1st lines differ - on the 1st token, expected: '3', found: '51' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
40896 KB |
Output is correct |
2 |
Correct |
47 ms |
40956 KB |
Output is correct |
3 |
Correct |
70 ms |
45352 KB |
Output is correct |
4 |
Correct |
87 ms |
44472 KB |
Output is correct |
5 |
Incorrect |
109 ms |
50620 KB |
1st lines differ - on the 1st token, expected: '1673106170551', found: '1673106170600' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
78 ms |
45520 KB |
Output is correct |
2 |
Correct |
87 ms |
48188 KB |
Output is correct |
3 |
Correct |
49 ms |
40932 KB |
Output is correct |
4 |
Correct |
46 ms |
40920 KB |
Output is correct |
5 |
Correct |
174 ms |
63728 KB |
Output is correct |
6 |
Correct |
246 ms |
66056 KB |
Output is correct |
7 |
Incorrect |
17 ms |
28440 KB |
1st lines differ - on the 1st token, expected: '2', found: '50' |
8 |
Halted |
0 ms |
0 KB |
- |