#include "fish.h"
#include <vector>
#include <algorithm>
#include <iostream>
#define int long long
using namespace std;
vector<pair<int, int>> adj[100005];
vector<pair<int, int>> prf[100005];
const long long inf = 1e18;
int _N;
int get_prfsum(int X, int to)
{
if (X <= 0 || _N+1 <= X) return 0;
return (*--lower_bound(prf[X].begin(), prf[X].end(), make_pair(to, inf))).second;
}
vector<int> dp[100005][3];
vector<int> suf[100005];
vector<int> prf0[100005], prf1[100005], suf0[100005];
vector<int> cpx[100005];
long long max_weights(signed N, signed M, std::vector<signed> X, std::vector<signed> Y,
std::vector<signed> W) {
_N= N;
for (int i = 0; i < M; i++) {
adj[X[i]+1].push_back(make_pair(Y[i] + 2, W[i]));
}
for (int i = 1; i <= N; i++) sort(adj[i].begin(), adj[i].end());
for (int i = 1; i <= N; i++) {
prf[i].resize(adj[i].size() + 1);
prf[i][0] = make_pair(0, 0);
for (int k = 1; k <= adj[i].size(); k++) {
prf[i][k] = make_pair(adj[i][k-1].first, adj[i][k-1].second + prf[i][k-1].second);
}
}
cpx[0].push_back(0);
for (int i = 1; i <= N; i++) {
cpx[i].push_back(0);
for (pair<int, int> p:adj[i]) cpx[i].push_back(p.first - 1);
cpx[i].push_back(N+1);
}
for (int i = 1; i <= N; i++) {
dp[i][0].resize(cpx[i].size());
dp[i][1].resize(cpx[i].size());
dp[i][2].resize(cpx[i-1].size());
suf[i].resize(dp[i][0].size());
prf0[i].resize(dp[i][0].size());
prf1[i].resize(dp[i][2].size());
suf0[i].resize(dp[i][2].size());
}
for (int i = 2; i <= N; i++) {
for (int j = 0; j < (int)dp[i-1][2].size(); j++) dp[i][2][0] = max(dp[i][2][0], dp[i-1][2][j]);
for (int j = 1; j < (int)dp[i][2].size(); j++) {
dp[i][2][j] = max(dp[i-1][0][j], dp[i-1][1][j]) + get_prfsum(i, cpx[i-1][j]);
}
for (int j = 1; j < (int)dp[i][1].size(); j++) {
int height = cpx[i][j]; //height까지 끌어올리기
//height보다 더 '큰' 최초의 인덱스 k를 찾자
int low = upper_bound(cpx[i-1].begin(), cpx[i-1].end(), height) - cpx[i-1].begin();
if (low == cpx[i-1].size()) {
dp[i][1][j] = -inf;
continue;
}
dp[i][1][j] = suf[i-1][low] - get_prfsum(i, cpx[i][j]);
}
for (int j = 1; j < (int)dp[i][0].size(); j++) {
int ord = upper_bound(cpx[i-1].begin(), cpx[i-1].end(), cpx[i][j]) - cpx[i-1].begin();
int M1 = ord == 1 ? -inf : (prf0[i][ord-1] + get_prfsum(i-1, cpx[i][j]));
int ord2 = upper_bound(cpx[i-2].begin(), cpx[i-2].end(), cpx[i][j]) - cpx[i-2].begin();
ord2--;
int M2 = prf1[i-1][ord2] + get_prfsum(i-1, cpx[i][j]);
int M3 = i == 2 ? -inf : suf0[i-1][ord2+1];
dp[i][0][j] = max({M1, M2, M3});
}
for (int j = 1; j < (int)dp[i][1].size(); j++) {
prf0[i][j] = dp[i][0][j] - get_prfsum(i, cpx[i][j]);
suf[i][j] = max(dp[i][0][j], dp[i][1][j]) + get_prfsum(i+1, cpx[i][j]);
}
for (int j = 0; j < (int)dp[i][2].size(); j++) {
prf1[i][j] = dp[i][2][j] - get_prfsum(i, cpx[i-1][j]);
suf0[i][j] = dp[i][2][j];
}
for (int j = 2; j < (int)dp[i][1].size(); j++) prf0[i][j] = max(prf0[i][j], prf0[i][j-1]);
for (int j = 1; j < (int)dp[i][2].size(); j++) prf1[i][j] = max(prf1[i][j], prf1[i][j-1]);
for (int j = (int)dp[i][2].size() - 2; j >= 0; j--) suf0[i][j] = max(suf0[i][j], suf0[i][j+1]);
for (int j = (int)dp[i][1].size() - 2; j >= 1; j--) suf[i][j] = max(suf[i][j], suf[i][j+1]);
}
int ans = 0;
for (int i = 1; i < (int)dp[N][0].size(); i++) ans = max(ans, dp[N][0][i]);
for (int i = 1; i < (int)dp[N][1].size(); i++) ans = max(ans, dp[N][1][i]);
for (int i = 0; i < (int)dp[N][2].size(); i++) ans = max(ans, dp[N][2][i]);
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:32:23: 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]
32 | for (int k = 1; k <= adj[i].size(); k++) {
| ~~^~~~~~~~~~~~~~~~
fish.cpp:60:17: 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]
60 | if (low == cpx[i-1].size()) {
| ~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
105 ms |
59940 KB |
Output is correct |
| 2 |
Correct |
128 ms |
65376 KB |
Output is correct |
| 3 |
Correct |
71 ms |
51880 KB |
Output is correct |
| 4 |
Correct |
71 ms |
51860 KB |
Output is correct |
| 5 |
Incorrect |
240 ms |
90312 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '149814460808466' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
1st lines differ - on the 1st token, expected: '2', found: '33' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
70 ms |
51920 KB |
Output is correct |
| 2 |
Correct |
71 ms |
52044 KB |
Output is correct |
| 3 |
Incorrect |
90 ms |
54604 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '21049836049923' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
1st lines differ - on the 1st token, expected: '3', found: '33' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
1st lines differ - on the 1st token, expected: '3', found: '33' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
1st lines differ - on the 1st token, expected: '3', found: '33' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
70 ms |
51920 KB |
Output is correct |
| 2 |
Correct |
71 ms |
52044 KB |
Output is correct |
| 3 |
Incorrect |
90 ms |
54604 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '21049836049923' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
105 ms |
59940 KB |
Output is correct |
| 2 |
Correct |
128 ms |
65376 KB |
Output is correct |
| 3 |
Correct |
71 ms |
51880 KB |
Output is correct |
| 4 |
Correct |
71 ms |
51860 KB |
Output is correct |
| 5 |
Incorrect |
240 ms |
90312 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '149814460808466' |
| 6 |
Halted |
0 ms |
0 KB |
- |
