oj.uz

Submission #608794

# Submission time Handle Problem Language Result Execution time Memory
608794 2022-07-27T10:14:09 Z generic_placeholder_name Popeala (CEOI16_popeala) C++17
100 / 100
 330 ms 17764 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 8916 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9172 KB Output is correct
2 Correct 10 ms 9044 KB Output is correct
3 Correct 11 ms 9172 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9900 KB Output is correct
2 Correct 60 ms 10316 KB Output is correct
3 Correct 63 ms 10708 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 8916 KB Output is correct
3 Correct 11 ms 9172 KB Output is correct
4 Correct 10 ms 9044 KB Output is correct
5 Correct 11 ms 9172 KB Output is correct
6 Correct 45 ms 9900 KB Output is correct
7 Correct 60 ms 10316 KB Output is correct
8 Correct 63 ms 10708 KB Output is correct
9 Correct 83 ms 11800 KB Output is correct
10 Correct 149 ms 12684 KB Output is correct
11 Correct 189 ms 17740 KB Output is correct
12 Correct 212 ms 17760 KB Output is correct
13 Correct 284 ms 17756 KB Output is correct
14 Correct 274 ms 17760 KB Output is correct
15 Correct 330 ms 17764 KB Output is correct