Submission #821352

#TimeUsernameProblemLanguageResultExecution timeMemory
821352Shreyan_PaliwalNafta (COI15_nafta)C++17
100 / 100
334 ms123656 KiB
// #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; template<typename T> string tostr(const T& value) { ostringstream oss; oss << value; return oss.str(); } template<typename... Args> string fstr(const string& format, Args... args) { string result = format; size_t pos = 0; size_t argIndex = 0; auto replaceArg = [&](const auto& arg) { pos = result.find("{}", pos); if (pos != string::npos) { result.replace(pos, 2, tostr(arg)); ++argIndex; } }; (replaceArg(args), ...); return result; } /* * Keeps mint objects modulo MOD constant */ // const int MOD = 1e9 + 7; // struct mint { // int x; // mint() { x = 0; } // mint(int X) { x = X; } // mint(long long X) { x = ((X % MOD) + MOD) % MOD; } // mint(unsigned long long X) { x = (X % MOD); } // mint pow(int k) { mint r = 1, a = *this; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; } // mint& operator+=(mint o) { if ((x += o.x) >= MOD) x -= MOD; return *this; } // mint& operator-=(mint o) { if ((x += MOD - o.x) >= MOD) x -= MOD; return *this; } // mint& operator*=(mint o) { x = 1ll * x * o.x % MOD; return *this; } // mint& operator/=(mint o) { return (*this) *= o.pow(MOD - 2); } // mint operator+(mint o) const { return mint(*this) += o; } // mint operator-(mint o) const { return mint(*this) -= o; } // mint operator*(mint o) const { return mint(*this) *= o; } // mint operator/(mint o) const { return mint(*this) /= o; } // bool operator<(mint o) const { return x < o.x; } // friend ostream& operator<<(ostream& os, mint a) { os << a.x; return os; } // }; /* * Matrices * Multiplication */ // typedef vector<vector<int>> MAT; // struct Matrix { // MAT v; // Matrix(MAT V) { swap(v, V); } // Matrix(int a, int b) { v.resize(a, vector<int>(b, 0)); } // Matrix operator*(const Matrix& o) { // // assert(v[0].size() == o.v.size()); // Matrix M(v.size(), o.v[0].size()); // for (int i = 0; i < v.size(); i++) // for (int j = 0; j < o.v[0].size(); j++) // for (int k = 0; k < (int)v[0].size(); k++) // M.v[i][j] += v[i][k] * o.v[k][j]; // return M; // } // Matrix operator^(int k) { // if (k&1) return (((*this)*(*this))^(k/2))*(*this); // else return ((*this)*(*this))^(k/2); // } // }; /* * Segment Tree * - RANGE QUERY * - RANGE UPDATE */ // template<class T> // T identity; // [SET IDENTITY OF CLASS T, hardcode T classname] // struct ND { // ND* ch[2] = { nullptr, nullptr }; // T v, f; // inline void create() { // if (!ch[0]) ch[0] = new ND; // [POTENTIALLY UPDATE VALUES] // if (!ch[1]) ch[1] = new ND; // [POTENTIALLY UPDATE VALUES] // } // inline void merge(int l, int r) { // // [INSERT CODE FOR MERGE SEGMENT] // } // inline void push(int l, int r) { // create(); // // [INSERT CODE FOR PUSHING SEGMENT FLAG] // } // void upd(int l, int r, int L, int R, T K) { // push(l, r); // if (R < l || r < L) return; // if (L <= l && r <= R) { // // [INSERT CODE FOR UPDATE SEGMENT] // return; // } // int m = (l + r) >> 1; // ch[0]->upd(l, m, L, R, K); // ch[1]->upd(m+1, r, L, R, K); // merge(l, r); // } // T qry(int l, int r, int L, int R) { // push(l, r); // if (R < l || r < L) return identity; // if (L <= l && r <= R) return s; // int m = (l + r) >> 1; // return merge(ch[0]->qry(l,m,L,R), ch[1]->qry(m+1,r,L,R)); // } // ~ND() { delete ch[0]; delete ch[1]; ch[0] = ch[1] = nullptr; } // }; /* * Convex Hull Trick * - ORDERED SLOPES * - UNORDERED QUERIES O(N log N), ORDERED QUERIES O(N) */ // struct F { // int a, b; // F() {} // F(int A, int B) : a(A), b(B){ if (b<0) a*=-1, b*=-1; } // bool operator<(F o) const { return a*o.b < b*o.a; } // bool operator<=(F o) const { return a*o.b <= b*o.a; } // }; // struct L { // int m, b; // int operator()(int x) { return m*x + b; } // F operator^(L o) { return F{b-o.b,o.m-m}; } // }; // struct CHT { // vector<L> h; // // deque<L> h; // if using SECOND CODE in QRY FUNCTION // void add(L l) { // // // min hull + decreasing slopes OR max hull + increasing slopes // // while (h.size() >= 2 && (h.end()[-2]^l) <= (h.end()[-2]^h.back())) h.pop_back(); // // h.push_back(l); // // // min hull + increasing slopes OR max hull + decreasing slopes // // while (h.size() >= 2 && (h.end()[-2]^h.back()) <= (h.end()[-2]^l)) h.pop_back(); // // h.push_back(l); // } // int qry(int x) { // // O(N log N) time, unordered queries // // int lo = 0, hi = h.size()-1; // // while (lo < hi) { // // int m = (lo + hi) >> 1; // // if (h[m](x) < h[m+1](x)) // < or > depending on min/max qry // // lo = m+1; // // else // // hi = m; // // } // // return h[lo](x); // // if need O(N) time, use **DEQUE INSTEAD OF VECTOR** & use code below // // while (h.size() >= 2 && h[1](x) < h[0](x)) h.pop_front(); // < or > depending on min/max qry // // return h[0](x); // } // }; /* * Li Chao Tree * UNORDERED SLOPES, UNORDERED QUERIES O(N log N) * Extension of segment tree */ // struct F { // int a, b; // F() {} // F(int A, int B) : a(A), b(B){ if (b<0) a*=-1, b*=-1; } // bool operator<(F o) const { return a*o.b < b*o.a; } // bool operator<=(F o) const { return a*o.b <= b*o.a; } // }; // struct L { // int m, b; // int operator()(int x) { return m*x + b; } // F operator^(L o) { return F{b-o.b,o.m-m}; } // }; // // #define OP(a, b) (a < b) // DEFINE OPERATOR // // #define OPR(a, b) (min(a,b)) // DEFINE OPERATOR // #define OP(a, b) (a > b) // #define OPR(a, b) (max(a,b)) // struct ND { // ND * ch[2] = { nullptr, nullptr }; // L v = L{1, 0}; // void create() { // if (!ch[0]) { ch[0] = new ND; ch[0]->v = v; } // if (!ch[1]) { ch[1] = new ND; ch[1]->v = v; } // } // void upd(int l, int r, L V) { // // update the li chao tree with line V // if (v.m == V.m && v.b == V.b) return; // if (l == r) { // // if new line is better, swap // if (OP(V(l), v(l))) swap(V, v); // return; // } // create(); // int m = (l + r) >> 1; // midpoint // if (OP(V(m), v(m))) swap(V, v); // if new line is better at mid, it has one half, so swap // F x = v ^ V; // intersection of two lines // if (x <= F(m, 1)) // ch[0]->upd(l, m, V); // else // ch[1]->upd(m+1, r, V); // } // int qry(int l, int r, int X) { // // qry li chao tree for x coord X // int ret = v(X); // gets value for current segment // if (l != r) { // int m = (l + r) >> 1; // if (X <= m && ch[0] != nullptr) return OPR(ret, ch[0]->qry(l, m, X)); // if (X > m && ch[1] != nullptr) return OPR(ret, ch[1]->qry(m+1, r, X)); // } // return ret; // } // }; // #undef OP // #undef OPR /* * Heavy Light Decomp */ #define valid(a, b) (a >= 1 && b >= 1 && a <= r && b <= s) const int maxr = 2005; int r, s; int gr[maxr][maxr]; int dp[maxr][maxr], f[maxr][maxr], g[maxr][maxr]; int dr[] = {1, 0, -1, 0}; int dc[] = {0, 1, 0, -1}; pair<int,int> curc; int num; void ff(int R, int C) { num += gr[R][C]; gr[R][C] = -1; curc.first = min(curc.first, C), curc.second = max(curc.second, C); for (int i = 0; i < 4; i++) { int nr = R + dr[i], nc = C + dc[i]; if (!valid(nr, nc)) continue; if (gr[nr][nc] == -1) continue; ff(nr, nc); } } void dvc(int L, int R, int lh, int hh, int k) { if (L > R) return; // cout << "-----" << endl; int m = (L + R) >> 1; // for (int i = lh; i <= min(m, hh); i++) // cout << L << ' ' << R << ' ' << m << ' ' << i << ' ' << dp[i][k-1] + f[i][m] << endl; int j = lh; for (int i = lh; i <= min(m, hh); i++) if (dp[m][k] <= dp[i][k-1] + f[i][m]) dp[m][k] = dp[i][k-1] + f[i][m], j = i; if (L == R) return; dvc(L, m-1, lh, j, k); dvc(m+1, R, j, hh, k); } void solve() { cin >> r >> s; for (int i = 1; i <= r; i++) for (int j = 1; j <= s; j++) { char c; cin >> c; if (c == '.') gr[i][j] = -1; else gr[i][j] = c - '0'; } for (int i = 1; i <= r; i++) for (int j = 1; j <= s; j++) { if (gr[i][j] == -1) continue; curc = {j, j}; num = 0; ff(i, j); for (int k = curc.first; k <= curc.second; k++) g[curc.first][k] += num; } for (int j = s; j >= 1; j--) // loop over js for (int i = j-1; i >= 0; i--) // loop over is stemming away from cur j f[i][j] = f[i+1][j] + g[i+1][j]; // for (int i = 0; i <= s; i++) { // for (int j = 0; j <= s; j++) { // cout << g[i][j] << ' '; // } // cout << endl; // } // cout << endl; // for (int i = 0; i <= s; i++) { // for (int j = 0; j <= s; j++) { // cout << f[i][j] << ' '; // } // cout << endl; // } // cout << endl; for (int k = 1; k <= s; k++) dvc(1, s, 0, s, k); for (int i = 1; i <= s; i++) { int r = 0; for (int j = 1; j <= s; j++) r = max(dp[j][i], r); cout << r << endl; } return; } signed main() { cin.tie(nullptr) -> ios::sync_with_stdio(false); // freopen("main.in", "r", stdin); int t; // cin >> t; t=1; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...