Submission

PPPPPPPPPP

Score: 100

User: lufychop

Problemset: Fool's Compensation

Language: cpp

Time: 0.006 second

Submitted On: 2025-03-14 15:42:06

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	long long n,t,ans=0;
	cin>>n;
	queue<long long> s;
	vector<long long> dis(n,1000);
	vector<long long> indeg(n,0);
	vector<vector<long long>> adj(n);
	long long a[n];
	cin>>a[0];
	for(int i=1;i<n;i++)
	{
		cin>>a[i];
		if(a[i-1]>a[i])
		{
			adj[i].push_back(i-1);
			indeg[i-1]++;
		}
		else if(a[i-1]<a[i])
		{
			adj[i-1].push_back(i);
			indeg[i]++;
		}
		else
		{
			adj[i].push_back(i-1);
			adj[i-1].push_back(i);
		}
	}
	for(int i=0;i<n;i++)
	{
		if(indeg[i]==0)
		{
			s.push(i);
			while(!s.empty())
			{
				t=s.front();
				s.pop();
				for(int j=0;j<adj[t].size();j++)
				{
					if(a[t]==a[adj[t][j]])
					{
						if(dis[adj[t][j]]<dis[t])
						{
							dis[adj[t][j]]=dis[t];
							s.push(adj[t][j]);
						}
					}
					else if(dis[adj[t][j]]<dis[t]+1000)
					{
						dis[adj[t][j]]=dis[t]+1000;
						s.push(adj[t][j]);
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		ans=ans+dis[i];
	}
	cout<<ans;
	return 0;
}
/*
4
20
25
5
1

20 25 5 1
 0  1 0-1
 2  3 2 1
 
6
49
35
25
25
25
26

10
3
3
3
3
3
3
3
2
10
*/