oj.uz

Submission #344636

# Submission time Handle Problem Language Result Execution time Memory
344636 2021-01-06T06:53:20 Z naj1sss Bigger segments (IZhO19_segments) C++17
27 / 100
 1500 ms 3436 KB 
#include <bits/stdc++.h>
/*
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <set>
#include <cmath>
#include <cstring>

#include <stdio.h>
#include <string.h>
#include <sstream>
#include <stdlib.h>
#include <vector>
#include <iomanip>
#include <ctime>
*/
#define nl "\n"
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define p_un(a) ((void)a)
#define p_st(a) string(a)
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define naj ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define NL cout << endl;
#define sqr(x) (sqrt(x) * 1LL)
#define pcnt(i) __builtin_popcount(i)
#define up_b upper_bound
#define low_b lower_bound
#define lcm(a,b) (a * b) / __gcd(a, b)
#define REVERSE(a, n) reverse(a + 1, a + n + 1);
#define SORT(a, n) sort(a + 1, a + n + 1);
#define rsz resize

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ul;
typedef vector <ll> vl;
typedef vector <bool> vb;
typedef vector <char> vc;
typedef vector <int> vi;
typedef vector <string> vs;
typedef pair <ll, ll> pll;
typedef map <ll, ll> mll;
typedef set <ll> sl;
typedef set <char> sc;
typedef map <string, ll> msl;
typedef map <string, bool> msb;
typedef map <char, ll> mcl;
typedef map <string, string> mss;
typedef vector <vl> vvl;

const ll mxn = 4e5 + 1;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);

#define int int64_t
#define FLN "LOL"

//int dx[]= {1,0,-1,0}; int dy[]= {0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1}; int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2}; int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[]={-1,-1,+0,+1,+1,+0}; int dy[]={-1,+1,+2,+1,-1,-2}; //Hexagonal Direction

inline void joji(bool ok = 0) {naj;if(ok){freopen(FLN".in","r",stdin);freopen(FLN".out","w",stdout);}}

int ans = 1;
int a[mxn], sum[mxn], dp[3001][3001];

signed main () {

	joji();
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[1][i] = 1;
		sum[i] = sum[i - 1] + a[i];
	}	
	for(int i = 1; i <= n; i++) 
		for(int j = i; j <= n; j++) 
			for(int k = j + 1; k <= n; k++)
				if(sum[k] - sum[j] >= sum[j] - sum[i - 1] && dp[i][j])
					dp[j + 1][k] = max(dp[j + 1][k], dp[i][j] + 1);				

	for(int i = 1; i <= n; i++) 
		for(int j = i; j <= n; j++) ans = max(ans, dp[i][j]);
	cout << ans;
	return 0;
}

Compilation message

segments.cpp: In function 'void joji(bool)':
segments.cpp:76:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   76 | inline void joji(bool ok = 0) {naj;if(ok){freopen(FLN".in","r",stdin);freopen(FLN".out","w",stdout);}}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~
segments.cpp:76:78: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   76 | inline void joji(bool ok = 0) {naj;if(ok){freopen(FLN".in","r",stdin);freopen(FLN".out","w",stdout);}}
      |                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 35 ms 364 KB Output is correct
17 Correct 37 ms 2924 KB Output is correct
18 Correct 37 ms 3180 KB Output is correct
19 Correct 45 ms 2432 KB Output is correct
20 Correct 35 ms 3436 KB Output is correct
21 Correct 37 ms 3180 KB Output is correct
22 Correct 20 ms 2540 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 37 ms 3180 KB Output is correct
25 Correct 37 ms 3292 KB Output is correct
26 Correct 36 ms 3308 KB Output is correct
27 Correct 36 ms 2924 KB Output is correct
28 Correct 38 ms 3328 KB Output is correct
29 Correct 36 ms 3308 KB Output is correct
30 Correct 35 ms 3308 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 35 ms 364 KB Output is correct
17 Correct 37 ms 2924 KB Output is correct
18 Correct 37 ms 3180 KB Output is correct
19 Correct 45 ms 2432 KB Output is correct
20 Correct 35 ms 3436 KB Output is correct
21 Correct 37 ms 3180 KB Output is correct
22 Correct 20 ms 2540 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 37 ms 3180 KB Output is correct
25 Correct 37 ms 3292 KB Output is correct
26 Correct 36 ms 3308 KB Output is correct
27 Correct 36 ms 2924 KB Output is correct
28 Correct 38 ms 3328 KB Output is correct
29 Correct 36 ms 3308 KB Output is correct
30 Correct 35 ms 3308 KB Output is correct
31 Execution timed out 1576 ms 620 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 35 ms 364 KB Output is correct
17 Correct 37 ms 2924 KB Output is correct
18 Correct 37 ms 3180 KB Output is correct
19 Correct 45 ms 2432 KB Output is correct
20 Correct 35 ms 3436 KB Output is correct
21 Correct 37 ms 3180 KB Output is correct
22 Correct 20 ms 2540 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 37 ms 3180 KB Output is correct
25 Correct 37 ms 3292 KB Output is correct
26 Correct 36 ms 3308 KB Output is correct
27 Correct 36 ms 2924 KB Output is correct
28 Correct 38 ms 3328 KB Output is correct
29 Correct 36 ms 3308 KB Output is correct
30 Correct 35 ms 3308 KB Output is correct
31 Execution timed out 1576 ms 620 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 35 ms 364 KB Output is correct
17 Correct 37 ms 2924 KB Output is correct
18 Correct 37 ms 3180 KB Output is correct
19 Correct 45 ms 2432 KB Output is correct
20 Correct 35 ms 3436 KB Output is correct
21 Correct 37 ms 3180 KB Output is correct
22 Correct 20 ms 2540 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 37 ms 3180 KB Output is correct
25 Correct 37 ms 3292 KB Output is correct
26 Correct 36 ms 3308 KB Output is correct
27 Correct 36 ms 2924 KB Output is correct
28 Correct 38 ms 3328 KB Output is correct
29 Correct 36 ms 3308 KB Output is correct
30 Correct 35 ms 3308 KB Output is correct
31 Execution timed out 1576 ms 620 KB Time limit exceeded
32 Halted 0 ms 0 KB -