#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using integer = int;
#define int long long
int n,m;
vector<pair<int,int>> a[100005];
vector<int> sp[100005];
vector<int> poz[100005];
vector<int> dp0[100005],dp1[100005];
vector<int> mp_dp0[100005],mp_dp1[100005],ms_dp0[100005],ms_dp1[100005];
vector<int> lol1[100005];///maxime pe prefix din dp1[i][h] - f(i,h)
vector<int> lol2[100005];///maxime pe sufix din max(dp0[i][h],dp1[i][h]) + f(i + 1,h)
int max_idx(int col,int h)
{
int st = -1,pas = 1 << 16;
while (pas != 0)
{
if (st + pas < poz[col].size() and poz[col][st + pas] <= h)
st += pas;
pas /= 2;
}
return st;
}
int max_idx_2(int col,int h)
{
int st = -1,pas = 1 << 16;
while (pas != 0)
{
if (st + pas < a[col].size() and a[col][st + pas].first <= h)
st += pas;
pas /= 2;
}
return st;
}
int f(int col,int h)
{
int idx = max_idx_2(col,h);
if (idx == -1)
return 0;
return sp[col][idx];
}
void build(int col)
{
for (int i = 0; i < poz[col].size(); i++)
{
if (i == 0)
{
mp_dp0[col][i] = dp0[col][i];
mp_dp1[col][i] = dp1[col][i];
}
else
{
mp_dp0[col][i] = max(mp_dp0[col][i - 1],dp0[col][i]);
mp_dp1[col][i] = max(mp_dp1[col][i - 1],dp1[col][i]);
}
}
for (int i = poz[col].size() - 1; i >= 0; i--)
{
if (i + 1 == poz[col].size())
{
ms_dp0[col][i] = dp0[col][i];
ms_dp1[col][i] = dp1[col][i];
}
else
{
ms_dp0[col][i] = max(ms_dp0[col][i + 1],dp0[col][i]);
ms_dp1[col][i] = max(ms_dp1[col][i + 1],dp1[col][i]);
}
}
for (int i = 0; i < poz[col].size(); i++)
{
int vl = dp1[col][i] - f(col,poz[col][i]);
if (i == 0)
lol1[col][i] = vl;
else
lol1[col][i] = max(lol1[col][i - 1],vl);
}
for (int i = poz[col].size() - 1; i >= 0; i--)
{
int vl = max(dp0[col][i],dp1[col][i]) - f(col + 1,poz[col][i]);
if (i + 1 == poz[col].size())
lol2[col][i] = vl;
else
lol2[col][i] = max(lol2[col][i + 1],vl);
}
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
int max_weights(integer N, integer M, vector<integer> X, vector<integer> Y, vector<integer> W)
{
n = N;
m = M;
for (int i = 0; i < m; i++)
X[i]++,Y[i]++;
for (int i = 0; i < m; i++)
a[Y[i]].push_back({X[i],W[i]});
for (int i = 0; i < m; i++)
poz[Y[i]].push_back(X[i] - 1);
for (int i = 1; i <= n; i++)
{
poz[i].push_back(n);
sort(poz[i].begin(),poz[i].end());
}
for (int i = 1; i <= n; i++)
{
sort(a[i].begin(),a[i].end());
sp[i].resize(a[i].size());
if (a[i].size() == 0)
continue;
sp[i][0] = a[i][0].second;
for (int j = 1; j < sp[i].size(); j++)
sp[i][j] = sp[i][j - 1] + a[i][j].second;
}
for (int i = 1; i <= n; i++)
{
int szz = poz[i].size();
dp0[i].resize(szz);
dp1[i].resize(szz);
mp_dp0[i].resize(szz);
mp_dp1[i].resize(szz);
ms_dp0[i].resize(szz);
ms_dp1[i].resize(szz);
lol1[i].resize(szz);
lol2[i].resize(szz);
}
///pentru coloana 1, dp-urile sunt 0, doar dau build care imi face chestiile auxiliare
//cout << 1 << endl;
build(1);
//cout << 2 << endl;
int ans = 0;
for (int i = 2; i <= n; i++)
{
//cout << f(1,2) << ' ' << lol1[1][0] << endl;
for (int j = 0; j < poz[i].size(); j++)
{
int hpmax = max_idx(i - 1,poz[i][j]);
if (hpmax != -1)
{
dp0[i][j] = max(dp0[i][j],mp_dp0[i - 1][hpmax]);
dp0[i][j] = max(dp0[i][j],f(i - 1,poz[i][j]) + lol1[i - 1][hpmax]);
}
hpmax++;
if (hpmax != poz[i - 1].size())
dp0[i][j] = max(dp0[i][j],lol2[i - 1][hpmax] - f(i,poz[i][j]));
}
for (int j = 0; j < poz[i].size(); j++)
{
int hpmax = max_idx(i - 1,poz[i][j]);
if (hpmax != -1)
{
dp1[i][j] = max(dp1[i][j],mp_dp0[i - 1][hpmax]);
dp1[i][j] = max(dp1[i][j],f(i - 1,poz[i][j]) + lol1[i - 1][hpmax]);
}
hpmax++;
if (hpmax != poz[i - 1].size())
dp1[i][j] = max(dp1[i][j],max(ms_dp0[i - 1][hpmax],ms_dp1[i - 1][hpmax]));
}
for (int j = 0; j < poz[i].size(); j++)
ans = max(ans,max(dp0[i][j],dp1[i][j]));
if (i != n)
build(i);
}
return ans;
}
/**
Daca am pus pana la i, si vreau sa pun la i + 1, am pretty much cateva cazuri:
-daca pun mai jos decat era la i, atunci nu mi se vor mai aduna alea pana unde am pus la i+1
-daca pun mai sus decat era la i, iar am doua cazuri:
-daca pun mai jos decat era la i - 1, nu se intampla mare lucru
-daca pun mai sus decat era la i - 1, e ca si cum as lua toti pestii de la h[i] la h[i + 1], dar sa nu ii fi considerat la i - 1 ofc
In dp-ul curent (pana la i) consider doar ce iau de la 1 la i (eventual, fara i deoarece sunt pe ultimul caz si iau cu urmatorul)
dp0[i][h] = costul de pana la i, daca consider si i ca fiind full pus, si i are inaltimea h (relativ la el)
dp1[i][h] = costul de pana la i, dar cand nu consider i, pentru ca ma bazez ca o sa imi vina i + 1 mai mare
dp0[i][h] vine din doua cazuri:
-daca h' (inaltimea lui i - 1) <= h atunci am dp0[i - 1][h'] si dp1[i - 1][h'] + f(i - 1,h) - f(i - 1,h')
Retin maxime pe prefix din dp0[i][h] si maxime pe prefix din dp1[i][h] - f(i,h)
-daca h' > h, atunci am dp0[i - 1][h'] + f(i,h') - f(i,h) si dp1[i - 1][h'] + f(i,h') - f(i,h)
Retin maxime pe sufix din dp0[i][h] + f(i + 1,h) si maxime pe sufix din dp1[i][h] + f(i + 1,h)
dp1[i][h] vine si el din doua cazuri:
-daca h' <= h atunci am dp0[i - 1][h'] si dp1[i - 1][h'] + f(i - 1,h) - f(i - 1,h')
Cazul e identic cu primul caz de la dp0[i][h]
-daca h' > h, doar am dp0[i - 1][h'] si dp1[i - 1][h']
Retin maxime pe sufix din dp0[i][h] si din dp1[i][h]
h-urile relevante pentru col i sunt (linia unui peste de pe i) - 1 si n, deci total vor fi O(N + M) stari
Sortez si caut binar chestii deci am total O((N + M)log(N + M))
**/
Compilation message
fish.cpp: In function 'long long int max_idx(long long int, long long int)':
fish.cpp:24:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if (st + pas < poz[col].size() and poz[col][st + pas] <= h)
| ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_idx_2(long long int, long long int)':
fish.cpp:36:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if (st + pas < a[col].size() and a[col][st + pas].first <= h)
| ~~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp: In function 'void build(long long int)':
fish.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 0; i < poz[col].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | if (i + 1 == poz[col].size())
| ~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < poz[col].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:90:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if (i + 1 == poz[col].size())
| ~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(integer, integer, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:127:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (int j = 1; j < sp[i].size(); j++)
| ~~^~~~~~~~~~~~~~
fish.cpp:150:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int j = 0; j < poz[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:159:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | if (hpmax != poz[i - 1].size())
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:162:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (int j = 0; j < poz[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:171:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | if (hpmax != poz[i - 1].size())
| ~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:174:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for (int j = 0; j < poz[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
105 ms |
59972 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '24806294221656' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
26204 KB |
Output is correct |
| 2 |
Incorrect |
135 ms |
66384 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '46804015619258' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
54360 KB |
Output is correct |
| 2 |
Correct |
47 ms |
54356 KB |
Output is correct |
| 3 |
Incorrect |
77 ms |
58852 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
26204 KB |
Output is correct |
| 2 |
Correct |
4 ms |
26144 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
26264 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
26204 KB |
Output is correct |
| 2 |
Correct |
4 ms |
26144 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
26264 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
26204 KB |
Output is correct |
| 2 |
Correct |
4 ms |
26144 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
26264 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
54360 KB |
Output is correct |
| 2 |
Correct |
47 ms |
54356 KB |
Output is correct |
| 3 |
Incorrect |
77 ms |
58852 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
105 ms |
59972 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '24806294221656' |
| 2 |
Halted |
0 ms |
0 KB |
- |
