Submission #1236425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236425		neisenn	Popeala (CEOI16_popeala)	C++20	100 / 100	187 ms	9652 KiB

popeala

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const char nl = '\n';
const ll inf = 2e9+1;
const int N = 51, T = 20001;
int val[T], pref[T], lst[T][N];
bool res[T][N];
int dp[N][T];

void solve(){
    int n, t, s;
    cin >> n >> t >> s;
    for (int i = 1; i <= t; i++){
        cin >> val[i];
        pref[i] = pref[i-1]+val[i];
    }
    for (int i = 1; i <= n; i++){ 
        string s; cin >> s;
        for (int j = 1; j <= t; j++){
            res[j][i] = (s[j-1] == '1');
            lst[j][i] = (!res[j][i] ? j : lst[j-1][i]);
        }
    }
    for (int i = 1; i <= t; i++){ 
        lst[i][0] = i;
        sort(lst[i], lst[i]+n+1);
    } 
    for (int i = 0; i <= s; i++){
        for (int j = 0; j <= t; j++){
            dp[i][j] = inf;
        }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= s; i++){
        vector<int> best(n+1, inf);
        for (int j = 1; j <= t; j++){
            for (int cnt = 0; cnt <= n; cnt++){
                for (int k = lst[j-1][cnt]; k < lst[j][cnt]; k++){
                    best[cnt] = min(best[cnt], dp[i-1][k]-cnt*pref[k]);
                }
                dp[i][j] = min(dp[i][j], best[cnt]+cnt*pref[j]);
            }
        }
    }
    for (int i = 1; i <= s; i++){
        cout << dp[i][t] << nl;
    }
}

int 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