Submission #1006391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006391		christinelynn	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	344 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++)
  {
    dp[i]=dp[pos[i]]+1;
//    dp[i]=max(dp[i-1], dp[i]);
    ll pt=lower_bound(pref+1, pref+n+1, 2*pref[i]-pref[max(pos[i], pos[i]-1)])-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: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27