#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
int n, t, s;
long long a[20005];
vector<int> go[20005];
long long f[55][20005];
char board[55][20005];
template<class num_t>
struct range {
num_t a[20005];
num_t f[15][20005];
void upd(int u,num_t v) {
a[u] = v;
}
void build() {
for (int i = 0; i <= t; ++i) f[0][i] = a[i];
for (int i = 1; i <= 14; ++i) {
for (int j = 0; j + (1 << i) - 1 <= t; ++j) {
f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
}
}
num_t get(int l,int r) {
int LG = __lg(r - l + 1);
return min(f[LG][l], f[LG][r - (1 << LG) + 1]);
}
};
range<long long> rmq[55];
int main() {
scanf("%d %d %d", &n, &t, &s);
for (int i = 1; i <= t; ++i) {
scanf("%lld", a + i);
a[i] += a[i - 1];
}
for (int i = 0; i < n; ++i) {
scanf("%s", board[i] + 1);
}
for (int i = 0; i < n; ++i) {
go[0].push_back(0);
}
for (int i = 1; i <= t; ++i) {
for (int j = 0; j < n; ++j) {
if (board[j][i] == '0') {
go[i].push_back(i);
} else {
go[i].push_back(go[i - 1][j]);
}
}
}
for (int i = 0; i <= t; ++i) {
sort(go[i].begin(), go[i].end());
}
for (int i = 0; i <= s; ++i) {
for (int j = 0; j <= t; ++j) {
f[i][j] = 1e18;
}
}
f[0][0] = 0;
for (int id = 0; id < s; ++id) {
for (int l = 0; l <= t; ++l) {
for (int num = 0; num <= n; ++num) {
rmq[num].upd(l, f[id][l] - a[l] * num);
}
}
for (int num = 0; num <= n; ++num) {
rmq[num].build();
}
for (int r = 0; r <= t; ++r) {
if (go[r].back() != r) go[r].push_back(r);
if (go[r].front()) {
f[id + 1][r] = rmq[0].get(0, go[r].front() - 1);
}
for (int num = 1; num < int(go[r].size()); ++num) {
if (go[r][num] > go[r][num - 1]) {
f[id + 1][r] = min(f[id + 1][r], rmq[num].get(go[r][num - 1], go[r][num] - 1) + a[r] * num);
}
}
}
}
for (int i = 1; i <= s; ++i) {
printf("%lld\n", f[i][t]);
}
}#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
int n, t, s;
long long a[20005];
vector<int> go[20005];
long long f[55][20005];
char board[55][20005];
template<class num_t>
struct range {
num_t a[20005];
num_t f[15][20005];
void upd(int u,num_t v) {
a[u] = v;
}
void build() {
for (int i = 0; i <= t; ++i) f[0][i] = a[i];
for (int i = 1; i <= 14; ++i) {
for (int j = 0; j + (1 << i) - 1 <= t; ++j) {
f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
}
}
num_t get(int l,int r) {
int LG = __lg(r - l + 1);
return min(f[LG][l], f[LG][r - (1 << LG) + 1]);
}
};
range<long long> rmq[55];
int main() {
scanf("%d %d %d", &n, &t, &s);
for (int i = 1; i <= t; ++i) {
scanf("%lld", a + i);
a[i] += a[i - 1];
}
for (int i = 0; i < n; ++i) {
scanf("%s", board[i] + 1);
}
for (int i = 0; i < n; ++i) {
go[0].push_back(0);
}
for (int i = 1; i <= t; ++i) {
for (int j = 0; j < n; ++j) {
if (board[j][i] == '0') {
go[i].push_back(i);
} else {
go[i].push_back(go[i - 1][j]);
}
}
}
for (int i = 0; i <= t; ++i) {
sort(go[i].begin(), go[i].end());
}
for (int i = 0; i <= s; ++i) {
for (int j = 0; j <= t; ++j) {
f[i][j] = 1e18;
}
}
f[0][0] = 0;
for (int id = 0; id < s; ++id) {
for (int l = 0; l <= t; ++l) {
for (int num = 0; num <= n; ++num) {
rmq[num].upd(l, f[id][l] - a[l] * num);
}
}
for (int num = 0; num <= n; ++num) {
rmq[num].build();
}
for (int r = 0; r <= t; ++r) {
if (go[r].back() != r) go[r].push_back(r);
if (go[r].front()) {
f[id + 1][r] = rmq[0].get(0, go[r].front() - 1);
}
for (int num = 1; num < int(go[r].size()); ++num) {
if (go[r][num] > go[r][num - 1]) {
f[id + 1][r] = min(f[id + 1][r], rmq[num].get(go[r][num - 1], go[r][num] - 1) + a[r] * num);
}
}
}
}
for (int i = 1; i <= s; ++i) {
printf("%lld\n", f[i][t]);
}
}
Compilation message
popeala.cpp:89:2: error: stray '#' in program
}#pragma GCC optimize("O3")
^
popeala.cpp:89:3: error: 'pragma' does not name a type; did you mean '_Pragma'?
}#pragma GCC optimize("O3")
^~~~~~
_Pragma
popeala.cpp:90:30: error: expected declaration before end of line
#pragma GCC optimize("Ofast")
^
popeala.cpp: In function 'int main()':
popeala.cpp:36:7: 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:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", a + i);
~~~~~^~~~~~~~~~~~~~~
popeala.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", board[i] + 1);
~~~~~^~~~~~~~~~~~~~~~~~~~
