# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90805 | EntityIT | Popeala (CEOI16_popeala) | C++14 | 7 ms | 5256 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 55, T = 2e4 + 5, inf = (int)2e9 + 123;
int n, t, s, points[T], lst[N][T], sum[N][T], dp[N][T];
vector<int> vec[T];
char res[N][T];
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("popeala.in", "r", stdin);
freopen("popeala.out", "w", stdout);
cin >> n >> t >> s;
for (int j = 1; j <= t; ++j) {
cin >> points[j];
for (int i = 0; i <= n; ++i) sum[i][j] = sum[i][j - 1] + points[j] * i;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= t; ++j) cin >> res[i][j];
}
for (int i = 1; i <= n; ++i) {
int last = 0;
for (int j = 1; j <= t; ++j) { if (res[i][j] == '0') last = j; lst[i][j] = last; }
}
for (int j = 1; j <= t; ++j) {
vec[j].pb(0); vec[j].pb(j);
for (int i = 1; i <= n; ++i) vec[j].pb(lst[i][j]);
sort(vec[j].begin(), vec[j].end() ); reverse(vec[j].begin(), vec[j].end() );
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < T; ++j) dp[i][j] = inf;
}
dp[0][0] = 0;
for (int i = 1; i <= s; ++i) {
// cout << "i = " << i << "*****\n";
deque<int> deq[N];
for (int j = 1; j <= t; ++j) {
// cout << "j = " << j << '\n';
vector<int> change = vec[j];
int iChange = 0;
while (iChange + 1 < change.size() ) {
do { iChange ++; } while (iChange + 1 < change.size() && change[iChange] == change[iChange - 1]);
int l = change[iChange], r = change[iChange - 1] - 1;
if (r != -1) {
// cout << "l = " << l << " r = " << r << ' ' << n - iChange + 1 << '\n';
while (deq[n - iChange + 1].size() && deq[n - iChange + 1].front() < l) deq[n - iChange + 1].pop_back();
if (!deq[n - iChange + 1].size() ) deq[n - iChange + 1].push_back(l);
while (deq[n - iChange + 1].size() && deq[n - iChange + 1].back() < r) {
int nxt = deq[n - iChange + 1].back() + 1;
while (deq[n - iChange + 1].size() &&
dp[i - 1][ deq[n - iChange + 1].back() ] - sum[n - iChange + 1][ deq[n - iChange + 1].back() ]
> dp[i - 1][nxt] - sum[n - iChange + 1][nxt]) deq[n - iChange + 1].pop_back();
deq[n - iChange + 1].push_back(nxt);
}
}
int tmp = (deq[n - iChange + 1].size() && dp[i - 1][ deq[n - iChange + 1].front() ] != inf ? dp[i - 1][ deq[n - iChange + 1].front() ]
- sum[n - iChange + 1][ deq[n - iChange + 1].front() ] : inf);
if (tmp != inf) dp[i][j] = min(dp[i][j], tmp + sum[n - iChange + 1][j]);
}
// cout << dp[i][j] << "+++++\n";
}
}
for (int i = 1; i <= s; ++i) cout << dp[i][t] << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |