Submission #531429

#TimeUsernameProblemLanguageResultExecution timeMemory
531429mat50013Bigger segments (IZhO19_segments)C++11
0 / 100
1 ms336 KiB
#include <bits/stdc++.h> using namespace std; /* Am un sir de n numere. Trebuie sa-l part in cat mai multe subsecvente astfel inca sumaSubsecv[i] <= sumaSubsecv[i + 1] 6 2 3 9 13 */ using ll = long long; const int NMAX(500005); int v[NMAX], dp[NMAX]; ll sum[NMAX], bestSol[NMAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n; cin >> n; for(int i = 1; i <= n; ++i){ cin >> v[i]; sum[i] = sum[i - 1] + v[i]; } for(int i = 1; i <= n; ++i){ if(bestSol[i] == 0) bestSol[i] = sum[i]; int nxtPz = lower_bound(sum + i + 1, sum + n + 1, sum[i] + bestSol[i]) - sum; if(nxtPz <= n){ dp[nxtPz] = dp[i] + 1; bestSol[nxtPz] = sum[nxtPz] - sum[i]; } } cout << dp[n] + 1 << '\n'; return 0; }
#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...