Submission #711215

#	Time	Username	Problem	Language	Result	Execution time	Memory
711215		ToroTN	Bigger segments (IZhO19_segments)	C++14	13 / 100	1 ms	340 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define ll long long
ll n,a[500005],qs[500005],dp[500005],sum[500005],st,md,ed;
ll query(ll l,ll r)
{
    if(l>r)return 0;
    return qs[r]-qs[l-1];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        qs[i]=qs[i-1]+a[i];
    }
    dp[0]=0,sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=1e18,sum[i]=1e18;
    }
    for(int i=1;i<=n;i++)
    {
        st=0;
        ed=i-1;
        while(ed>=st)
        {
            md=(st+ed)/2;
            if(query(md+1,i)>=sum[md])
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
        dp[i]=dp[ed]+1;
        sum[i]=query(ed+1,i);
    }
    //printf("%lld %lld\n",dp[n],sum[n]);
    printf("%lld\n",dp[n]);
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:14:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   14 |     scanf("%d",&n);
      |            ~^  ~~
      |             |  |
      |             |  long long int*
      |             int*
      |            %lld
segments.cpp:17:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   17 |         scanf("%d",&a[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  long long int*
      |                 int*
      |                %lld
segments.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
segments.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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