#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)
// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
const int INF = 2e9 + 5;
const int MAX_N = 55;
const int MAX_T = 2e4 + 5;
int pts[MAX_T];
int len[MAX_T][MAX_N];
char str[MAX_T];
int dp[MAX_N][MAX_T];
bool seen[MAX_N];
int pref[MAX_N][MAX_T];
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n, t, s;
scanf("%d %d %d", &n, &t, &s);
for (int i = 1; i <= t; i++) {
scanf("%d", &pts[i]);
pts[i] += pts[i - 1];
}
for (int i = 1; i <= n; i++) {
scanf(" %s", str + 1);
for (int j = 1; j <= t; j++) {
if (str[j] == '1')
len[j][i] = len[j - 1][i] + 1;
else
len[j][i] = 0;
}
}
for (int k = 1; k <= s; k++) {
for (int i = 1; i <= t; i++) {
dp[k][i] = INF;
if (i < k) continue;
memset(seen, false, sizeof seen);
int pos = i;
int x = n;
for (int j = 1; j <= n; j++) {
if (len[i][j] == 0) {
seen[j] = true;
x--;
}
}
while (true) {
//printf("for (k: %d, i: %d) now at (pos: %d, x: %d)\n", k, i, pos, x);
if (pos < k) break;
if (x < 0) break;
dp[k][i] = min(dp[k][i], pref[x][pos - 1] + x * pts[i]);
int who = -1, nxt = 0;
for (int j = 1; j <= n; j++)
if (!seen[j] && pos - len[i][j] > nxt) {
nxt = pos - len[i][j];
who = j;
}
if (who == -1) break;
seen[who] = true;
pos = nxt;
x--;
}
}
for (int x = 0; x <= n; x++) {
pref[x][k - 1] = INF;
for (int i = k; i <= t; i++) {
pref[x][i] = min(pref[x][i - 1], dp[k][i] - x * pts[i]);
//printf("pref[%d][%d] = %d\n", x, i, pref[x][i]);
}
}
}
for (int k = 1; k <= s; k++)
printf("%d\n", dp[k][t]);
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &t, &s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &pts[i]);
~~~~~^~~~~~~~~~~~~~~
popeala.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", str + 1);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
616 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
1332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
934 ms |
2364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
616 KB |
Output isn't correct |
