Submission #627738

#TimeUsernameProblemLanguageResultExecution timeMemory
627738YomapeedCatfish Farm (IOI22_fish)C++17
44 / 100
1097 ms82668 KiB
#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")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...