Submission #1006399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006399		devariaota	Bigger segments (IZhO19_segments)	C++17	100 / 100	63 ms	18852 KiB

segments

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[500005], pos[500005], pref[500005], a[500005];
int main()
{
  ll n;
  scanf("%lld", &n);
  for(int i=1; i<=n; i++)
  {
    scanf("%lld", &a[i]);
    pref[i]=pref[i-1]+a[i];
  }
  pref[n+1]=1e18;
  for(int i=1; i<=n; i++)
  {
    pos[i]=max(pos[i], pos[i-1]);
    dp[i]=dp[pos[i]]+1;
    ll pt=lower_bound(pref+1, pref+n+1, 2*pref[i]-pref[pos[i]])-pref;
//    printf("pos=%lld %lld %lld\n", pos[i], pt, dp[i]);
    pos[pt]=i;
  }
  printf("%lld\n", dp[n]);
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   scanf("%lld", &n);
      |   ~~~~~^~~~~~~~~~~~
segments.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%lld", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27