Submission #1096871

#TimeUsernameProblemLanguageResultExecution timeMemory
1096871MuhammetBigger segments (IZhO19_segments)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector <int> a(n+1), p(n+1, 0); for(int i = 1; i <= n; i++){ cin >> a[i]; p[i] = p[i-1] + a[i]; } vector <vector <int>> v, v1; v.resize(n+1); v1.resize(n+1); for(int i = 1; i <= n; i++){ long long s = 0; for(int j = i-1; j >= 1; j--){ s += a[j+1]; int t = upper_bound(v[j].begin(), v[j].end(), s) - v[j].begin(); if(t != 0){ v[i].push_back(s); v1[i].push_back(v1[j][t-1]+1); } } s += a[1]; v[i].push_back(s); v1[i].push_back(1); for(int j = 1; j < (int)v1[i].size(); j++){ v1[i][j] = max(v1[i][j],v1[i][j-1]); } } cout << v1[n-1].back()+1; }
#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...