Submission #173472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
173472	2020-01-04T08:35:14 Z	Just_Solve_The_Problem	Bigger segments (IZhO19_segments)	C++11	0 / 100	3 ms	504 KB

segments

#include <bits/stdc++.h>

#define ll long long

using namespace std;          

const int N = (int)5e5 + 7;

int n;
int a[N], dp[N], ind[N];
ll pref[N];

main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		pref[i] = pref[i - 1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1];
		ind[i] = ind[i - 1];
		int l = 0;
		int ok2 = 0;
		for (int j = 0; j < i; j++) {
			if (pref[i] >= 2 * pref[j] - pref[ind[j]]) {
				assert(!ok2);
				l = j;
			} else {
				ok2 = 1;
			}
		}
		dp[i] = dp[l] + 1;
		ind[i] = l;
	}
	// cerr << ind[4] << endl;
	cout << dp[n];
}
/*
4
2 3 1 7
3
 
5
6 2 3 9 13
3

3
3 1 2
2
*/

Compilation message

segments.cpp:13:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
segments.cpp: In function 'int main()':
segments.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
segments.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	292 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	292 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	292 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	292 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	292 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Runtime error	3 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-