Submission #384337

#	Time	Username	Problem	Language	Result	Execution time	Memory
384337		patrikpavic2	Bigger segments (IZhO19_segments)	C++17	100 / 100	159 ms	21972 KiB

segments

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

#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];
priority_queue < 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);
	}
	int ndp = 0; ll npr = 0;
	for(int i = 0;i < n;i++){
		while(!pri.empty() && -pri.top().X.X <= P[i]){
			if(pri.top().X.Y > npr){
				npr = pri.top().X.Y;
				ndp = pri.top().Y;
			}
			pri.pop();
		}	
		dp[i] = ndp + 1;
		pri.push({{-(2LL * P[i] - npr), P[i]}, dp[i]});
	}
	printf("%d\n", dp[n - 1]);
	return 0;
}

Compilation message (stderr)

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

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