#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define en cout << '\n'
#define pi pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
const int N = 100005;
// ll dp[N][N], pref[N][N], mx[N], dp2[N][N], suf[N][N];
vector<ll> dp2[N], dp[N], pref[N], suf[N];
vector<pair<ll, ll>> a[N];
ll mx[N];
ll get(int pos, ll idx){
int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin(); --x;
return (x == -1 ? 0 : pref[pos][x]);
}
ll getsuf(int pos, ll idx){
int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin();
return (x == a[pos].size() ? 0 : suf[pos][x]);
}
ll getdp(int pos, ll idx){
int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin(); --x;
return (x == -1 ? 0 : dp[pos][x]);
}
ll getdp2(int pos, ll idx){
int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin(); --x;
return (x == -1 ? 0 : dp2[pos][x]);
}
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){
a[X[i]].pb({Y[i] + 1, W[i]});
// a[X[i]][Y[i] + 1] = W[i];
}
for(int i = 0; i < n; ++i){
if(a[i].empty()) a[i].pb({n, 0});
else if(a[i].back().ff != n) a[i].pb({n, 0});
sort(all(a[i]));
}
for(int i = 0; i < n; ++i){
pref[i].resize(a[i].size() + 1);
suf[i].resize(a[i].size() + 1);
dp[i].resize(a[i].size() + 1);
dp2[i].resize(a[i].size() + 1);
pref[i][0] = a[i][0].ss;
for(int j = 1; j < a[0].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j].ss;
}
for(int i = 0; i < a[0].size(); ++i){
dp[0][i] = dp2[0][i] = get(1, a[0][i].ff);
}
mx[0] = pref[1].back();
suf[0][a[0].size()] = 0;
for(int j = a[0].size() - 1; j >= 0 ;--j) suf[0][j] = max(suf[0][j + 1], dp[0][j]);
for(int i = 1; i < n; ++i){
mx[i] = 0;
ll mx_pref = 0, mx_pref2 = 0;
for(int j = 0; j < a[i].size(); ++j){
ll A = get(i - 1, a[i][j].ff);
ll B = get(i, a[i][j].ff);
ll C = get(i + 1, a[i][j].ff);
ll add = A + C; //pref[i + 1][j] + pref[i - 1][j];
dp[i][j] = add;
if(i > 2) dp[i][j] = max(dp[i][j], mx[i - 3] + add);
dp2[i][j] = dp[i][j];
// cout << i << ' ' << j << ' ' << add1 << ' ' <<add2 << ' ';
ll x = C - B; //add - pref[i - 1][j] - pref[i][j];
// for(int j2 = j + 1; j2 <= n; ++j2){
// dp[i][j] = max(dp[i][j], dp[i - 1][j2] + x);
// }
mx_pref2 = max(mx_pref2, getdp2(i - 1, j) - A - B); //dp2[i - 1][j] - pref[i - 1][j] - pref[i][j]);
dp[i][j] = max(dp[i][j], mx_pref2 + add);
dp2[i][j] = max(dp2[i][j], mx_pref2 + add);
dp[i][j] = max(dp[i][j], getsuf(i - 1, j) + x);//suf[i - 1][j] + x);
if(i > 1){
mx_pref = max(mx_pref, getdp(i - 2, j) - A);//dp[i - 2][j] - pref[i - 1][j]);
dp[i][j] = max(dp[i][j], mx_pref + add);
dp[i][j] = max(dp[i][j], getsuf(i - 2, j) - A);//suf[i - 2][j] - pref[i - 1][j]);
dp2[i][j] = max(dp2[i][j], mx_pref + add);
dp2[i][j] = max(dp2[i][j], getsuf(i - 2, j) - A);//suf[i - 2][j] - pref[i - 1][j]);
}
// cout << dp[i][j] << '\n';
mx[i] = max(mx[i], dp[i][j]);
}
suf[i][a[i].size()] = 0;
for(int j = int(a[i].size()) - 1; j >= 0 ;--j) suf[i][j] = max(suf[i][j + 1], dp[i][j]);
// for(int j = n-1; j >= 0 ;--j) suf2[i][j] = max(suf2[i][j + 1], dp[i][j]);
// en;
}
ll ans = mx[n - 1];
return ans;
}
Compilation message
fish.cpp: In function 'long long int getsuf(int, long long int)':
fish.cpp:24:13: 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]
24 | return (x == a[pos].size() ? 0 : suf[pos][x]);
| ~~^~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:50: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]
50 | for(int j = 1; j < a[0].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j].ss;
| ~~^~~~~~~~~~~~~
fish.cpp:52:20: 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]
52 | for(int i = 0; i < a[0].size(); ++i){
| ~~^~~~~~~~~~~~~
fish.cpp:62: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]
62 | for(int j = 0; j < a[i].size(); ++j){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
41664 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12124 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 |
Correct |
24 ms |
28496 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
28508 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12120 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12120 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12120 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
28496 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
28508 KB |
1st lines differ - on the 1st token, expected: '882019', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
41664 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
