Submission #570208

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
570208	2022-05-28T20:24:24 Z	KingJt	Mountains (NOI20_mountains)	C++17	70 / 100	2000 ms	7380 KB

Mountains

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define bn binary_search
#define sz(x) int((x).size())
#define lz(x) long long((x).size())
#define INF 1000000007
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ll> vl;
typedef pair<ll,ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<pair<int,ii>> gw;
typedef vector<pair<ll,il>> lw;
typedef vector<vc> vvc;
void solve(){
	ll n;
	cin>>n;
	vl in(n);
	bool ban1=true,ban2=true;
	for(ll i=0;i<n;i++){
		cin>>in[i];
		if(i>0){
			if(in[i]<in[i-1]) ban1=false;
		}
		if(in[i]>1) ban2=false;
	}
	if(ban1){
		cout<<0<<endl;
		return;
	}
	if(ban2){
		vl a(n,0);
		for(ll i=1;i<n-1;i++){
			if(!in[i-1]){
				a[i]=a[i-1]+1;
			}else a[i]=a[i-1];
		}
		vl b(n,0);
		for(ll i=n-2;i>=1;i--){
			if(!in[i+1]) b[i]=b[i+1]+1;
			else b[i]=b[i+1];
		}
		/*for(ll i=0;i<n;i++){
			cout<<a[i]<<" ";
		}
		cout<<endl;
		for(ll i=0;i<n;i++){
			cout<<b[i]<<" ";
		}*/
		ll ans=0;
		for(ll i=0;i<n;i++){
			if(in[i]){
				ans+=a[i]*b[i];
			}
		}
		cout<<ans<<endl;
		return;
	}
	ll ans=0;
	for(ll i=1;i<n-1;i++){
		ll left=0,right=0;
		for(ll j=0;j<n;j++){
			if(j<i&&in[i]>in[j]){
				left++;
			}else if(j>i&&in[i]>in[j]) right++;
		}
		ans+=left*right;
	}	
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	46 ms	2644 KB	Output is correct
3	Correct	62 ms	2656 KB	Output is correct
4	Correct	57 ms	2656 KB	Output is correct
5	Correct	53 ms	2660 KB	Output is correct
6	Correct	46 ms	2660 KB	Output is correct
7	Correct	46 ms	2656 KB	Output is correct
8	Correct	52 ms	2644 KB	Output is correct
9	Correct	48 ms	2644 KB	Output is correct
10	Correct	46 ms	2656 KB	Output is correct

Subtask #2

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	7244 KB	Output is correct
2	Correct	27 ms	7284 KB	Output is correct
3	Correct	26 ms	7252 KB	Output is correct
4	Correct	22 ms	7380 KB	Output is correct
5	Correct	24 ms	7380 KB	Output is correct
6	Correct	23 ms	7284 KB	Output is correct
7	Correct	22 ms	7336 KB	Output is correct
8	Correct	14 ms	2680 KB	Output is correct
9	Correct	17 ms	2676 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #3

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	7244 KB	Output is correct
2	Correct	27 ms	7284 KB	Output is correct
3	Correct	26 ms	7252 KB	Output is correct
4	Correct	22 ms	7380 KB	Output is correct
5	Correct	24 ms	7380 KB	Output is correct
6	Correct	23 ms	7284 KB	Output is correct
7	Correct	22 ms	7336 KB	Output is correct
8	Correct	14 ms	2680 KB	Output is correct
9	Correct	17 ms	2676 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Execution timed out	2069 ms	2644 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

36.0 / 36.0

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

Subtask #5

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	321 ms	380 KB	Output is correct
12	Correct	336 ms	388 KB	Output is correct
13	Correct	332 ms	380 KB	Output is correct
14	Correct	317 ms	376 KB	Output is correct
15	Correct	355 ms	376 KB	Output is correct
16	Correct	324 ms	376 KB	Output is correct
17	Correct	320 ms	380 KB	Output is correct
18	Correct	358 ms	340 KB	Output is correct
19	Correct	321 ms	376 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct

Subtask #6

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	7244 KB	Output is correct
2	Correct	27 ms	7284 KB	Output is correct
3	Correct	26 ms	7252 KB	Output is correct
4	Correct	22 ms	7380 KB	Output is correct
5	Correct	24 ms	7380 KB	Output is correct
6	Correct	23 ms	7284 KB	Output is correct
7	Correct	22 ms	7336 KB	Output is correct
8	Correct	14 ms	2680 KB	Output is correct
9	Correct	17 ms	2676 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Execution timed out	2069 ms	2644 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #7

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	46 ms	2644 KB	Output is correct
3	Correct	62 ms	2656 KB	Output is correct
4	Correct	57 ms	2656 KB	Output is correct
5	Correct	53 ms	2660 KB	Output is correct
6	Correct	46 ms	2660 KB	Output is correct
7	Correct	46 ms	2656 KB	Output is correct
8	Correct	52 ms	2644 KB	Output is correct
9	Correct	48 ms	2644 KB	Output is correct
10	Correct	46 ms	2656 KB	Output is correct
11	Correct	33 ms	7244 KB	Output is correct
12	Correct	27 ms	7284 KB	Output is correct
13	Correct	26 ms	7252 KB	Output is correct
14	Correct	22 ms	7380 KB	Output is correct
15	Correct	24 ms	7380 KB	Output is correct
16	Correct	23 ms	7284 KB	Output is correct
17	Correct	22 ms	7336 KB	Output is correct
18	Correct	14 ms	2680 KB	Output is correct
19	Correct	17 ms	2676 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Execution timed out	2069 ms	2644 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-