oj.uz

Submission #530396

# Submission time Handle Problem Language Result Execution time Memory
530396 2022-02-25T09:38:08 Z jiahng Cigle (COI21_cigle) C++14
48 / 100
 1000 ms 366244 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MOD 1000000007
#define maxn 5001
//~ #define getchar_unlocked _getchar_nolock

int N,D[maxn],ss[maxn];

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

vpi A[maxn];
int dp[maxn][maxn],R[maxn][maxn];

struct node{
	int s,e,m,v=0, lazy=0;
	node *l,*r;
	node (int ss,int ee){
		s = ss; e = ee; m = (s + e) / 2;
		if (s != e){
			l = new node(s,m); r = new node(m+1,e);
		}
	}
	void prop(){
		if (lazy == 0 || s == e) return;
		l->lazy = max(l->lazy, lazy); r->lazy = max(r->lazy, lazy);
		l->v = max(l->v, lazy); r->v = max(r->v, lazy);
		lazy = 0;
	}
	void upd(int a,int b,int c){
		prop();
		if (a <= s && e <= b){
			v = max(v, c); lazy = max(lazy, c);
		}else if (a > e || s > b) return;
		else{
			l->upd(a,b,c); r->upd(a,b,c); v = max(v, c);
		}
	}
	int qry(int p){
		prop();
		if (s == e) return v;
		else if (p > m) return r->qry(p);
		else return l->qry(p);
	}
}*root;

int32_t main() {
    fast;
    N = readInt();
    FOR(i,1,N){
		D[i] = readInt();
		ss[i] = ss[i-1] + D[i];
	}
    mem(R, -1);
	FOR(l,2,N) FOR(r,l+1,N-1) if ((ss[l-1] + ss[r]) % 2 == 0){
		int ssb = (ss[l-1] + ss[r]) / 2;
		int b = lower_bound(ss+l,ss+r,ssb) - ss;
		if (ss[b] == ssb ){
			//~ cout << l-1 << ' ' << b << ' ' << r << '\n';
			A[b].pb(pi(l-1,r));
		}
	}
	FOR(i,1,N) sort(all(A[i]), greater <pi>());
	
	root = new node(0,N);
	
	DEC(i,N,1){
		FOR(k,0,A[i].size()-1){
			int newdp = dp[max(i,A[i][k].s+1)][i] + k + 1;
			root->upd(0, A[i][k].f - 1, newdp);
		}
		FOR(j,0,N) dp[i][j] = root->qry(j);
	}
			//~ FOR(j,0,i-1) {
				//~ dp[i][j] = dp[i+1][j];
				
		//~ if (A[i][k].f > j){ // Range update max dp[i][j] from j from 0 to A[i][k].f
			//~ dp[i][j] = max(dp[i][j], newdp);
		//~ }
	//~ }
	cout << dp[1][0];
	
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196232 KB Output is correct
2 Correct 71 ms 196240 KB Output is correct
3 Correct 77 ms 196276 KB Output is correct
4 Correct 73 ms 196184 KB Output is correct
5 Correct 75 ms 196276 KB Output is correct
6 Correct 74 ms 196256 KB Output is correct
7 Correct 79 ms 196288 KB Output is correct
8 Correct 89 ms 196292 KB Output is correct
9 Correct 75 ms 196172 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196232 KB Output is correct
2 Correct 71 ms 196240 KB Output is correct
3 Correct 77 ms 196276 KB Output is correct
4 Correct 73 ms 196184 KB Output is correct
5 Correct 75 ms 196276 KB Output is correct
6 Correct 74 ms 196256 KB Output is correct
7 Correct 79 ms 196288 KB Output is correct
8 Correct 89 ms 196292 KB Output is correct
9 Correct 75 ms 196172 KB Output is correct
10 Correct 75 ms 196608 KB Output is correct
11 Correct 75 ms 196508 KB Output is correct
12 Correct 81 ms 196616 KB Output is correct
13 Correct 81 ms 196640 KB Output is correct
14 Correct 75 ms 196504 KB Output is correct
15 Correct 84 ms 196548 KB Output is correct
16 Correct 76 ms 196532 KB Output is correct
17 Correct 80 ms 196508 KB Output is correct
18 Correct 90 ms 196500 KB Output is correct
19 Correct 76 ms 196516 KB Output is correct
20 Correct 77 ms 196596 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 200900 KB Output is correct
2 Correct 91 ms 201248 KB Output is correct
3 Correct 85 ms 201092 KB Output is correct
4 Correct 87 ms 201120 KB Output is correct
5 Correct 86 ms 201284 KB Output is correct
6 Correct 87 ms 201180 KB Output is correct
7 Correct 87 ms 201108 KB Output is correct
8 Correct 106 ms 201160 KB Output is correct
9 Correct 99 ms 201124 KB Output is correct
10 Correct 89 ms 201068 KB Output is correct
11 Correct 91 ms 201012 KB Output is correct
12 Correct 89 ms 200996 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196232 KB Output is correct
2 Correct 71 ms 196240 KB Output is correct
3 Correct 77 ms 196276 KB Output is correct
4 Correct 73 ms 196184 KB Output is correct
5 Correct 75 ms 196276 KB Output is correct
6 Correct 74 ms 196256 KB Output is correct
7 Correct 79 ms 196288 KB Output is correct
8 Correct 89 ms 196292 KB Output is correct
9 Correct 75 ms 196172 KB Output is correct
10 Correct 75 ms 196608 KB Output is correct
11 Correct 75 ms 196508 KB Output is correct
12 Correct 81 ms 196616 KB Output is correct
13 Correct 81 ms 196640 KB Output is correct
14 Correct 75 ms 196504 KB Output is correct
15 Correct 84 ms 196548 KB Output is correct
16 Correct 76 ms 196532 KB Output is correct
17 Correct 80 ms 196508 KB Output is correct
18 Correct 90 ms 196500 KB Output is correct
19 Correct 76 ms 196516 KB Output is correct
20 Correct 77 ms 196596 KB Output is correct
21 Correct 86 ms 200900 KB Output is correct
22 Correct 91 ms 201248 KB Output is correct
23 Correct 85 ms 201092 KB Output is correct
24 Correct 87 ms 201120 KB Output is correct
25 Correct 86 ms 201284 KB Output is correct
26 Correct 87 ms 201180 KB Output is correct
27 Correct 87 ms 201108 KB Output is correct
28 Correct 106 ms 201160 KB Output is correct
29 Correct 99 ms 201124 KB Output is correct
30 Correct 89 ms 201068 KB Output is correct
31 Correct 91 ms 201012 KB Output is correct
32 Correct 89 ms 200996 KB Output is correct
33 Correct 98 ms 200928 KB Output is correct
34 Correct 94 ms 200980 KB Output is correct
35 Correct 85 ms 201012 KB Output is correct
36 Correct 91 ms 201300 KB Output is correct
37 Correct 86 ms 201156 KB Output is correct
38 Correct 89 ms 201188 KB Output is correct
39 Correct 85 ms 200476 KB Output is correct
40 Correct 82 ms 200220 KB Output is correct
41 Correct 85 ms 200232 KB Output is correct
42 Correct 104 ms 200208 KB Output is correct
43 Correct 84 ms 200284 KB Output is correct
44 Correct 82 ms 200160 KB Output is correct
45 Correct 81 ms 200268 KB Output is correct
46 Correct 81 ms 200196 KB Output is correct
47 Correct 98 ms 200164 KB Output is correct
48 Correct 103 ms 200260 KB Output is correct
49 Correct 86 ms 200216 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196232 KB Output is correct
2 Correct 71 ms 196240 KB Output is correct
3 Correct 77 ms 196276 KB Output is correct
4 Correct 73 ms 196184 KB Output is correct
5 Correct 75 ms 196276 KB Output is correct
6 Correct 74 ms 196256 KB Output is correct
7 Correct 79 ms 196288 KB Output is correct
8 Correct 89 ms 196292 KB Output is correct
9 Correct 75 ms 196172 KB Output is correct
10 Correct 75 ms 196608 KB Output is correct
11 Correct 75 ms 196508 KB Output is correct
12 Correct 81 ms 196616 KB Output is correct
13 Correct 81 ms 196640 KB Output is correct
14 Correct 75 ms 196504 KB Output is correct
15 Correct 84 ms 196548 KB Output is correct
16 Correct 76 ms 196532 KB Output is correct
17 Correct 80 ms 196508 KB Output is correct
18 Correct 90 ms 196500 KB Output is correct
19 Correct 76 ms 196516 KB Output is correct
20 Correct 77 ms 196596 KB Output is correct
21 Correct 86 ms 200900 KB Output is correct
22 Correct 91 ms 201248 KB Output is correct
23 Correct 85 ms 201092 KB Output is correct
24 Correct 87 ms 201120 KB Output is correct
25 Correct 86 ms 201284 KB Output is correct
26 Correct 87 ms 201180 KB Output is correct
27 Correct 87 ms 201108 KB Output is correct
28 Correct 106 ms 201160 KB Output is correct
29 Correct 99 ms 201124 KB Output is correct
30 Correct 89 ms 201068 KB Output is correct
31 Correct 91 ms 201012 KB Output is correct
32 Correct 89 ms 200996 KB Output is correct
33 Correct 98 ms 200928 KB Output is correct
34 Correct 94 ms 200980 KB Output is correct
35 Correct 85 ms 201012 KB Output is correct
36 Correct 91 ms 201300 KB Output is correct
37 Correct 86 ms 201156 KB Output is correct
38 Correct 89 ms 201188 KB Output is correct
39 Correct 85 ms 200476 KB Output is correct
40 Correct 82 ms 200220 KB Output is correct
41 Correct 85 ms 200232 KB Output is correct
42 Correct 104 ms 200208 KB Output is correct
43 Correct 84 ms 200284 KB Output is correct
44 Correct 82 ms 200160 KB Output is correct
45 Correct 81 ms 200268 KB Output is correct
46 Correct 81 ms 200196 KB Output is correct
47 Correct 98 ms 200164 KB Output is correct
48 Correct 103 ms 200260 KB Output is correct
49 Correct 86 ms 200216 KB Output is correct
50 Execution timed out 1114 ms 366244 KB Time limit exceeded
51 Halted 0 ms 0 KB -