Submission #1196280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196280		heavylightdecomp	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	0 ms	324 KiB

soccer

//Template credits:
//Benq, Errichto and me
#include <bits/stdc++.h>
using namespace std;
#define i32 signed
#define int long long
using str = string; //yay python!
#define X first
#define Y second
using pii = pair<int,int>;
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
#define each(x,y) for(auto x : y)
#define sim template<class c
#define dor > dbg& operator<<
#define ris return *this
#define eni(x) sim> typename enable_if<sizeof dud<c>(0) x 1, dbg&>::type operator<<(c i)
sim> struct rge { c b,e; };
sim> rge<c> range(c i, c j) { return rge<c>{i,j}; }
sim> auto dud(c* x) -> decltype(cout << *x, 0);
sim> char dud(...);
template<class T, size_t R, size_t C>
struct matrik {
    T (&arr)[R][C];
    int r1, r2, c1, c2;
    //pythonic: dim is either {r2, c2} or {r1, r2, c1, c2}
    matrik(T (&a)[R][C], initializer_list<int> dims)
      : arr(a), r1(0), r2(R), c1(0), c2(C)
    {
        auto it = dims.begin();
        if (dims.size() == 2) {
            r2 = *it++;
            c2 = *it;
        }
        else if (dims.size() == 4) {
            r1 = *it++;
            r2 = *it++;
            c1 = *it++;
            c2 = *it;
        }
    }
};
sim, class b> ostream& operator<<(ostream &out, pair<b,c> d) {
    out << "(" << d.X << ", " << d.Y << ")";
    return out;
}
sim> ostream& operator<<(ostream &out, rge<c> d) {
    out << "{";
    f0r(it, d.b, d.e) out << ", " + 2*(it==d.b) << *it;
    out << "}";
    return out;
}
struct dbg {
    //behaviour: it won't print spaces after debugging
    ~dbg() { cerr << '\n'; }
    eni(!=) {                 // for non-iterables
        cerr << boolalpha << i; ris;
    }
    eni(==) {                 // for iterables
        ris << range(all(i));
    }
    // pair printer
    sim, class b dor(pair<b,c> d) {
        ris << "(" << d.X << ", " << d.Y << ")";
    }
    // range printer (should work for like most c++ stuffs)
    sim dor(rge<c> d) {
        *this << "{";
        f0r(it, d.b, d.e) *this << ", " + 2*(it==d.b) << *it;
        ris << "}";
    }
    
    sim, size_t R, size_t C dor(const matrik<c,R,C>& m) {
        int rows = m.r2 - m.r1;
        int cols = m.c2 - m.c1;

        //ts only works for immediate printables...rip
        std::vector<int> w(cols, 0);
        for (int j = 0; j < cols; ++j)
            for (int i = 0; i < rows; ++i) {
                std::ostringstream buf;
                buf << m.arr[m.r1 + i][m.c1 + j];
                w[j] = std::max(w[j], (int)buf.str().size());
            }

        *this << "[";                         
        for (int i = 0; i < rows; ++i) {
            if (i) cerr << ",\n ";            
            cerr << "[";                      
            for (int j = 0; j < cols; ++j) {
                if (j) cerr << ", ";
                cerr << setw(w[j])       // right-justify to column width
                    << m.arr[m.r1 + i][m.c1 + j];
            }
            cerr << "]";                     
        }
        ris << "]";                           
    }

    
    //3 tuple example
    sim, class d, class e dor(const tuple<c,d,e>& t) {
        ris << "(" << get<0>(t) << ", "
                     << get<1>(t) << ", " << get<2>(t) << ")";
    }
};

#define imie(r...) " [" << #r << ": " << (r) << "] "
sim, size_t depth>
struct _nvt {
    using type = vt<typename _nvt<c,depth-1>::type>;
};
sim>
struct _nvt<c,1> {
    using type = vt<c>;
};
sim, size_t depth>
using nvt = typename _nvt<c,depth>::type;


mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
//do not forget to invert priority queue comparisons
//never forget the cf "the way home" incident
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
constexpr int pct(int x) { return __builtin_popcountll((unsigned long long)x); }
//this is more mathematically cool than you think
//it should work for o(1) range max queries
//p2(bits(x)) returns the highest power of 2 <= x
constexpr int bits(int x) { return x == 0 ? 0 : 63 - __builtin_clzll((unsigned long long)x); }
constexpr int p2(int x) { return (int)1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }
inline long long cdiv(long long a, long long b) { return a / b + ((a ^ b) > 0 && a % b); }
inline long long fdiv(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }
//olympiad (ts is so tuff bro)
template<class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<class T, class U> T fstTrue(T lo, T hi, U f) { ++hi; assert(lo <= hi); while(lo < hi) { T mid = lo + (hi - lo) / 2; f(mid) ? hi = mid : lo = mid + 1; } return lo; }
template<class T, class U> T lstTrue(T lo, T hi, U f) { --lo; assert(lo <= hi); while(lo < hi) { T mid = lo + (hi - lo + 1) / 2; f(mid) ? lo = mid : hi = mid - 1; } return lo; }
template<class T> void remDup(vector<T> &v) { sort(all(v)); v.erase(unique(all(v)), end(v)); }
//never forget the aiio 2013 RJ incident
template<class T, class U> void safeErase(T &t, const U &u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }
const auto beg_time = chrono::high_resolution_clock::now();
double time_elapsed() { return chrono::duration<double>(chrono::high_resolution_clock::now() - beg_time).count(); }
using matrix = vt<vt<int>>;
//n dimensional vector i guess
int solve(matrix a) {
    int n = sz(a);
    auto b = matrix(n, vt<int> (n,0));
    // auto trees = matrix(n+5);
    // f0r(i,0,n) {
    //     f0r(j,0,n) {
    //         if(a[i][j]) {
    //             trees[i].pb(j);
    //         }
    //     }
    // }
    //pyramid proof of concept
    const int INF = 1e10;
    nvt<int,3> dp = vt(n+5,vt(n+5,vt(n+5,-INF)));
    auto pd = dp;
    nvt<bool,3> valid = vt(n+5,vt(n+5,vt(n+5,bool(0))));
    f0r(row,0,n) {
        //dbg() << imie(row);
        f0r(i,0,n) {
            f0r(j,i,n) {
                if(i == j) {
                    valid[row][i][j] = !a[row][j];
                } else {
                    valid[row][i][j] = valid[row][i][j-1] and !a[row][j];
                }
                // cerr << (int)valid[row][i][j] << ' ';
            }
            // cerr << '\n';
        }
    }
    //dbg() << imie(a[1][1]);
    // dbg() << imie(valid[1][0][1]);
    f0r(i,0,n) {
        f0r(j,i,n) {
            if(valid[0][i][j]) {
                dp[0][i][j] = j-i+1;
            } else {
                dp[0][i][j] = 0;
            }
        }
    }
    f0r(row,1,n) {
        f0r(i,0,n) {
            f0r(j,i,n) {
                f0r(l,0,n) {
                    f0r(r,l,n) {
                        if(i <= l and r <= j and valid[row][i][j] and valid[row-1][l][r]) {
                            // dbg() << imie(row) << imie(i) << imie(j) << imie(l) << imie(r);
                            dp[row][i][j] = max(dp[row][i][j], dp[row-1][l][r]+j-i+1);
                        }
                    }
                }
                if(valid[row][i][j]) {
                    dp[row][i][j] = j-i+1;
                } else {
                    dp[row][i][j] = 0;
                }
            }
        }
    }
    // auto pd = 
    f0r(i,0,n) {
        f0r(j,i,n) {
            if(valid[n-1][i][j]) {
                pd[n-1][i][j] = j-i+1;
            } else {
                pd[n-1][i][j] = 0;
            }
        }
    }
    r0f(row,n-2,0) {
        f0r(i,0,n) {
            f0r(j,i,n) {
                f0r(l,0,n) {
                    f0r(r,l,n) {
                        if(i <= l and r <= j and valid[row][i][j] and valid[row+1][l][r]) {
                            // dbg() << imie(row) << imie(i) << imie(j) << imie(l) << imie(r);
                            pd[row][i][j] = max(pd[row][i][j], pd[row+1][l][r]+j-i+1);
                            // dbg() << imie(pd[row][i][j]);
                        }
                    }
                }
                if(valid[row][i][j]) {
                    pd[row][i][j] = j-i+1;
                } else {
                    pd[row][i][j] = 0;
                }
            }
        }
    }
    int res = 0;
    
    // dbg() << "yooooooo\n";
    f0r(row,0,n) f0r(i,0,n) f0r(j,i,n) {
        int nxt = dp[row][i][j] + pd[row][i][j] - (j-i+1);
        if(ckmax(res,nxt)) {
            // dbg() << imie(dp[row][i][j]) << imie(pd[row][i][j]) << imie(row) << imie(i) << imie(j);
        }
    };
    return res;
    
}
i32 biggest_stadium(i32 N, vt<vt<i32>> F) {
    nvt<int,2> a = vt(N,vt(N,0ll));
    f0r(i,0,N) {
        f0r(j,0,N) {
            a[i][j] = F[i][j];
        }
    }
    int res = solve(a);
    return res;
}
// i32 main() {
//     cin.tie(0)->sync_with_stdio(0);
//     matrix a = {{0,0,1}, {0,1,1}, {0,0,1}};
//     solve(a);
    
// }


/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * on easy problems: it's usually an easy bug
 * work probabilistically and be rational
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30