Submission #238589

#	Time	Username	Problem	Language	Result	Execution time	Memory
238589		Aydarov03	Bigger segments (IZhO19_segments)	C++14	0 / 100	135 ms	262144 KiB

segments

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define fr first
#define sc second
#define int long long
using namespace std;

// ~30 points
const int N  = 3005;

int dp[N][N];
int pref[N], a[N];

void mk(int &a, int other) {
  if (a == 0) {
    a = other;
  } else if (a < other) {
    a = other;
  }
}

int get_sum(int l, int r) {
  if (l > r) {
    return 1e18;
  }
  return pref[r] - pref[l - 1];
}

struct T {
  int tree[N][N * 4]; // i | group
  int lz[N][N * 4];
  T () {
    memset (tree, -1, sizeof tree);
    memset (lz, 0, sizeof lz);
  }
  void push(int i, int v, int tl, int tr) {
    if (lz[i][v]) {
      if (tl != tr) {
        mk(lz[i][v + v], lz[i][v]);
        mk(lz[i][v + v + 1], lz[i][v]);
      } else {
        if (tree[i][v] == -1) {
          tree[i][v] = 1e18;
        }
        tree[i][v] = min(tree[i][v], get_sum(lz[i][v], tl));
      }
      lz[i][v] = 0;
    }
  }
  void upd(int i, int l, int r, int val, int v = 1, int tl = 1, int tr = N) {
    push(i, v, tl, tr);
    if (l <= tl && tr <= r) {
      lz[i][v] = val;
//      cout << "push " << i << " " << tl << " " << tr << " : " << val << endl;
      push(i, v, tl, tr);
      return;
    }
    if (l > tr || tl > r) {
      return;
    }
    int mid = tl + tr >> 1;
    upd(i, l, r, val, v + v, tl, mid);
    upd(i, l, r, val, v + v + 1, mid + 1, tr);
  }
  void kek(int i, int pos, int val, int v = 1, int tl = 1, int tr = N) {
    if (tl == tr) {
      tree[i][v] = val;
      return;
    }
    int mid = tl + tr >> 1;
    if (pos <= mid) {
      kek(i, pos, val, v + v, tl, mid);
    } else {
      kek(i, pos, val, v + v + 1, mid + 1, tr);
    }
  }
  int get(int i, int pos, int v = 1, int tl = 1, int tr = N) {
    push(i, v, tl, tr);
    if (tl == tr) {
      return tree[i][v];
    }
    int mid = tl + tr >> 1;
    if (pos <= mid) {
      return get(i, pos, v + v, tl, mid);
    } else {
      return get(i, pos, v + v + 1, mid + 1, tr);
    }
  }
} DP;

main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    pref[i] = pref[i - 1] + a[i];
  }

  for (int lst = 1; lst <= n; lst++) {
    DP.kek(1, lst, pref[lst]);
  }
  for (int gr = 1; gr < n; gr++) {
    for (int i = gr; i <= n; i++) {
      int best = DP.get(gr, i);
      if (best == -1) {
        continue;
      }
      if (best > get_sum(i + 1, n)) {
        continue;
      }
      int l = i, r = n + 1;
      while (r - l > 1) {
        int mid = l + r >> 1;
        if (get_sum(i + 1, mid) >= best) {
          r = mid;
        } else {
          l = mid;
        }
      }
      if (r <= n) {
        DP.upd(gr + 1, r, n, i + 1);
      }
    }
  }

  int ans = 0;
  for (int gr = 3000; gr >= 1; gr--) {
    if (DP.get(gr, n) != -1) {
      ans = gr;
      break;
    }
  }
  cout << ans;
}

Compilation message (stderr)

segments.cpp: In member function 'void T::upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
segments.cpp:62:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1;
               ~~~^~~~
segments.cpp: In member function 'void T::kek(long long int, long long int, long long int, long long int, long long int, long long int)':
segments.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1;
               ~~~^~~~
segments.cpp: In member function 'long long int T::get(long long int, long long int, long long int, long long int, long long int)':
segments.cpp:83:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1;
               ~~~^~~~
segments.cpp: At global scope:
segments.cpp:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
segments.cpp: In function 'int main()':
segments.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
segments.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &a[i]);
     ~~~~~^~~~~~~~~~~~~~~
segments.cpp:27:16: warning: array subscript is above array bounds [-Warray-bounds]
   return pref[r] - pref[l - 1];
          ~~~~~~^
segments.cpp:27:16: warning: array subscript is above array bounds [-Warray-bounds]
   return pref[r] - pref[l - 1];
          ~~~~~~^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27