Submission #116079

#TimeUsernameProblemLanguageResultExecution timeMemory
116079SpeedOfMagicPopeala (CEOI16_popeala)C++17
26 / 100
1900 ms24184 KiB
/** MIT License Copyright (c) 2018-2019 Vasilev Daniil **/ #include <bits/stdc++.h> using namespace std; template<typename T> using v = vector<T>; //#define int long long typedef long double ld; typedef string str; typedef vector<int> vint; #define rep(a, l, r) for(int a = (l); a < (r); a++) #define pb push_back #define fs first #define sc second #define sz(a) ((int) a.size()) const long long inf = 4611686018427387903; //2^62 - 1 const long double EPS = 1e-10; #if 0 //FileIO const string fileName = ""; ifstream fin ((fileName == "" ? "input.txt" : fileName + ".in" )); ofstream fout((fileName == "" ? "output.txt" : fileName + ".out")); #define get fin >> #define put fout << #else #define get cin >> #define put cout << #endif #define eol put endl void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg) ;read(args...) ;} void print(){} template<typename Arg,typename... Args> void print(Arg arg,Args... args){put (arg)<<" ";print(args...);} int getInt(){int a; get a; return a;} //code starts here const int N = 4096; const int oo = 2000000001; int val[N * 2], lazy[N * 2]; inline void pushdown(int cur) { if (lazy[cur]) { if (cur < N) { lazy[cur << 1] += lazy[cur]; lazy[cur << 1 | 1] += lazy[cur]; } val[cur] += lazy[cur]; lazy[cur] = 0; } } inline void upd(int l, int r, int w, int cur = 1, int ll = 1, int rr = N) { pushdown(cur); if (l > r) return; if (l == ll && r == rr) { lazy[cur] += w; pushdown(cur); return; } int mid = (ll + rr) >> 1; upd(l, min(r, mid), w, cur << 1, ll, mid); upd(max(l, mid + 1), r, w, cur << 1 | 1, mid + 1, rr); val[cur] = min(val[cur << 1], val[cur << 1 | 1]); } inline int query(int l, int r, int cur = 1, int ll = 1, int rr = N) { if (l > r) return oo; pushdown(cur); if (l == ll && r == rr) return val[cur]; int mid = (ll + rr) >> 1; return min(query(l, min(r, mid), cur << 1, ll, mid), query(max(l, mid + 1), r, cur << 1 | 1, mid + 1, rr)); } struct quer { int l, r, w; quer() {} quer(int ll, int rr, int ww) : l(ll), r(rr), w(ww) {} }; void run() { int n, t, s; read(n, t, s); int pts[t]; rep(i, 0, t) get pts[i]; char res[n][t]; rep(i, 0, n) { str st; get st; rep(j, 0, t) res[i][j] = st[j] - '0'; } v<quer> queries[t]; rep(i, 0, n) { int pr = 0; rep(j, 0, t) { if (res[i][j]) queries[j].pb(quer(pr + 1, j, pts[j])); else { int sum = 0; for (int k = j - 1; k > pr; k--) { sum += pts[k]; queries[j].pb({k, k, -sum}); } pr = j; } } } int dp[t][s]; rep(i, 0, t) rep(j, 0, s) dp[i][j] = oo; int cur[n]; memset(cur, 0, sizeof cur); rep(i, 0, t) { rep(j, 0, n) if (res[j][i] && cur[j] != -1) cur[j] += pts[i]; else cur[j] = -1; dp[i][0] = 0; rep(j, 0, n) if (cur[j] != -1) dp[i][0] += cur[j]; } rep(j, 1, s) { memset(lazy, 0, sizeof lazy); for (int i = N; i < N + t; i++) val[i] = dp[i - N][j - 1]; for (int i = N + t; i < N * 2; i++) val[i] = oo; for (int i = N - 1; i; i--) val[i] = min(val[i << 1], val[i << 1 | 1]); rep(i, 0, t) { for (quer q : queries[i]) if (q.l == q.r) { val[q.l + N - 1] += q.w; for (int k = (q.l + N - 1) >> 1; k; k >>= 1) { pushdown(k); pushdown(k << 1); pushdown(k << 1 | 1); val[k] = min(val[k << 1], val[k << 1 | 1]); } } else upd(q.l, q.r, q.w); dp[i][j] = min(dp[i][j], query(1, i)); } } rep(j, 0, s) put dp[t - 1][j], eol; /* rep(i, 0, n) rep(j, 0, t) for (quer q : queries[i][j]) print(j, q.l, q.r, q.w), eol; rep(i, 0, s) { rep(j, 0, t) print(dp[j][i]); eol; } */ } /* 0 8 16 2 3 3 4 3 5 101 110 *//* 7 7 1 2 2 4 3 11 *//* 0 1 1 3 2 2 4 1 011 *//* 0 0 3 4 2 4 5 6 7 1001 0110 1010 *//* 0 10 2 5 2 1 2 3 4 5 01111 11101 */ signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run();}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...