/** 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 = 32768;
const int oo = 2000000001;
int val[N * 2];
inline void upd(int p, int w) {
val[p + N - 1] += w;
for (int cur = (p + N - 1) >> 1; cur; cur >>= 1)
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;
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));
}
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';
}
int toUpd[n][t];
int from[n][t];
memset(toUpd, 0, sizeof toUpd);
memset(from, -1, sizeof from);
rep(i, 0, n) {
int pr = 0;
rep(j, 0, t) {
if (res[i][j]) {
toUpd[i][pr] += pts[j];
toUpd[i][j] -= pts[j];
} else {
from[i][j] = pr;
pr = j;
}
}
int sum = 0;
rep(j, 0, t) {
sum += toUpd[i][j];
toUpd[i][j] = sum;
}
}
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) {
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) {
rep(k, 0, n) {
if (from[k][i] != -1) {
rep(l, from[k][i], i)
upd(l + 1, -toUpd[k][l]);
}
upd(i + 1, toUpd[k][i]);
}
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)
print(toUpd[i][j], from[i][j]), 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();}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
640 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
74 ms |
964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
355 ms |
2112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
640 KB |
Output isn't correct |
