| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 853281 | resting | Soccer Stadium (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#include "soccer.h"
#define int long long
struct segtree{ //range max
int l, r;
int v = -1;
segtree *lc = 0, *rc = 0;
segtree*getmem();
segtree(int l, int r): l(l), r(r){
if(l == r) return;
int m = (l+r)/2;
lc = getmem(); *lc = segtree(l, m);
rc = getmem(); *rc = segtree(m+1, r);
}
segtree():segtree(-1, -1){};
int q(int ql, int qr){
if(ql <= l && r <= qr) return v;
if(qr < l || ql > r) return -1;
return max(lc->q(ql, qr), rc->q(ql, qr));
}
void upd(int qi, int qv){
if(qi < l || qi > r) return;
if(l == r){v = qv; return;}
lc->upd(qi, qv); rc->upd(qi, qv);
v = max(lc->v, rc->v);
}
}mem[1024*1024*4*2]; int memsz = 0;
segtree* segtree::getmem(){return &mem[memsz++];}
int solve(int n, vector<vector<pair<int,int>>> &adj){
vector<int> cnt(n);
for(auto j : adj) for(auto &x : j)cnt[x.first]++;
vector<int> q; // topological sorting
for(int i = 0; i < n; i++) if(cnt[i] == 0) q.push_back(i);
vector<int> sort;
while(q.size()){
int v = q.back();
q.pop_back();
sort.push_back(v);
for(auto &x : adj[v]){
cnt[x.first]--;
if(cnt[x.first]==0)
q.push_back(x.first);
}
}
//sorted
vector<int> dp(n, 0);
int res = 0;
for(auto &x : sort){
res = max(res, dp[x]);
for(auto &j : adj[x]){
dp[j.first] = max(dp[j.first], dp[x] + j.second);
}
}
return res;
}
int32_t biggest_stadium(int32_t N, std::vector<std::vector<int32_t>> F){
map<vector<int>, int> owo; int cur = 1; // map to good shit ig idkkk
vector<vector<pair<int,int>>> adj(N*N+5); // shouldnt be moree??
//set up segtree???
vector<vector<int>> lo, hi, l;
lo = hi = l = vector<vector<int>>(N, vector<int>(N, -1));
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(j) l[i][j] = l[i][j-1];
if(F[i][j]) l[i][j] = j;
}
}
segtree uwu(0, N-1);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(F[i][j]) uwu.upd(j, i);
}
for(int j = 0; j < N; j++){
if(F[i][j]) continue;
lo[i][j] = uwu.q(l[i][j]+1, j)+1;
}
}
uwu = segtree(0, N-1);
for(int i = N-1; i >= 0; i--){
for(int j = 0; j < N; j++){
if(F[i][j]) uwu.upd(j, N-i-1);
}
for(int j = 0; j < N; j++){
if(F[i][j]) continue;
hi[i][j] = N-uwu.q(l[i][j]+1, j)-2;
}
}
auto extend = [&](int i, int j, int i2, int j2){
int lo2 = lo[i][j], hi2 = hi[i][j], lo3 = lo[i2][j2], hi3 = hi[i2][j2];
int id = owo[{lo2, hi2, j}], id2 = owo[{lo3, hi3, j2}];
adj[id].push_back(make_pair(id2, (lo2-lo3 + hi3-hi2) * (j2 - l[i2][j2])));
};
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(F[i][j]) continue;
int lo2 = lo[i][j];
int hi2 = hi[i][j];
if(!owo.count({lo2, hi2, j})) owo[{lo2, hi2, j}] = cur++;
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(F[i][j]) continue;
int lo2 = lo[i][j];
int hi2 = hi[i][j];
int id = owo[{lo2, hi2, j}];
adj[0].push_back(make_pair(id, (hi2-lo2+1) * (j - (l[i][j]+1) + 1)));
if(l[i][j]+1 != j){
extend(i, j, i, j-1);
}
if(lo2 && !F[lo2-1][j]){
extend(i, j, lo2-1, j);
}
if(hi2 < N-1 && !F[hi2+1][j]){
extend(i, j, hi2+1, j);
}
}
}
return solve(adj.size(), adj);
}
int32_t main()
{
int N;
assert(1 == scanf("%d", &N));
std::vector<std::vector<int32_t>> F(N, std::vector<int32_t>(N));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
assert(1 == scanf("%d", &F[i][j]));
}
}
fclose(stdin);
int res = biggest_stadium(N, F);
printf("%d\n", res);
fclose(stdout);
return 0;
}