제출 #687672

#제출 시각아이디문제언어결과실행 시간메모리
687672Matteo_VerzBigger segments (IZhO19_segments)C++17
27 / 100
1585 ms35656 KiB
#include <bits/stdc++.h> #ifdef BLAT #include "debug/debug.hpp" #else #define debug(x...) #endif using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector <int> v(1 + n); vector <long long> sp(1 + n); vector <vector <int>> dp(1 + n, vector <int>(1 + n, -1)); for (int i = 1; i <= n; i++) { cin >> v[i]; sp[i] = sp[i - 1] + v[i]; dp[i][1] = 0; for (int jumps = 2; jumps <= i; jumps++) { for (int j = 1; j < i; j++) { if (dp[j][jumps - 1] != -1 && sp[i] - sp[j] >= sp[j] - sp[dp[j][jumps - 1]]) dp[i][jumps] = j; } } } int maxjumps = 1; for (int i = 1; i <= n; i++) if (dp[n][i] != -1) maxjumps = max(maxjumps, i); cout << maxjumps << '\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...