#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));(s)<(e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int k,n,s;
int arr[20005];
int pre[20005];
string ac[51];
int memo[2][20005];
int ver[51][20005];
struct node{
int table[15][20005];
void init(int v[20005]){
int n=k+1;
rep(x,0,n) table[0][x]=v[x];
int layer=0;
n--;
while (n>0){
rep(x,0,n)
table[layer+1][x]=min(table[layer][x],table[layer][x+(1<<layer)]);
layer++;
n-=1<<layer;
}
}
int query(int i,int j){
int len=j-i+1;
int layer=31-__builtin_clz(len);
return min(table[layer][i],table[layer][j-(1<<layer)+1]);
}
} root[51];
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>k>>s;
rep(x,1,k+1) cin>>arr[x];
rep(x,1,k+1) pre[x]=pre[x-1]+arr[x];
rep(x,0,n) cin>>ac[x];
rep(x,0,n) ac[x]="$"+ac[x];
memset(memo,63,sizeof(memo));
int a=0,b=1;
memo[a][0]=0;
rep(zzz,0,s){
memset(memo[b],63,sizeof(memo[b]));
rep(x,0,n+1){
rep(y,0,k+1) ver[x][y]=memo[a][y]-x*pre[y];
root[x].init(ver[x]);
}
vector<ii> imp;
rep(x,-1,n) imp.pub({0,x});
rep(x,1,k+1){
vector<ii> temp;
for (auto it:imp) if (it.se==-1 || ac[it.se][x]=='1') temp.pub(it);
rep(y,0,n) if (ac[y][x]=='0') temp.pub({x,y});
swap(imp,temp);
imp.pub({x,-1});
int best=2e9+100;
int curr=0;
rep(y,n+1,0){
if (imp[y].fi!=imp[y+1].fi){
//cout<<"debug2: "<<n-y<<" "<<imp[y+1]<<" "<<imp[y]-1<<endl;
//cout<<root[n-y].query(imp[y+1],imp[y]-1)<<endl;
best=min(best,root[y].query(imp[y].fi,imp[y+1].fi-1)+curr);
}
curr-=pre[x];
}
best+=n*pre[x];
memo[b][x]=best;
imp.pob();
}
swap(a,b);
//rep(x,0,k+1) cout<<memo[a][x]<<" "; cout<<endl;
cout<<memo[a][k]<<endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
1492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
3564 KB |
Output is correct |
2 |
Correct |
33 ms |
3412 KB |
Output is correct |
3 |
Correct |
34 ms |
3572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
158 ms |
7972 KB |
Output is correct |
2 |
Correct |
216 ms |
10324 KB |
Output is correct |
3 |
Correct |
293 ms |
13132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
1492 KB |
Output is correct |
3 |
Correct |
33 ms |
3564 KB |
Output is correct |
4 |
Correct |
33 ms |
3412 KB |
Output is correct |
5 |
Correct |
34 ms |
3572 KB |
Output is correct |
6 |
Correct |
158 ms |
7972 KB |
Output is correct |
7 |
Correct |
216 ms |
10324 KB |
Output is correct |
8 |
Correct |
293 ms |
13132 KB |
Output is correct |
9 |
Correct |
491 ms |
20412 KB |
Output is correct |
10 |
Correct |
670 ms |
26424 KB |
Output is correct |
11 |
Correct |
1460 ms |
58260 KB |
Output is correct |
12 |
Correct |
1606 ms |
60552 KB |
Output is correct |
13 |
Correct |
1582 ms |
60620 KB |
Output is correct |
14 |
Correct |
1605 ms |
60636 KB |
Output is correct |
15 |
Correct |
1573 ms |
60640 KB |
Output is correct |