# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
402657 | Ruxandra985 | Bigger segments (IZhO19_segments) | C++14 | 126 ms | 14948 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define DIMN 500010
using namespace std;
pair <int, int> dp[DIMN];
int v[DIMN];
long long sp[DIMN];
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , st , dr , mid;
fscanf (fin,"%d",&n);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d",&v[i]);
sp[i] = v[i] + sp[i - 1];
dp[i] = make_pair(1 , 1);/// o secventa, incepe la 1 si se termina la i
}
for (i = 1 ; i <= n ; i++){
if (i > 1){
/// 1. iei o sg secventa de la 1 la i, initializat
/// 2. prelungesti cu 1 secventa de la i - 1
if (dp[i].first < dp[i - 1].first || (dp[i].first == dp[i - 1].first && dp[i].second < dp[i - 1].second)){
dp[i].first = dp[i - 1].first;
dp[i].second = dp[i - 1].second;
}
}
/// acuma ma duc in unele mai mari
st = i + 1;
dr = n;
while (st <= dr){
mid = (st + dr)/2;
if (sp[mid] - sp[i] >= sp[i] - sp[dp[i].second - 1]) /// e ok
dr = mid - 1;
else st = mid + 1;
}
/// solutia in st
if (dp[st].first < dp[i].first + 1 || (dp[st].first == dp[i].first + 1 && i + 1 > dp[st].second)){
dp[st].first = dp[i].first + 1;
dp[st].second = i + 1;
}
}
fprintf (fout,"%d",dp[n].first);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |