Submission #344690

#TimeUsernameProblemLanguageResultExecution timeMemory
344690RakhmandBigger segments (IZhO19_segments)C++14
27 / 100
1593 ms46716 KiB
// // A.cpp // torelax // // Created by Rakhman on 1/5/21. // #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <iterator> #define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0); #define S second #define F first #define pb push_back #define nl '\n' #define NL cout << '\n'; #define EX exit(0) #define all(s) s.begin(), s.end() #define no_answer {cout << "NO"; exit(0);} #define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k) const long long mxn = 1e6 + 110; const long long mnn = 3e3 + 2; const long long mod = 1e9 + 7; const long long inf = 1e18; const long long OO = 1e9 + 100; typedef long long llong; typedef unsigned long long ullong; using namespace std; llong n, b[mxn], dp[mnn][mnn]; int main() { cin >> n; for(int i = 1; i <= n; i++){ cin >> b[i]; } for(int i = 0; i <= n; i++){ for(int j = 0; j <= i; j++){ dp[i][j] = inf; } } dp[0][0] = 0; for(int i = 1; i <= n; i++){ llong sum = b[i]; for(int j = i - 1; j >= 1; j--){ for(int k = 1; k <= j; k++){ if(dp[j][k] == inf) break; if(sum >= dp[j][k]){ dp[i][k + 1] = min(dp[i][k + 1], sum); } } sum += b[j]; } dp[i][1] = min(dp[i][1], sum); } for(int i = n; i >= 1; i--){ if(dp[n][i] != inf) return cout << i, 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...