| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 627741 | 2022-08-12T21:02:32 Z | Yomapeed | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KB |
#include "fish.h"
#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999
#define pb push_back
#define ff first
#define ss second
#define printclock cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<<"ms\n";
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll B) { return (unsigned ll)rng() % B;}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void chmax(ll &a, ll b){
a = max(a, b);
}
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<int>> adj(n);
for(int i = 0; i < m; i++){
adj[x[i]].pb(y[i]);
}
gp_hash_table<pair<int, int>, ll> score;
for(int i = 0; i < m; i++){
score[{x[i], y[i]}] = w[i];
}
gp_hash_table<ll, ll> L, R, S;
L[-1] = R[-1] = 0;
S[-1] = 0;
ll sum = 0;
for(int i = 0; i < n; i++){
set<int> nys, nyx;
nys.insert(-1);
for(auto u : adj[i]){
nys.insert(u);
}
nyx = nys;
if(i) {
for(auto [a, b] : L){
nys.insert(a);
}
for(auto u : adj[i - 1]){
nyx.insert(u);
}
}
if(i + 1 < n){
for(auto u : adj[i + 1]){
nys.insert(u);
nyx.insert(u);
}
}
vector<int> ny;
for(auto u : nys) ny.pb(u);
gp_hash_table<ll, ll> nL, nR, nS, nSS;
for(auto u : ny){
nS[u] += score[{i, u}];
nSS[u] = S[u];
}
int p = -1;
nSS = S;
ll mmx = 0;
for(auto [a, b] : nS){
chmax(mmx, nSS[a]);
if(p != -1){
nS[a] += nS[p];
nSS[a] = mmx;
}
p = a;
}
S = nSS;
{
//Case 1.1
ll mx = -INF;
for(auto j : ny){
if(i){
chmax(mx, L[j]);
}
chmax(nL[j], mx);
}
}
{
//Case 1.2
ll mx = -INF;
for(int k = ny.size() - 1; k >= 0; k--){
int j = ny[k];
chmax(nL[j], mx - nS[j]);
if(i){
chmax(mx, L[j] + nS[j]);
}
}
}
{
//Case 2.1
ll mx = -INF;
for(auto j : ny){
if(i){
chmax(mx, R[j] - S[j]);
}
chmax(nL[j], mx + S[j]);
}
}
{
//Case 2.2
ll mx = -INF;
for(int k = ny.size() - 1; k >= 0; k--){
int j = ny[k];
chmax(nL[j], mx - nS[j]);
if(i){
chmax(mx, R[j] + nS[j]);
}
}
}
{
//Case 3.1
ll mx = -INF;
for(auto j : ny){
chmax(mx, L[j]);
}
for(auto j : ny){
chmax(nR[j], mx);
}
}
{
//Case 4.1
ll mx = -INF;
for(auto j : ny){
chmax(mx, R[j] - S[j]);
chmax(nR[j], mx + S[j]);
}
}
{
//Case 4.2
ll mx = -INF;
for(int k = ny.size() - 1; k >= 0; k--){
int j = ny[k];
chmax(nR[j], mx);
chmax(mx, R[j]);
}
}
gp_hash_table<ll,ll> nnL, nnR, nnS;
for(auto u : nyx){
nnL[u] = nL[u];
nnR[u] = nR[u];
nnS[u] = nS[u];
}
swap(L, nnL);
swap(R, nnR);
swap(S, nnS);
sum += L.size();
// cout << i << " $$$$$$$$$$$$$$$$$$$$$" << endl;
// for(auto [a, b] : L){
// cout << a << " : " << b << " " << R[a] << endl;
// }
}
ll ans = 0;
for(auto [a, b] : L){
chmax(ans, b);
// cout << a << " : " << b << endl;
chmax(ans, R[a]);
}
return ans;
}