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 <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define int int64_t
using namespace std;
struct dpstruct
{
vector<vector<int>> table;
vector<vector<int>> contprefsum;
vector<int> tasks;
int cont, tcs, stsks;
int getscore(int from, int end)
{
int tms = 0;
for (int i = 0; i < cont; i++)
{
if ((contprefsum[i][end] - contprefsum[i][from]) == 0) tms++;
}
int pts = (tasks[end] - tasks[from]);
return tms * pts;
}
void init(const vector<int> &p, const vector<string> &ip)
{
contprefsum.resize(cont, vector<int>(tcs + 1, 0));
for (int i = 0; i < cont; i++)
{
int curr = 0;
for (int j = 1; j <= tcs; j++)
{
curr += (ip[i][j - 1] == '0');
contprefsum[i][j] = curr;
}
}
tasks.resize(tcs + 1, 0);
int curr = 0;
for (int i = 1; i <= tcs; i++)
{
curr += p[i - 1];
tasks[i] = curr;
}
}
void calculate()
{
table.resize(tcs + 1, vector<int>(stsks + 1, (int)1e12));
table[0][0] = 0;
for (int i = 1; i <= tcs; i++)
{
for (int j = 1; j <= stsks; j++)
{
int mmin = 1e12;
for (int c = 0; c < i; c++)
{
mmin = min(mmin, table[c][j - 1] + getscore(c, i));
}
table[i][j] = mmin;
}
}
//print();
for (int i = 1; i <= stsks; i++)
{
cout << table[tcs][i] << "\n";
}
}
void print()
{
cout << "\n";
for (auto a : table) {for (auto g : a) cout << g << " "; cout << "\n";}
cout << "\n";
for (auto a : contprefsum) {for (auto g : a) cout << g << " "; cout << "\n";}
cout << "\n";
for (auto a : tasks) cout << a << " ";
cout << "\n";
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
dpstruct dps;
cin >> dps.cont >> dps.tcs >> dps.stsks;
vector<int> pnts(dps.tcs);
for (int i = 0; i < dps.tcs; i++)
{
cin >> pnts[i];
}
vector<string> s(dps.cont);
for (int i = 0; i < dps.cont; i++)
{
cin >> s[i];
}
dps.init(pnts, s);
dps.calculate();
}
# | 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... |