| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 630806 | 2022-08-17T06:53:46 Z | JustInCase | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KB |
#include "fish.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>
#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));
#define maxWeights max_weights
const int32_t MAX_N = 1e5;
struct Catfish {
int32_t row;
int32_t id;
mutable int64_t prefSum;
Catfish(int32_t _row, int32_t _id, int32_t w): row(_row), id(_id), prefSum((int64_t) w) {}
bool operator< (const Catfish &other) const {
if(row != other.row) {
return row <= other.row;
}
else {
return id <= other.id;
}
}
};
struct DpState {
int32_t row;
mutable int64_t incrVal, decrVal;
DpState(int32_t _row): row(_row), incrVal(0), decrVal(0) {}
bool operator< (const DpState &other) const {
return row <= other.row;
}
};
int64_t maxWeights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
std::vector<std::set<Catfish>> catfishByColumn(n);
for(int32_t i = 0; i < m; i++) {
catfishByColumn[x[i]].insert(Catfish(y[i], i, w[i]));
}
for(int32_t i = 0; i < n; i++) {
int64_t total = 0;
for(auto &x : catfishByColumn[i]) {
total += (int64_t) x.prefSum;
x.prefSum = total;
}
}
std::vector<std::set<DpState>> dp(n + 1);
for(int32_t i = 0; i <= n; i++) {
if(i > 0 && i != n) {
for(auto &x : catfishByColumn[i - 1]) {
dp[i].insert(DpState(x.row + 1));
}
}
if(i < n - 1) {
for(auto &x : catfishByColumn[i + 1]) {
dp[i].insert(DpState(x.row + 1));
}
}
dp[i].insert(DpState(0));
}
auto getWPrefSum = [&](int32_t column, int32_t row) -> int64_t {
if(column >= n) {
return 0;
}
auto p = catfishByColumn[column].lower_bound(Catfish(row, -1, 0));
if(p == catfishByColumn[column].begin()) {
return 0;
}
p--;
return p->prefSum;
/**
for(auto it = catfishByColumn[column].rbegin(); it != catfishByColumn[column].rend(); it++) {
if(it->row < row) {
return it->prefSum;
}
}
return 0;
*/
};
for(int32_t i = 1; i <= n; i++) {
{ // compute incrVal
auto prevIt = dp[i - 1].begin();
int64_t pref = 0;
for(auto it = dp[i].begin(); it != dp[i].end(); it++) {
while(prevIt != dp[i - 1].end() && prevIt->row <= it->row) {
remax(pref, prevIt->incrVal - getWPrefSum(i - 1, prevIt->row));
prevIt++;
}
it->incrVal = std::max(pref + getWPrefSum(i - 1, it->row), dp[i - 1].begin()->decrVal);
}
}
{ // compute decrVal
auto prevIt = dp[i - 1].rbegin();
int64_t suff = 0;
for(auto it = dp[i].rbegin(); it != dp[i].rend(); it++) {
while(prevIt != dp[i - 1].rend() && prevIt->row >= it->row) {
remax(suff, std::max(prevIt->incrVal, prevIt->decrVal) + getWPrefSum(i, prevIt->row));
prevIt++;
}
it->decrVal = suff - getWPrefSum(i, it->row);
}
}
}
/**
for(int32_t i = 0; i <= n; i++) {
std::cout << i << ": ";
for(auto &x : dp[i]) {
std::cout << "{ " << x.row << ", " << x.incrVal << ", " << x.decrVal << " }, ";
}
std::cout << '\n';
}
*/
return std::max(dp.back().begin()->incrVal, dp.back().begin()->decrVal);
}