Submission #1116274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116274		SalihSahin	Cigle (COI21_cigle)	C++14	48 / 100	1004 ms	145220 KiB

cigle

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
 
const int N = 5e3 + 5;
 
vector<int> a(N);

struct SEGT{
   vector<int> tree, lazy;

   void init(int n){
      tree.assign(4*n, 0);
      lazy.assign(4*n, 0);
   }

   void push(int ind){
      if(lazy[ind] == 0) return;

      lazy[ind*2] += lazy[ind];
      tree[ind*2] += lazy[ind];
      lazy[ind*2+1] += lazy[ind];
      tree[ind*2+1] += lazy[ind];
      lazy[ind] = 0;
   }

   void build(int ind, int l, int r, vector<int> &a){
      if(l == r){
         tree[ind] = a[l];
      }
      else{
         int m = (l + r)/2;

         build(ind*2, l, m, a);
         build(ind*2+1, m+1, r, a);
         tree[ind] = max(tree[ind*2], tree[ind*2+1]);
      }
   }

   void update(int ind, int l, int r, int ql, int qr, int val){
      if(l > r || r < ql || l > qr || ql > qr) return;
      if(l >= ql && r <= qr){
         tree[ind] += val;
         lazy[ind] += val;
      }
      else{
         push(ind);
         int m = (l + r)/2;

         update(ind*2, l, m, ql, qr, val);
         update(ind*2+1, m+1, r, ql, qr, val);
         tree[ind] = max(tree[ind*2], tree[ind*2+1]);
      }
   }

   int query(int ind, int l, int r, int ql, int qr){
      if(l > r || r < ql || l > qr || ql > qr) return 0;
      if(l >= ql && r <= qr){
         return tree[ind];
      }
      else{
         push(ind);
         int m = (l + r)/2;

         return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
      }
   }
};
 
 
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);
   // dp[son kat l][son kat r] -> dp[r + 1][x] + match({l, r} , {r+1, x});
   int n;
   cin>>n;
   for(int i = 1; i <= n; i++){
      cin>>a[i];
   }

   vector<pair<int, int> > upd[n+5];

   for(int i = 2; i <= n-1; i++){
      vector<pair<int, int> > v1, v2;
 
      int val = 0;
      for(int j = i; j > 1; j--){
         val += a[j];
         v1.pb({val, j});
      }
 
      val = 0;
      for(int j = i+1; j <= n-1; j++){
         val += a[j];
         v2.pb({val, j});
      }
 
      int ind2 = 0;
      for(int j = 0; j < v1.size(); j++){
         while(ind2 < v2.size() && v2[ind2].first < v1[j].first) ind2++;
         if(ind2 < v2.size() && v2[ind2].first == v1[j].first){
            upd[i].pb({v2[ind2].second, v1[j].second});
         }
      }
   }
 
   vector<vector<int> > dp(n+5, vector<int>(n+5));

   for(int r = 1; r <= n-1; r++){
      sort(upd[r].begin(), upd[r].end());
      int updind = 0;

      SEGT seg;
      seg.init(r);
      vector<int> a(r+1);
      for(int i = 1; i <= r; i++) a[i] = dp[i][r];
      seg.build(1, 1, r, a);

      for(int x = r+1; x <= n; x++){
         while(updind < upd[r].size() && upd[r][updind].first < x){
            seg.update(1, 1, r, 1, upd[r][updind].second-1, 1);
            updind++;
         }

         dp[r+1][x] = seg.tree[1];
      }
   }

   int ans = 0;
   for(int i = 1; i <= n; i++){
      ans = max(ans, dp[i][n]);
   }
   cout<<ans<<endl;
   return 0;
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |       for(int j = 0; j < v1.size(); j++){
      |                      ~~^~~~~~~~~~~
cigle.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |          while(ind2 < v2.size() && v2[ind2].first < v1[j].first) ind2++;
      |                ~~~~~^~~~~~~~~~~
cigle.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |          if(ind2 < v2.size() && v2[ind2].first == v1[j].first){
      |             ~~~~~^~~~~~~~~~~
cigle.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |          while(updind < upd[r].size() && upd[r][updind].first < x){
      |                ~~~~~~~^~~~~~~~~~~~~~~

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