제출 #1196281

#제출 시각아이디문제언어결과실행 시간메모리
1196281heavylightdecompSoccer Stadium (IOI23_soccer)C++17
0 / 100
4544 ms20292 KiB
//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) { if(valid[row][i][j]) { dp[row][i][j] = j-i+1; } else { dp[row][i][j] = 0; } 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); } } } } } } // 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) { if(valid[row][i][j]) { pd[row][i][j] = j-i+1; } else { pd[row][i][j] = 0; } 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]); } } } } } } 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...