| 16289 | 2025-04-20 17:39:58 | horka | Mágikus táblázat | cpp17 | Elfogadva 100/100 | 305ms | 13452 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m; cin>>n>>m;
vector<int> a(n+1),b(m+1),pontok{(int)-1e9-10};
for(int i=1; i<=n; i++)
{
cin>>a[i];
pontok.pb(a[i]);
}
for(int i=1; i<=m; i++)
{
cin>>b[i];
pontok.pb(b[i]);
}
sort(all(pontok));
pontok.erase(unique(all(pontok)),pontok.end());
for(int i=1; i<=n; i++)
{
a[i]=lower_bound(all(pontok),a[i])-pontok.begin();
}
for(int i=1; i<=m; i++)
b[i]=lower_bound(all(pontok),b[i])-pontok.begin();
vector<array<int, 2>> op;
for(int i=1; i<=m; i++)
op.pb({b[i],i});
sort(all(op));
int mer=sz(pontok);
vector<int> maxi(mer);
set<int> s;
for(int i=0; i<=m+1; i++)
s.insert(i);
for(auto &[ert,ind]:op)
{
s.erase(ind);
auto l=s.lower_bound(ind),r=s.upper_bound(ind);
l=prev(l);
maxi[ert]=max(maxi[ert],*r-*l-1);
//cout<<"itt: "<<ert<<" "<<ind<<" "<<*l<<" "<<*r<<endl;
}
for(int i=1; i<mer; i++)
maxi[i]=max(maxi[i],maxi[i-1]);
int ans=0;
op.clear();
for(int i=1; i<=n; i++)
op.pb({a[i],i});
sort(rall(op));
s.clear();
for(int i=0; i<=n+1; i++)
s.insert(i);
for(auto &[ert,ind]:op)
{
s.erase(ind);
auto l=s.lower_bound(ind),r=s.upper_bound(ind);
l=prev(l);
ans=max(ans,(*r-*l-1)*maxi[ert]);
}
cout<<ans<<"\n";
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| 2 | Elfogadva | 23ms | 1588 KiB | ||||
| subtask2 | 14/14 | ||||||
| 3 | Elfogadva | 1ms | 316 KiB | ||||
| 4 | Elfogadva | 1ms | 316 KiB | ||||
| 5 | Elfogadva | 1ms | 500 KiB | ||||
| 6 | Elfogadva | 1ms | 316 KiB | ||||
| 7 | Elfogadva | 1ms | 316 KiB | ||||
| 8 | Elfogadva | 1ms | 316 KiB | ||||
| subtask3 | 27/27 | ||||||
| 9 | Elfogadva | 4ms | 520 KiB | ||||
| 10 | Elfogadva | 4ms | 544 KiB | ||||
| 11 | Elfogadva | 4ms | 552 KiB | ||||
| 12 | Elfogadva | 4ms | 856 KiB | ||||
| 13 | Elfogadva | 3ms | 424 KiB | ||||
| 14 | Elfogadva | 2ms | 500 KiB | ||||
| 15 | Elfogadva | 3ms | 564 KiB | ||||
| 16 | Elfogadva | 4ms | 564 KiB | ||||
| 17 | Elfogadva | 4ms | 676 KiB | ||||
| subtask4 | 21/21 | ||||||
| 18 | Elfogadva | 245ms | 10532 KiB | ||||
| 19 | Elfogadva | 240ms | 10660 KiB | ||||
| 20 | Elfogadva | 165ms | 10528 KiB | ||||
| 21 | Elfogadva | 159ms | 10660 KiB | ||||
| 22 | Elfogadva | 143ms | 9252 KiB | ||||
| 23 | Elfogadva | 143ms | 9252 KiB | ||||
| 24 | Elfogadva | 3ms | 564 KiB | ||||
| subtask5 | 38/38 | ||||||
| 25 | Elfogadva | 305ms | 13348 KiB | ||||
| 26 | Elfogadva | 296ms | 13452 KiB | ||||
| 27 | Elfogadva | 301ms | 13348 KiB | ||||
| 28 | Elfogadva | 294ms | 13348 KiB | ||||
| 29 | Elfogadva | 212ms | 12676 KiB | ||||
| 30 | Elfogadva | 226ms | 12436 KiB | ||||
| 31 | Elfogadva | 172ms | 12332 KiB | ||||
| 32 | Elfogadva | 180ms | 8740 KiB | ||||
| 33 | Elfogadva | 175ms | 8740 KiB | ||||
| 34 | Elfogadva | 97ms | 7716 KiB | ||||
| 35 | Elfogadva | 148ms | 7972 KiB | ||||
| 36 | Elfogadva | 232ms | 12840 KiB | ||||
| 37 | Elfogadva | 233ms | 12580 KiB | ||||
| 38 | Elfogadva | 219ms | 12580 KiB | ||||
| 39 | Elfogadva | 296ms | 13348 KiB | ||||
| 40 | Elfogadva | 279ms | 13092 KiB | ||||
| 41 | Elfogadva | 231ms | 11300 KiB | ||||
| 42 | Elfogadva | 212ms | 12068 KiB | ||||
| 43 | Elfogadva | 177ms | 12324 KiB | ||||
| 44 | Elfogadva | 196ms | 12584 KiB | ||||