Submission #1058831

#TimeUsernameProblemLanguageResultExecution timeMemory
1058831underwaterkillerwhaleCatfish Farm (IOI22_fish)C++17
0 / 100
1092 ms578700 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (int)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e5 + 7; const int Mod = 1e9 + 7; const ll INF = 2e9 + 7; const ll BASE = 137; const int szBL = 320; void inline maximize (ll &A, ll B) { if (A < B) A = B; } struct Fish { int fs, se; ll W; }; int n, m; vector<ll> pcur[N], Left[N], Right[N], dp[N], fsuf[N], fpre[N]; vector<pll> high[N]; Fish a[(int)3e5 + 7]; void init (int j, int m) { pcur[j].resize(m + 2, 0); Left[j].resize(m + 2, 0); Right[j].resize(m + 2, 0); fpre[j].resize(m + 2, 0); fsuf[j].resize(m + 2, 0); dp[j].resize(m + 2, 0); ///sửa ik } //void solution () { ll max_weights(int _n, int _m, vector<int> X, vector<int> Y, vector<int> W) { // cin >> n >> m; n = _n; m = _m; rep (i, 1, m) { // cin >> a[i].fs >> a[i].se >> a[i].W; a[i].fs = X[i - 1]; a[i].se = Y[i - 1]; a[i].W = W[i - 1]; ++a[i].fs; ++a[i].se; high[a[i].fs].pb(MP(a[i].se, a[i].W)); } high[0] = {MP(0, 0)}; init(0, 5); rep (j, 1, n) { iter (&id, high[j - 1]) high[j].pb(MP(id.fs, 0)); iter (&id, high[j + 1]) high[j].pb(MP(id.fs, 0)); high[j].pb(MP(0, 0)); sort (ALL(high[j])); high[j].resize(unique(ALL(high[j])) - high[j].begin()); int m = SZ(high[j]); init(j, m); rep (i, 1, m - 1){ pcur[j][i] = pcur[j][i - 1] + high[j][i].se; } rep (i, 1, m - 1) { int pos = lower_bound(ALL(high[j - 1]), MP(high[j][i].fs, 0LL)) - high[j - 1].begin(); Left[j][i] = pcur[j - 1][pos]; } } rep (j, 1, n - 1) { int m = SZ(high[j]); rep (i, 1, m - 1) { int pos = lower_bound(ALL(high[j + 1]), MP(high[j][i].fs, 0LL)) - high[j + 1].begin(); Right[j][i] = pcur[j + 1][pos]; } } rep (j, 1, n) { int m = SZ(high[j]); vector<pll> &ch = high[j]; dp[j][0] = *max_element(dp[j - 1].begin(), dp[j - 1].end()); if (j == n) { rep (i, 1, SZ(high[j - 1]) - 1) { maximize(dp[j][0], dp[j - 1][i] + Right[j - 1][i]); } } if (j == 2) { rep (i, 1, m - 1) { dp[j][i] = Left[j][i]; } } if (j > 2) { rep (i, 1, m - 1) { int pos = upper_bound(ALL(high[j - 2]), MP(ch[i].fs, INF)) - high[j - 2].begin(); maximize(dp[j][i], fpre[j - 2][pos - 1] + Left[j][i]); maximize(dp[j][i], fsuf[j - 2][pos]); } ll premx = 0; rep (i, 1, SZ(high[j - 1]) - 1) { premx = max(premx, dp[j - 1][i] - pcur[j - 1][i]); } rep (i, 1, m - 1) { maximize(dp[j][i], Left[j][i] + premx); } } if (j > 3) { ll premx = 0; rep (i, 1, SZ(high[j - 3]) - 1) { premx = max(premx, dp[j - 3][i] + Right[j - 3][i]); } rep (i, 1, m - 1) { maximize(dp[j][i], Left[j][i] + premx); } } fpre[j][0] = dp[j][0]; rep (i, 1, m - 1) { fpre[j][i] = max(fpre[j][i - 1], dp[j][i]); } reb (i, m - 1, 0) { fsuf[j][i] = max(fsuf[j][i + 1], dp[j][i] + Right[j][i]); } // rep (i, 1, m - 1) { // cout << j << " "<<high[j][i].fs <<" "<< dp[j][i] <<"\n"; // } } // cout << *max_element(dp[n].begin(), dp[n].end()) <<"\n"; return *max_element(dp[n].begin(), dp[n].end()); } //#define file(name) freopen(name".inp","r",stdin); \ //freopen(name".out","w",stdout); //int main () { //// file("c"); // ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); // int num_Test = 1; //// cin >> num_Test; // while (num_Test--) //// solution(); // cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}); //} /* no bug challenge +2 2 + 8 * 2 - 9 5 4 0 2 5 1 1 2 4 4 1 3 3 3 */

Compilation message (stderr)

fish.cpp:140:1: warning: multi-line comment [-Wcomment]
  140 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
#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...