#include<bits/stdc++.h>
const int N = 55;
const int inf = 2e9 + 7;
using namespace std;
int n, t, s, sc[20005], dp[N][20005], cur[20005];
string a[N];
deque <int> mq[N];
void Insert(int id, int i, int j){
while (mq[id].size() && dp[i][mq[id].back()] >= dp[i][j]) mq[id].pop_back();
mq[id].push_back(j);
}
void Erase(int id, int i, int j){
if (mq[id].size() && mq[id].front() == j) mq[id].pop_front();
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> t >> s;
for (int i = 1; i <= t; i++) cin >> sc[i], sc[i] += sc[i-1];
for (int i = 1; i <= n; i++) cin >> a[i], a[i] = '.' + a[i];
for (int i = 0; i < N; i++) for (int j = 0; j < 20005; j++) dp[i][j] = inf;
dp[0][0] = 0;
for (int sub = 1; sub <= s; sub++){
for (int j = 0; j <= n; j++) mq[j].clear();
Insert(n, sub-1, 0); cur[0] = n;
for (int test = 1; test <= t; test++){
for (int peo = 1; peo <= n; peo++){
if (a[peo][test] == '1') continue;
int last = test-1;
while(last > 0 && a[peo][last] == '1') last--;
for (int ntest = last; ntest < test; ntest++){
Erase(cur[ntest], sub-1, ntest);
dp[sub-1][ntest] += sc[ntest];
cur[ntest]--;
Insert(cur[ntest], sub-1, ntest);
}
}
for (int k = 0; k <= n; k++){
if (mq[k].size()) dp[sub][test] = min(dp[sub][test], k * sc[test] + dp[sub-1][mq[k].front()]);
}
dp[sub-1][test] -= n * sc[test]; cur[test] = n;
Insert(n, sub-1, test);
}
cout << dp[sub][t] << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4736 KB |
Output is correct |
2 |
Correct |
6 ms |
4736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
4736 KB |
Output is correct |
2 |
Correct |
33 ms |
4736 KB |
Output is correct |
3 |
Correct |
34 ms |
4736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
4984 KB |
Output is correct |
2 |
Correct |
195 ms |
5120 KB |
Output is correct |
3 |
Correct |
251 ms |
5340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4736 KB |
Output is correct |
2 |
Correct |
6 ms |
4736 KB |
Output is correct |
3 |
Correct |
35 ms |
4736 KB |
Output is correct |
4 |
Correct |
33 ms |
4736 KB |
Output is correct |
5 |
Correct |
34 ms |
4736 KB |
Output is correct |
6 |
Correct |
135 ms |
4984 KB |
Output is correct |
7 |
Correct |
195 ms |
5120 KB |
Output is correct |
8 |
Correct |
251 ms |
5340 KB |
Output is correct |
9 |
Correct |
382 ms |
5516 KB |
Output is correct |
10 |
Correct |
548 ms |
5752 KB |
Output is correct |
11 |
Correct |
1198 ms |
7000 KB |
Output is correct |
12 |
Correct |
1184 ms |
7092 KB |
Output is correct |
13 |
Correct |
1269 ms |
7160 KB |
Output is correct |
14 |
Correct |
1313 ms |
7072 KB |
Output is correct |
15 |
Correct |
1303 ms |
7160 KB |
Output is correct |