Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Try not to think about the whole answer key at once. What happens if you focus on just one question ?
The choice of correct answer for question does not affect the score from any other question. So the total score is a sum of independent column contributions.
For a fixed question with value , if the correct answer is letter , then the class earns points, where is how many students chose .
Since each question has only five choices , just count their frequencies in every column.
For every question , take the largest frequency among its five letters and add to the answer. That's literally the whole problem — no DP goblin hiding here.
The exam key can be chosen after seeing all student answers, and everyone is being extremely optimistic. For each question, we are free to choose whichever option gives the most total points.
Let be the answer of student to question . Suppose the correct answer for question is . Then exactly
students get that question right, so this question contributes
points to the total class score.
The answer chosen for question does not affect any other question. Therefore, instead of searching over all possible answer keys — which would be hilariously doomed — we optimize each question independently.
For question , the best possible correct answer is simply the most common letter in column :
So the final answer is
We inspect each character once, so the time complexity is
Memory usage is
which is tiny. With , this is comfortably within limits.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int n, m;
cin >> n >> m;
vector<array<int, 5>> cnt(m);
for (auto &x : cnt) x.fill(0);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
cnt[j][s[j] - 'A']++;
}
}
ll ans = 0;
for (int j = 0; j < m; j++) {
int points;
cin >> points;
int best = *max_element(cnt[j].begin(), cnt[j].end());
ans += 1LL * best * points;
}
cout << ans << '\n';
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int n, m;
cin >> n >> m;
vector<array<int, 5>> cnt(m);
for (auto &x : cnt) x.fill(0);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
cnt[j][s[j] - 'A']++;
}
}
ll ans = 0;
for (int j = 0; j < m; j++) {
int points;
cin >> points;
int best = *max_element(cnt[j].begin(), cnt[j].end());
ans += 1LL * best * points;
}
cout << ans << '\n';
}