Submission #1116166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116166		SalihSahin	Cigle (COI21_cigle)	C++14	48 / 100	1059 ms	279388 KiB

cigle

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int inf = 1e16;
const int N = 5e3 + 5;

vector<int> a(N);
vector<pair<int, int> > prec[N];

int add(int l, int r, int x){
   if(!prec[r].size() || (prec[r][0].first <= l || prec[r][0].second >= x)) return 0;

   int lb = 0, rb = prec[r].size()-1;
   while(lb < rb){
      int mid = (lb + rb + 1)/2;

      if(prec[r][mid].first > l && prec[r][mid].second < x) lb = mid;
      else rb = mid - 1;
   }

   return lb + 1;
}


int32_t 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 = 0; i < n; i++){
      cin>>a[i];
   }

   for(int i = 1; i < n-1; i++){
      vector<pair<int, int> > v1, v2;

      int val = 0;
      for(int j = i; j > 0; 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){
            prec[i].pb({v1[j].second, v2[ind2].second});
         }
      }
   }

   vector<vector<int> > dp(n, vector<int>(n, -inf));
   for(int i = 0; i < n; i++){
      dp[0][i] = 0;
   }

   int ans = 0;
   for(int l = 0; l < n; l++){
      for(int r = l; r < n; r++){
         for(int x = r+1; x < n; x++){
            dp[r+1][x] = max(dp[r+1][x], dp[l][r] + add(l, r, x));
         }
      }
      ans = max(ans, dp[l][n-1]);
   }

   cout<<ans<<endl;
   return 0;
}

Compilation message (stderr)

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

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