Submission #908622

#	Time	Username	Problem	Language	Result	Execution time	Memory
908622		bobbilyking	Catfish Farm (IOI22_fish)	C++17	0 / 100	68 ms	42096 KiB

fish

#include "fish.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)


long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  vector<vl> fishes(N+1);
  vector<vl> states(N+1, {0});
  // initializing states
  F(i, 0, M) {
    ++Y[i];
    F(j, max(X[i]-1, 0), min(X[i]+1, N-1) + 1) 
        states[j].push_back(Y[i]);
  }

    // rank reduction and correction, i suppose
  F(i, 0, N+1) {
    sort(A(states[i]));
    states[i].erase(unique(A(states[i])), states[i].end());
    fishes[i].resize(states[i].size());
  }

  // 
  F(i, 0, M) {
    int x = X[i];
    int y = lower_bound(A(states[x]), Y[i]) - states[x].begin();
    fishes[x][y] += W[i];
  }

  vector<vl> dp_up(N+1), dp_down(N+1);
  F(i, 1, N+1) {
    int sz = states[i].size();
    dp_up[i].assign(sz, 0);
    dp_down[i].assign(sz, 0);

    if (i > 1) {
        ll best = max(dp_up[i-2][0], dp_down[i-2][0]), sum = 0;
        for (int j = 0, lef = 0, mid = 0; j < sz; ++j) {
            while (lef+1 < (int)states[i-2].size() && states[i-2][lef+1] <= states[i][j]) {
            ++lef;
            while (mid+1 < (int)states[i-1].size() && states[i-1][mid+1] <= states[i-2][lef]) {
                ++mid;
                best += fishes[i-1][mid];
                sum += fishes[i-1][mid];
            }
            best = max(best, max(dp_up[i-2][lef], dp_down[i-2][lef]) + sum);
            }
            dp_up[i][j] = max(dp_up[i][j], best);
        }
    }
    if (i > 1) {
        ll best = 0, sum = accumulate(fishes[i-1].begin(), fishes[i-1].end(), 0LL);
        for (int j = sz-1, lef = states[i-2].size(), mid = states[i-1].size(); j >= 0; --j) {
            while (lef > 0 && states[i-2][lef-1] >= states[i][j]) {
            --lef;
            while (mid > 0 && states[i-1][mid-1] > states[i-2][lef]) {
                --mid;
                sum -= fishes[i-1][mid];
            }
            best = max(best, max(dp_up[i-2][lef], dp_down[i-2][lef]) + sum);
            }
            dp_up[i][j] = max(dp_up[i][j], best);
        }
    }   

    if (i > 0) {
        ll best = dp_up[i-1][0], sum = 0;
        for (int j = 0, lef = 0; j < sz; ++j) {
            while (lef+1 < (int)states[i-1].size() && states[i-1][lef+1] <= states[i][j]) {
            ++lef;
            best += fishes[i-1][lef];
            best = max(best, dp_up[i-1][lef]);
            }
            dp_up[i][j] = max(dp_up[i][j], best);
        }
    }
    
    if (i > 0) {
        ll best = 0, sum = accumulate(fishes[i].begin(), fishes[i].end(), 0LL);
        for (int j = sz-1, lef = states[i-1].size(); j >= 0; --j) {
            while (lef > 0 && states[i-1][lef-1] >= states[i][j]) {
            --lef;
            best = max(best, max(dp_down[i-1][lef], dp_up[i-1][lef]) + sum);
            }
            dp_down[i][j] = max(dp_down[i][j], best-sum);
            sum -= fishes[i][j];
        }
    }
  }

  return max(dp_up[N][0], dp_down[N][0]);
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:87:34: warning: unused variable 'sum' [-Wunused-variable]
   87 |         ll best = dp_up[i-1][0], sum = 0;
      |                                  ^~~

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