# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1002960 |
2024-06-19T21:40:00 Z |
teesla |
Cigle (COI21_cigle) |
C++17 |
|
14 ms |
1440 KB |
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
vector<int> tam(n+1, 0);
vector<int> sum(n+1, 0);
for(int i=1; i<=n; i++) cin >> tam[i];
for(int i=1; i<=n; i++) sum[i] = sum[i-1] + tam[i];
vector<vector<int>> dp(n+1, vector<int> (n+1,0));
int maior = 0;
for(int l = 1; l<= n; l++) for(int r = l; r<=n; r++){
int somaPedaco = sum[r-1] - sum[l-1];
if(somaPedaco >= sum[l-1]) continue;
int qnt = 0;
int cima = l, baixo = l-1;
int SumCima = tam[l];
int SumBaixo = tam[l-1];
while(cima < r){
if(SumCima == SumBaixo) {
qnt++;
baixo--;
cima++;
SumBaixo+= tam[baixo];
SumCima+= tam[cima];
}
else if(SumCima > SumBaixo) {baixo--; SumBaixo+= tam[baixo];}
else{ cima++; SumCima += tam[cima];}
}
//cout << l << ' '<< r << ' '<< qnt << endl;
for(int oo = baixo; oo>=1; oo--){
dp[l][r] = max(dp[l][r], dp[oo][l-1] + qnt);
}
maior = max(maior, dp[l][r]);
}
// for(int i=1; i<=n; i++){
// for(int j=1; j<=n; j++) cout << dp[i][j] << ' ';
// cout << endl;
// }
cout << maior << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
1372 KB |
Output is correct |
2 |
Correct |
13 ms |
1368 KB |
Output is correct |
3 |
Correct |
14 ms |
1368 KB |
Output is correct |
4 |
Correct |
13 ms |
1440 KB |
Output is correct |
5 |
Correct |
13 ms |
1440 KB |
Output is correct |
6 |
Incorrect |
13 ms |
1372 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |