Submission #1015605

#TimeUsernameProblemLanguageResultExecution timeMemory
1015605elitewantsyouBigger segments (IZhO19_segments)C++14
27 / 100
43 ms2396 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second const int N = 505; const int mod = 998244353; using namespace std; const long long inf = 1e18; int n; int a[N]; long long s[N]; long long d[N][N]; int main() { ios_base::sync_with_stdio(0); #ifdef zxc freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i - 1] + a[i]; d[0][i] = inf; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { d[i][j] = inf; } d[i][1] = s[i]; for (int j = 2; j <= i; j++) { for (int h = i; h >= 1; h--) { if (d[h - 1][j - 1] <= s[i] - s[h - 1]) { d[i][j] = min(d[i][j], s[i] - s[h - 1]); } } if (d[i][j] == inf) { break; } /* if (d[i][j - 1] < d[i][j]) { cout << i << " " << j << " " << d[i][j - 1] << " " << d[i][j] << "\n"; exit(0); } */ assert (d[i][j] <= d[i][j - 1]); } } int res = n; while (d[n][res] == inf) { res -= 1; } cout << res << "\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...