#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], mxpref[N], mxpref2[N];
vector<pair<ll, ll>> a[N];
vector<ll> b[N];
ll mx[N];
int n;
ll get(int pos, ll idx){
if(pos >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : pref[pos][x]);
}
ll getmxpref2(int pos, ll idx){
if(pos >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : mxpref2[pos][x]);
}
ll getmxpref(int pos, ll idx){
if(pos >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : mxpref[pos][x]);
}
ll getsuf(int pos, ll idx){
if(pos >= n) return 0;
int x = lower_bound(all(b[pos]), idx) - b[pos].begin();
return (x == b[pos].size() ? 0 : suf[pos][x]);
}
ll getdp(int pos, ll idx){
if(pos >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : dp[pos][x]);
}
ll getdp2(int pos, ll idx){
if(pos >= n) return 0;
int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
return (x == -1 ? 0 : dp2[pos][x]);
}
long long max_weights(int nn, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
n = nn;
for(int i = 0; i < m; ++i){
a[X[i]].pb({Y[i] + 1, W[i]});
// a[X[i]][Y[i] + 1] = W[i];
b[X[i]].pb(Y[i]);
}
for(int i = 0; i < n; ++i){
a[i].pb({n + 1, 0});
b[i].pb(n);
sort(all(a[i]));
sort(all(b[i]));
}
for(int i = 0; i < n; ++i){
pref[i].resize(b[i].size() + 1);
suf[i].resize(b[i].size() + 1);
dp[i].resize(b[i].size() + 1);
dp2[i].resize(b[i].size() + 1);
mxpref[i].resize(b[i].size() + 1);
mxpref2[i].resize(b[i].size() + 1);
pref[i][0] = 0;
for(int j = 1; j < b[i].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j - 1].ss;
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < b[i].size(); ++j) cout << pref[i][j] << ' ';
// en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < b[i].size(); ++j) cout << b[i][j] << ' ';
// en;
// }
// en;en;
// return 0;
mx[0] = 0;
for(int i = 0; i < b[0].size(); ++i){
dp[0][i] = dp2[0][i] = get(1, b[0][i]);
mx[0] = max(mx[0], dp[0][i]);
}
suf[0][b[0].size()] = 0;
for(int j = b[0].size() - 1; j >= 0 ;--j) suf[0][j] = max(suf[0][j + 1], dp[0][j]);
// return 0ll;
int i = 0;
mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);
for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j - 1], dp[i][j] - get(i + 1, b[i][j]));
for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
for(i = 1; i < n; ++i){
mx[i] = 0;
ll mx_pref = 0, mx_pref2 = 0;
for(int j = 0; j < b[i].size(); ++j){
ll pos = b[i][j];
ll A = get(i - 1, pos);
ll B = get(i, pos);
ll C = get(i + 1, pos);
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 = add - B - A; //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, getmxpref2(i - 1, pos));//max(mx_pref2, getdp2(i - 1, pos) - 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, pos) + x);//suf[i - 1][j] + x);
if(i > 1){
mx_pref = max(mx_pref, getmxpref(i - 2, pos));//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, pos) - 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, pos) - A);//suf[i - 2][j] - pref[i - 1][j]);
}
// cout << dp[i][j] << ' ' << i << ' ' << pos << endl;
mx[i] = max(mx[i], dp[i][j]);
}
suf[i][b[i].size()] = 0;
for(int j = int(b[i].size()) - 1; j >= 0 ;--j) suf[i][j] = max(suf[i][j + 1], dp[i][j]);
mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);
for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j - 1], dp[i][j] - get(i + 1, b[i][j]));
for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
// for(int j = n-1; j >= 0 ;--j) suf2[i][j] = max(suf2[i][j + 1], dp[i][j]);
// en;
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < b[i].size(); ++j) cout << 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:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | return (x == b[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:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int j = 1; j < b[i].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j - 1].ss;
| ~~^~~~~~~~~~~~~
fish.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0; i < b[0].size(); ++i){
| ~~^~~~~~~~~~~~~
fish.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j - 1], dp[i][j] - get(i + 1, b[i][j]));
| ~~^~~~~~~~~~~~~
fish.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
| ~~^~~~~~~~~~~~~
fish.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j = 0; j < b[i].size(); ++j){
| ~~^~~~~~~~~~~~~
fish.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j - 1], dp[i][j] - get(i + 1, b[i][j]));
| ~~^~~~~~~~~~~~~
fish.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
91 ms |
50068 KB |
Output is correct |
| 2 |
Correct |
102 ms |
54408 KB |
Output is correct |
| 3 |
Correct |
60 ms |
44880 KB |
Output is correct |
| 4 |
Correct |
34 ms |
44892 KB |
Output is correct |
| 5 |
Correct |
147 ms |
73364 KB |
Output is correct |
| 6 |
Correct |
221 ms |
74580 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
19800 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
35 ms |
44884 KB |
Output is correct |
| 2 |
Correct |
34 ms |
44884 KB |
Output is correct |
| 3 |
Correct |
61 ms |
44592 KB |
Output is correct |
| 4 |
Correct |
47 ms |
46224 KB |
Output is correct |
| 5 |
Correct |
72 ms |
48720 KB |
Output is correct |
| 6 |
Correct |
81 ms |
48884 KB |
Output is correct |
| 7 |
Correct |
80 ms |
48720 KB |
Output is correct |
| 8 |
Correct |
82 ms |
48740 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
19800 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
19800 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
19800 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
35 ms |
44884 KB |
Output is correct |
| 2 |
Correct |
34 ms |
44884 KB |
Output is correct |
| 3 |
Correct |
61 ms |
44592 KB |
Output is correct |
| 4 |
Correct |
47 ms |
46224 KB |
Output is correct |
| 5 |
Correct |
72 ms |
48720 KB |
Output is correct |
| 6 |
Correct |
81 ms |
48884 KB |
Output is correct |
| 7 |
Correct |
80 ms |
48720 KB |
Output is correct |
| 8 |
Correct |
82 ms |
48740 KB |
Output is correct |
| 9 |
Incorrect |
74 ms |
48720 KB |
1st lines differ - on the 1st token, expected: '99999', found: '66666' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
91 ms |
50068 KB |
Output is correct |
| 2 |
Correct |
102 ms |
54408 KB |
Output is correct |
| 3 |
Correct |
60 ms |
44880 KB |
Output is correct |
| 4 |
Correct |
34 ms |
44892 KB |
Output is correct |
| 5 |
Correct |
147 ms |
73364 KB |
Output is correct |
| 6 |
Correct |
221 ms |
74580 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
19800 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 8 |
Halted |
0 ms |
0 KB |
- |
