Submission #490547

#	Time	Username	Problem	Language	Result	Execution time	Memory
490547		SirCovidThe19th	Popeala (CEOI16_popeala)	C++17	100 / 100	395 ms	18276 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ll long long

const int mN = 55, mT = 20005;

int n, t, s, pts[mT], mat[mN][mT], lft[mT][mN]; ll dp[mT][mN];

int main(){
    cin >> n >> t >> s;
    FOR(tst, 1, t + 1) cin >> pts[tst], pts[tst] += pts[tst - 1];
    FOR(p, 1, n + 1) FOR(tst, 1, t + 1){
        char c; cin >> c;
        mat[p][tst] = c - '0';
        lft[tst][p] = (!mat[p][tst] ? tst : lft[tst - 1][p]);
    }
    FOR(tst, 1, t + 1) lft[tst][0] = tst, sort(lft[tst], lft[tst] + n + 1);

    memset(dp, 0x3f, sizeof(dp)); dp[0][0] = 0;
    FOR(subT, 1, s + 1){
        ll bst[n + 1]; memset(bst, 0x3f, sizeof(bst));
        FOR(tst, 1, t + 1){
            FOR(correct, 0, n + 1){
                FOR(x, lft[tst - 1][correct], lft[tst][correct]){
                    bst[correct] = min(bst[correct], dp[x][subT - 1] - pts[x] * correct);
                }
                dp[tst][subT] = min(dp[tst][subT], bst[correct] + pts[tst] * correct);
            }
        }
        cout<<dp[t][subT]<<"\n";
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74