Submission #924207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924207	2024-02-08T16:19:18 Z	vjudge1	Cat Exercise (JOI23_ho_t4)	C++17	14 / 100	2000 ms	45744 KB

Main

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto edu:v)cout<<edu<<" "; cout<<"\n"
#define MAX(a,b) a=max(a,b)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=5005;

ll dp[MAXN][MAXN];
const ll K=18;
ll st[K][1ll<<K];
ll a[MAXN];
ll n;

ll oper(ll i, ll j){
	if(i==-1)return j;
	if(j==-1)return i;
	if(a[i]>a[j])return i;
	return j;
}

void st_init(){
	fore(i,0,n)st[0][i]=i;
	fore(k,1,K)fore(i,0,n-(1ll<<k)+1){
		//if(i+(1ll<<k-1)>=n)break;
		st[k][i]=oper(st[k-1][i],st[k-1][i+(1ll<<(k-1))]);
	}
}

ll st_query(ll s, ll e){
	if(e-s==0)return -1;
	ll k=63-__builtin_clzll(e-s);
	return oper(st[k][s],st[k][e-(1ll<<k)]);
}

int main(){FIN;
	cin>>n;
	fore(i,0,n)cin>>a[i],a[i]--;
	st_init();
	fore(r,1,n+1)for(ll l=n-1;l>=0;l--){
		if(r-l<=1)continue;
		ll k=st_query(l,r);
		fore(t,l,r){
			if(t<k)MAX(dp[l][r],dp[t+1][r]);
			if(t>k)MAX(dp[l][r],dp[l][t]);
			if(t==k){
				ll k1=st_query(l,k),k2=st_query(k+1,r);
				//cout<<l<<","<<r<<" "<<k<<": "<<k1<<" "<<k2<<": ";
				if(oper(k1,k2)==k1)MAX(dp[l][r],dp[l][k]+k-k1);//,cout<<"1\n";
				else MAX(dp[l][r],dp[k+1][r]+k2-k);//,cout<<"2\n";
			}
		}
	}
	cout<<dp[0][n]<<"\n";
	return 0;
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	8540 KB	Output is correct
5	Correct	1 ms	8540 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	8540 KB	Output is correct
5	Correct	1 ms	8540 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	9 ms	18268 KB	Output is correct
12	Correct	9 ms	18268 KB	Output is correct
13	Correct	9 ms	18268 KB	Output is correct
14	Correct	9 ms	18268 KB	Output is correct
15	Correct	9 ms	18396 KB	Output is correct
16	Correct	9 ms	18268 KB	Output is correct
17	Correct	9 ms	18268 KB	Output is correct

Subtask #3
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	8540 KB	Output is correct
5	Correct	1 ms	8540 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	9 ms	18268 KB	Output is correct
12	Correct	9 ms	18268 KB	Output is correct
13	Correct	9 ms	18268 KB	Output is correct
14	Correct	9 ms	18268 KB	Output is correct
15	Correct	9 ms	18396 KB	Output is correct
16	Correct	9 ms	18268 KB	Output is correct
17	Correct	9 ms	18268 KB	Output is correct
18	Execution timed out	2055 ms	45744 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	8540 KB	Output is correct
5	Correct	1 ms	8540 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	9 ms	18268 KB	Output is correct
12	Correct	9 ms	18268 KB	Output is correct
13	Correct	9 ms	18268 KB	Output is correct
14	Correct	9 ms	18268 KB	Output is correct
15	Correct	9 ms	18396 KB	Output is correct
16	Correct	9 ms	18268 KB	Output is correct
17	Correct	9 ms	18268 KB	Output is correct
18	Execution timed out	2055 ms	45744 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	8540 KB	Output is correct
5	Correct	1 ms	8540 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	9 ms	18268 KB	Output is correct
12	Correct	9 ms	18268 KB	Output is correct
13	Correct	9 ms	18268 KB	Output is correct
14	Correct	9 ms	18268 KB	Output is correct
15	Correct	9 ms	18396 KB	Output is correct
16	Correct	9 ms	18268 KB	Output is correct
17	Correct	9 ms	18268 KB	Output is correct
18	Execution timed out	2055 ms	45744 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Incorrect	4 ms	15708 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	1 ms	8540 KB	Output is correct
5	Correct	1 ms	8540 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	9 ms	18268 KB	Output is correct
12	Correct	9 ms	18268 KB	Output is correct
13	Correct	9 ms	18268 KB	Output is correct
14	Correct	9 ms	18268 KB	Output is correct
15	Correct	9 ms	18396 KB	Output is correct
16	Correct	9 ms	18268 KB	Output is correct
17	Correct	9 ms	18268 KB	Output is correct
18	Execution timed out	2055 ms	45744 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Submission #924207

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 7.0

Subtask #4 0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 7.0

Subtask #4
0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0