| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1168469 | jj_master | 메기 농장 (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ins insert
int max_weights(int N, int M, vector<int> &X, vector<int> &Y, vector<int> &W)
{
map<int, vector<pair<int, int>>> catfish_in_coloumn;
for(int i = 0; i < M; i++) {
catfish_in_coloumn[X[i]].pb({Y[i], W[i]});
}
for(auto &entry : catfish_in_coloumn) {
sort(entry.se.begin(), entry.se.end());
}
vector<int> dp(N, 0);
for(int col = 0; col < N; col++) {
if(col > 0) {
dp[col] = dp[col - 1];
}
int catfish_caught = 0;
for(auto &fish : catfish_in_coloumn[col]) {
int row = fish.fi;
int weight = fish.se;
bool can_be_caught = false;
if(col > 0) {
bool caught_from_left = true;
for(auto &left_fish : catfish_in_coloumn[col - 1]) {
if(left_fish.fi == row) {
caught_from_left = false;
break;
}
}
if(caught_from_left) can_be_caught = true;
}
if(col < N - 1) {
bool caught_from_right = true;
for(auto &right_fish : catfish_in_coloumn[col + 1]) {
if(right_fish.fi == row) {
caught_from_right = false;
break;
}
}
if(caught_from_right) can_be_caught = true;
}
if(can_be_caught) {
catfish_caught += weight;
}
}
if(col > 0) {
dp[col] = max(dp[col], dp[col - 1] + catfish_caught);
} else {
dp[col] = max(dp[col], catfish_caught);
}
}
return dp[N - 1];
}