Submission #399603

#	Time	Username	Problem	Language	Result	Execution time	Memory
399603		fedoseevtimofey	Cigle (COI21_cigle)	C++14	100 / 100	582 ms	129820 KiB

cigle

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
 
using namespace std;
 
typedef long long ll;

struct triple {
  int i, l, r, score;
};
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector <int> d(n);
  for (int i = 0; i < n; ++i) cin >> d[i];
  vector <ll> pref(n + 1);
  for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] + d[i];
  }
  vector <triple> gs;
  vector <vector <int>> go(n);
  vector <vector <int>> who(n);
  for (int i = 0; i + 1 < n; ++i) {
    int r = 0;
    for (int l = 1; l <= i + 1; ++l) {
      while (r <= n - i - 1 && pref[i + 1] - pref[i + 1 - l] > pref[i + r + 1] - pref[i + 1]) ++r;
      if (pref[i + 1] - pref[i + 1 - l] == pref[i + r + 1] - pref[i + 1] && i + 1 >= l + 1 && (i + 1) + (r + 1) <= n) {
        gs.push_back({i, l, r, (int)go[i].size() + 1});
        //cout << i + 1 << ' ' << l << ' ' << r << ' ' << go[i].size() + 1 << endl;
        int id = (int)gs.size() - 1;
        go[i].push_back(id);
        who[max(0, i - l)].push_back(id);
      }
    }
  }
  vector <int> fen(n);
  vector <int> best((int)gs.size());
  auto modify = [&] (int id, int val) {
    for (; id < n; id |= id + 1) fen[id] = max(fen[id], val);
  };
  auto get = [&] (int r) {
    int res = 0;
    for (; r >= 0; r &= r + 1, --r) {
      res = max(res, fen[r]);
    }
    return res;
  };
  for (int i = 0; i + 1 < n; ++i) {
    for (int id : who[i]) {
      //cout << "get " << gs[id].i - 1 << ' ' << gs[id].score << ' ' << id << endl;
      best[id] = get(gs[id].i - 1) + gs[id].score;
    }
    for (int id : go[i]) {
      //cout << "set " << gs[id].i + gs[id].r << ' ' << best[id] << ' ' << id << endl;
      modify(min(n - 1, gs[id].i + gs[id].r), best[id]);
    }
  } 
  int ans = 0;
  for (auto x : best) ans = max(ans, x);
  cout << ans << '\n';
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 52 / 52