Submission #1234566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234566		broskiz	Popeala (CEOI16_popeala)	C++20	100 / 100	244 ms	8832 KiB

popeala

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

#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
// DEBUGING TEMPLETE ////////////////////////////////////////////////////////////////////////
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL_DEBUG   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif

template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}

int a[20005], mi[55], lt[20005][55], dp[55][20005];

int inf = 1e9;
int main() {
    int n, t, s;
    cin >> n >> t >> s;
    for (int i =  1; i <= t; ++i) {
        cin >> a[i];
        a[i] += a[ i - 1];
    }

    for (int i = 0; i < n; ++i) {
        string ss; 
        cin >> ss;
        for (int j = 0; j < t; ++j) {
            lt[j + 1][i] = ss[j] == '1' ? lt[j][i] : j + 1;
        }
    }

    for (int i = 1; i <= t; ++i) {
        lt[i][n] = i;
        sort(lt[i], lt[i] + n + 1);
    }

    fill(dp[0] + 1, dp[0] + t + 1, inf);
    for (int i = 1; i <= s; ++i) {
        fill(mi, mi + n + 1, inf);
        dp[i][0] = inf;
        for (int j = 1; j <= t; ++j) {
            dp[i][j] = inf;
            for (int k = 0; k <= n; ++k) {
                for (int p = lt[j - 1][k]; p < lt[j][k]; ++p) {
                    if (dp[i - 1][p] ^ inf) {
                        mi[k] = min(mi[k], dp[i - 1][p] - a[p] * k);
                    }
                }
                if (mi[k] ^ inf) {
                    dp[i][j] = min(dp[i][j], mi[k] + a[j] * k);
                }
            }
        }
        cout << dp[i][t] << "\n";
    }
}

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