oj.uz

Submission #609173

# Submission time Handle Problem Language Result Execution time Memory
609173 2022-07-27T12:38:37 Z SlavicG Popeala (CEOI16_popeala) C++17
100 / 100
 346 ms 20188 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
#define int long long
const int N = 55, T = 2e4 + 10;
string c[N];
int p[T], pf[T];
int dp[T][N];
int pref[N][T];
int pr[T];
int idx[T][N];
void solve() {
    int n, t, s; cin >> n >> t >> s;
    for(int i = 1; i <= t; ++i) cin >> p[i];
    for(int i = 1; i <= t; ++i) {
        pr[i] = p[i];
        pr[i] += pr[i - 1];
    }
    for(int i = 1; i <= n; ++i) {
        cin >> c[i];
        for(int j = 1; j <= t; ++j) {
            if(c[i][j - 1] == '1') {
                idx[j][i] = idx[j - 1][i];
            } else {
                idx[j][i] = j;
            }
        }
    }
    for(int i = 1; i <= t; ++i) {
        idx[i][0] = i;
        sort(idx[i], idx[i] + n + 1);
    }
    forn(i, T) forn(j, N) dp[i][j] = 1e16;
    dp[0][0] = 0;
    for(int ss = 1; ss <= s; ++ss) {
        vector<int> cur(n + 1, 1e16);
        for(int i = 1; i <= t; ++i) {
            for(int k = 0; k <= n; ++k) {
                for(int j = idx[i - 1][k]; j < idx[i][k]; ++j) {
                    cur[k] = min(cur[k], dp[j][ss - 1] - k * pr[j]); 
                }
                dp[i][ss] = min(dp[i][ss], cur[k] + k * pr[i]);
            }
        }
    }
    for(int i = 1; i <= s; ++i) {
        cout << dp[t][i] << "\n";
    }
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

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 8900 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10152 KB Output is correct
2 Correct 57 ms 10612 KB Output is correct
3 Correct 79 ms 11148 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 8900 KB Output is correct
3 Correct 12 ms 9172 KB Output is correct
4 Correct 10 ms 9232 KB Output is correct
5 Correct 10 ms 9172 KB Output is correct
6 Correct 45 ms 10152 KB Output is correct
7 Correct 57 ms 10612 KB Output is correct
8 Correct 79 ms 11148 KB Output is correct
9 Correct 69 ms 12500 KB Output is correct
10 Correct 128 ms 13696 KB Output is correct
11 Correct 278 ms 20036 KB Output is correct
12 Correct 250 ms 20188 KB Output is correct
13 Correct 278 ms 20168 KB Output is correct
14 Correct 280 ms 20176 KB Output is correct
15 Correct 346 ms 20176 KB Output is correct