제출 #332454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332454		dolphingarlic	Bigger segments (IZhO19_segments)	C++14	100 / 100	93 ms	12016 KiB

segments

#include <stdio.h>

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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