| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 595355 | Red_Inside | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>
int mni[maxn], mxi[maxn];
ll mx[maxn], mn[maxn];
long long find_maximum(int k, vector <vector <int> > a)
{
vector <vector <int> > use;
int n = a.size();
int m = a[0].size();
use = a;
forn(0, i, n-1) forn(0, j, m-1) use[i][j] = -1;
ll ret = 0;
vector <int> vec;
forn(0, i, n-1)
{
mni[i] = -1;
mxi[i] = -1;
forn(0, j, m-1)
{
if(mni[i] == -1 || a[i][mni[i]] > a[i][j]) mni[i] = j;
if(mxi[i] == -1 || a[i][mxi[i]] < a[i][j]) mxi[i] = j;
}
vec.pb(a[i][mxi[i]]);
vec.pb(a[i][mni[i]]);
mx[i] = a[i][mxi[i]];
mn[i] = a[i][mni[i]];
}
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
set <pii> Mn, Mx;
ll smx = 0, smn = 0;
forn(0, i, n-1)
{
Mx.insert({mx[i], i});
smx += mx[i];
}
vector <pii> used;
for(auto i : vec)
{
while(Mx.size() && Mx.begin()->first < i)
{
Mn.insert({mn[Mx.begin()->s], Mx.begin()->s});
smx -= mx[Mx.begin()->s];
smn += mn[Mx.begin()->s];
Mx.erase(Mx.begin());
}
vector <pii> temp;
while(Mx.size() && Mx.begin()->f == i)
{
temp.pb(*Mx.begin());
smx -= mx[Mx.begin()->s];
Mx.erase(Mx.begin());
}
if(Mx.size() <= n / 2 && Mn.size() <= n / 2)
{
if(ret < i * ((int)Mn.size()) - smn + smx - i * ((int)Mx.size()))
{
ret = i * ((int)Mn.size()) - smn + smx - i * ((int)Mx.size());
used.clear();
for(auto j : Mx)
{
used.pb({j.s, mxi[j.s]});
}
for(auto j : Mn)
{
used.pb({j.s, mni[j.s]});
}
forn(0, j, temp.size())
{
if(j < (n + 1) / 2 - Mx.size())
{
used.pb({temp[j].s, mxi[temp[j].s]});
}
else
{
used.pb({temp[j].s, mni[temp[j].s]});
}
}
}
}
for(auto j : temp)
{
smx += mx[j.s];
Mx.insert(j);
}
}
for(auto i : used)
{
use[i.f][i.s] = 0;
}
allocate_tickets(use);
return ret;
}