Submission #332453

#	Time	Username	Problem	Language	Result	Execution time	Memory
332453		dolphingarlic	Bigger segments (IZhO19_segments)	C++14	100 / 100	91 ms	12140 KiB

segments

#include <stdio.h>

long long pref[500001], dp_cost[500001];
int dp_cnt[500001], lptr = 0, rptr = 0, dq[500001];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", pref + i);
        pref[i] += pref[i - 1];
        while (rptr - lptr && pref[i] - pref[dq[lptr + 1]] >= dp_cost[dq[lptr + 1]])
            ++lptr;
        dp_cnt[i] = dp_cnt[dq[lptr]] + 1;
        dp_cost[i] = pref[i] - pref[dq[lptr]];
        while (dp_cost[dq[rptr]] - dp_cost[i] >= pref[i] - pref[dq[rptr]])
            --rptr;
        dq[++rptr] = i;
    }
    printf("%d", dp_cnt[n]);
    return 0;
}

Compilation message (stderr)

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

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