oj.uz

Submission #1116134

# Submission time Handle Problem Language Result Execution time Memory
1116134 2024-11-21T09:29:40 Z SalihSahin Cigle (COI21_cigle) C++14
20 / 100
 1000 ms 2384 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 43 ms 336 KB Output is correct
11 Correct 23 ms 336 KB Output is correct
12 Correct 23 ms 336 KB Output is correct
13 Correct 23 ms 336 KB Output is correct
14 Correct 25 ms 556 KB Output is correct
15 Correct 25 ms 336 KB Output is correct
16 Correct 24 ms 504 KB Output is correct
17 Correct 23 ms 336 KB Output is correct
18 Correct 23 ms 556 KB Output is correct
19 Correct 23 ms 336 KB Output is correct
20 Correct 41 ms 336 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 2384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 43 ms 336 KB Output is correct
11 Correct 23 ms 336 KB Output is correct
12 Correct 23 ms 336 KB Output is correct
13 Correct 23 ms 336 KB Output is correct
14 Correct 25 ms 556 KB Output is correct
15 Correct 25 ms 336 KB Output is correct
16 Correct 24 ms 504 KB Output is correct
17 Correct 23 ms 336 KB Output is correct
18 Correct 23 ms 556 KB Output is correct
19 Correct 23 ms 336 KB Output is correct
20 Correct 41 ms 336 KB Output is correct
21 Execution timed out 1054 ms 2384 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 43 ms 336 KB Output is correct
11 Correct 23 ms 336 KB Output is correct
12 Correct 23 ms 336 KB Output is correct
13 Correct 23 ms 336 KB Output is correct
14 Correct 25 ms 556 KB Output is correct
15 Correct 25 ms 336 KB Output is correct
16 Correct 24 ms 504 KB Output is correct
17 Correct 23 ms 336 KB Output is correct
18 Correct 23 ms 556 KB Output is correct
19 Correct 23 ms 336 KB Output is correct
20 Correct 41 ms 336 KB Output is correct
21 Execution timed out 1054 ms 2384 KB Time limit exceeded
22 Halted 0 ms 0 KB -