Submission #707738

#TimeUsernameProblemLanguageResultExecution timeMemory
707738arcaneCigle (COI21_cigle)C++17
20 / 100
1070 ms2260 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define mp make_pair #define pb emplace_back int32_t main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, tot, cnt, ans = 0; cin >> n; int arr[n], pref[n], dp[n][n]; for (int i = 0; i < n; i++) fill(dp[i], dp[i] + n, 0); for (int i = 0; i < n; i++) cin >> arr[i]; for (int s = 0; s < n; s++){ for (int e = s; e < n; e++){ if (s == 0) dp[s][e] = 0; else{ set <int> se; tot = arr[s]; cnt = 0; for (int i = s + 1; i <= e; i++){ se.insert(tot); tot += arr[i]; } tot = 0; for (int i = s - 1; i >= 0; i--){ dp[s][e] = max(dp[s][e], dp[i][s - 1] + cnt); tot += arr[i]; if (se.find(tot) != se.end()) cnt += 1; } } } } for (int i = 0; i < n; i++) ans = max(ans, dp[i][n - 1]); cout << ans; }

Compilation message (stderr)

cigle.cpp: In function 'int32_t main()':
cigle.cpp:12:14: warning: unused variable 'pref' [-Wunused-variable]
   12 |  int arr[n], pref[n], dp[n][n];
      |              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...