Submission #850612

#	Time	Username	Problem	Language	Result	Execution time	Memory
850612		StefanSebez	Cat Exercise (JOI23_ho_t4)	C++14	41 / 100	175 ms	35260 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const int N=2*1e5+50;
map<pair<int,int>,int>mapa;
ll dp[N];
int main()
{
    int n;scanf("%i",&n);
    int a[n+1],L[n+1],R[n+1];
    vector<int>mono;
    for(int i=1;i<=n;i++)
	{
		L[i]=0,R[i]=n+1;
		scanf("%i",&a[i]);
		while(!mono.empty() && a[mono.back()]<a[i])
		{
			R[mono.back()]=i;
			mono.pop_back();
		}
		if(!mono.empty()) L[i]=mono.back();
		mono.push_back(i);
	}
	pair<int,int>par[n+1];
	for(int i=1;i<=n;i++)
	{
		mapa[{L[i],R[i]}]=i;
		par[i]=make_pair(R[i]-L[i],i);
	}
	sort(par+1,par+n+1);
	for(int i=1;i<=n;i++)
	{
		int j=par[i].se,maks=0,l=mapa[{L[j],j}],r=mapa[{j,R[j]}];
		if(j-L[j]>1)dp[j]=max(dp[l]+j-l,dp[j]);
		if(R[j]-j>1)dp[j]=max(dp[r]+r-j,dp[j]);
	}
    for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%i%i",&u,&v);
	}
	printf("%lld\n",dp[mapa[{0,n+1}]]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:19: warning: unused variable 'maks' [-Wunused-variable]
   35 |   int j=par[i].se,maks=0,l=mapa[{L[j],j}],r=mapa[{j,R[j]}];
      |                   ^~~~
Main.cpp:11:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     int n;scanf("%i",&n);
      |           ~~~~~^~~~~~~~~
Main.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%i",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%i%i",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26