Submission #627738

#	Time	Username	Problem	Language	Result	Execution time	Memory
627738		Yomapeed	Catfish Farm (IOI22_fish)	C++17	44 / 100	1097 ms	82668 KiB

fish

#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]);
    }
    
    map<pair<int, int>, ll> score;
    for(int i = 0; i < m; i++){
        score[{x[i], y[i]}] = w[i];
    }
    map<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);
        map<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]);
            }
        }
        map<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;
        // }
    }
    assert(sum <= 300000);
    ll ans = 0;
    for(auto [a, b] : L){
        chmax(ans, b);
        // cout << a << " : " << b << endl;
        chmax(ans, R[a]);
    }
    return ans;
}

Compilation message (stderr)

fish.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
fish.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16