Submission #384336

#	Time	Username	Problem	Language	Result	Execution time	Memory
384336		patrikpavic2	Bigger segments (IZhO19_segments)	C++17	37 / 100	1592 ms	3684 KiB

segments

#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 5e5 + 500;

int A[N], n, dp[N];
ll P[N];
vector < pair < pair < ll, ll > , int > > pri;

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
		P[i] = A[i] + (i ? P[i - 1] : 0LL);
	}
	pri.PB({{0, 0}, 0});
	for(int i = 0;i < n;i++){
		int naj = 0;
		for(int j = 1;j < (int)pri.size();j++)
			if(P[i] >= pri[j].X.X && pri[j].X.Y > pri[naj].X.Y)
				naj = j;
		dp[i] = pri[naj].Y + 1;
		pri.PB({{2LL * P[i] - pri[naj].X.Y, P[i]}, dp[i]});
	}
	printf("%d\n", dp[n - 1]);
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
segments.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

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