Submission #609173

#	Time	Username	Problem	Language	Result	Execution time	Memory
609173		SlavicG	Popeala (CEOI16_popeala)	C++17	100 / 100	346 ms	20188 KiB

popeala

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74