Submission #485171

#	Time	Username	Problem	Language	Result	Execution time	Memory
485171		MilosMilutinovic	Bigger segments (IZhO19_segments)	C++14	100 / 100	85 ms	14964 KiB

segments

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define ll long long
using namespace std;

int n;
int niz[500005];
ll pref[500005];
int dp[500005];
int pos[500005];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	ff(i,1,n)cin >> niz[i];
	ff(i,1,n)pref[i] = pref[i - 1] + niz[i];
	ff(i,1,n){
		pos[i] = max(pos[i], pos[i - 1]);
		dp[i] = dp[pos[i]] + 1;
		int ind = lower_bound(pref + 1, pref + n + 1, pref[i] * 2 - pref[pos[i]]) - pref;
		if(ind <= n)pos[ind] = max(pos[ind], i);
	}
	cout << dp[n];
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
segments.cpp:19:2: note: in expansion of macro 'ff'
   19 |  ff(i,1,n)cin >> niz[i];
      |  ^~
segments.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
segments.cpp:20:2: note: in expansion of macro 'ff'
   20 |  ff(i,1,n)pref[i] = pref[i - 1] + niz[i];
      |  ^~
segments.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
segments.cpp:21:2: note: in expansion of macro 'ff'
   21 |  ff(i,1,n){
      |  ^~

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