Submission #608794

#	Time	Username	Problem	Language	Result	Execution time	Memory
608794		generic_placeholder_name	Popeala (CEOI16_popeala)	C++17	100 / 100	330 ms	17764 KiB

popeala

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 55, T = 20005;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

ll dp[T][N], a[T], prv[T][N], best[N];

int32_t main() {
    fastio;
    int n, t, s; cin >> n >> t >> s;
    rep1(i, t) cin >> a[i], a[i] += a[i - 1];
    rep1(i, n) {
        string s; cin >> s;
        rep(j, t) prv[j + 1][i] = s[j] == '1' ? prv[j][i] : j + 1;
    }
    rep1(i, t) {
        prv[i][0] = i;
        sort(prv[i], prv[i] + n + 1);
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    rep1(i, s) {
        rep(j, n + 1) best[j] = INF;
        rep1(j, t) rep(k, n + 1) {
            for(int l = prv[j - 1][k]; l < prv[j][k]; l++) best[k] = min(best[k], dp[l][i - 1] - a[l] * k);
            dp[j][i] = min(dp[j][i], best[k] + a[j] * k);
        }
        cout << dp[t][i] << endl;
    }
}

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