Submission #345580

#	Time	Username	Problem	Language	Result	Execution time	Memory
345580		georgerapeanu	Bigger segments (IZhO19_segments)	C++11	73 / 100	24 ms	3180 KiB

segments

#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int n;
int v[NMAX + 5];
long long sum[NMAX + 5];
int bst_pos[NMAX + 5];
int ans[NMAX + 5];

int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;i++){
        scanf("%d",&v[i]);
        sum[i] = sum[i - 1] + v[i];
    }

    for(int i = 1;i <= n;i++){
        bst_pos[i] = max(bst_pos[i],bst_pos[i - 1]);
        ans[i] = ans[bst_pos[i]] + 1;
        int target = (lower_bound(sum + 1,sum + 1 + n,2 * sum[i] - sum[bst_pos[i]]) - sum);
        bst_pos[target] = max(bst_pos[target],i);
    }

    printf("%d\n",ans[n]);

    return 0;
}

Compilation message (stderr)

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

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