Submission #1116134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116134		SalihSahin	Cigle (COI21_cigle)	C++14	20 / 100	1054 ms	2384 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);

int add(pair<int, int> f1, pair<int, int> f2){
   int l = f1.first, r = f1.second, x = f2.second;

   vector<int> v1, v2;
   int val = 0;
   for(int i = r; i > l; i--){
      val += a[i];
      v1.pb(val);
   }
   val = 0;
   for(int i = r+1; i < x; i++){
      val += a[i];
      v2.pb(val);
   }

   int ans = 0;
   int ind2 = 0;
   for(int i = 0; i < v1.size(); i++){
      while(ind2 < v2.size() && v2[ind2] < v1[i]) ind2++;
      if(ind2 < v2.size() && v2[ind2] == v1[i]) ans++;
   }

   return ans;
}

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];
   }
   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}, {r+1, x}));
         }
      }
      ans = max(ans, dp[l][n-1]);
   }

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

Compilation message (stderr)

cigle.cpp: In function 'long long int add(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
cigle.cpp:28:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int i = 0; i < v1.size(); i++){
      |                   ~~^~~~~~~~~~~
cigle.cpp:29:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |       while(ind2 < v2.size() && v2[ind2] < v1[i]) ind2++;
      |             ~~~~~^~~~~~~~~~~
cigle.cpp:30:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |       if(ind2 < v2.size() && v2[ind2] == v1[i]) ans++;
      |          ~~~~~^~~~~~~~~~~

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