Submission #711804

#TimeUsernameProblemLanguageResultExecution timeMemory
711804tutisCoins (LMIO19_monetos)C++17
10.22 / 100
2071 ms11220 KiB
/*input 0 4 1 5 0 0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 */ #pragma GCC optimize("O3") #pragma GCC target("avx2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); using ll = long long; using ull = unsigned long long; using ld = long double; template<typename A, typename B> using omap = tree <A, B, less<A>, rb_tree_tag, tree_order_statistics_node_update>; template<typename A> using oset = tree <A, null_type, less<A>, rb_tree_tag, tree_order_statistics_node_update>; const ll mod = 1e9 + 7; ll ran(ll a, ll b) { //return a + (ll)(rng() % (b - a + 1)); return uniform_int_distribution<ll>(a, b)(rng); } ll power(ll x, ll p) { if (abs(x) >= mod) x %= mod; if (x < 0) x += mod; if (abs(p) >= mod - 1) p %= mod - 1; if (p < 0) p += mod - 1; ll r = 1; while (p) { if (p % 2) r = (r * x) % mod; x = (x * x) % mod; p /= 2; } return r; } void solve() { int t, n, k1, k2; cin >> t >> n >> k1 >> k2; int a[n][n]; int c = 0; for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { cin >> a[i][j]; c += a[i][j]; } } int sp[n][n + 1]; for (int i = 0; i < n; i++) { sp[i][0] = 0; for (int j = 0; j < n; j++) sp[i][j + 1] = sp[i][j] + a[i][j]; } int x[n + 2]; int* h = x + 1; h[-1] = n; h[n] = 0; { int c1 = c; for (int i = 0; i < n; i++) { h[i] = min(n, c1); c1 -= h[i]; } } for (int t = 0; t < 100; t++) { int D = 10; int S = 100; pair<int, int> dp[n][2 * D + 1][2 * S + 1]; for (int i = 0; i < n; i++) for (int d = -D; d <= D; d++) for (int s = -S; s <= S; s++) dp[i][d + D][s + S] = { -1e8, -1}; for (int i = 0; i < n; i++) { for (int d = -D; d <= D; d++) { int hi = h[i] + d; if (hi < 0 || hi > n) continue; if (i == 0) { dp[i][d + D][d + S] = {sp[i][hi], 0}; } else { for (int dj = -D; dj <= D; dj++) { if (h[i - 1] + dj >= hi) { for (int s = -S; s <= S; s++) { int sj = s - d; if (sj >= -S && sj <= S) { dp[i][d + D][s + S] = max(dp[i][d + D][s + S], {dp[i - 1][dj + D][sj + S].first + sp[i][hi], dj}); } } } } } } } int s = 0; int i = n - 1; int di = 0; { pair<int, int>mx = { -1000, -1000}; for (int d = -D; d <= D; d++) mx = max(mx, {dp[i][d + D][s + S].first, d}); di = mx.second; } while (i >= 0) { h[i] += di; int dj = dp[i][di + D][s + S].second; s -= di; i--; di = dj; } } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) a[i][j] = 0; for (int i = 0; i < n; i++) for (int j = 0; j < h[i]; j++) a[i][j] = 1; for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { cout << a[i][j] << " "; } cout << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...