Submission #609505

#	Time	Username	Problem	Language	Result	Execution time	Memory
609505		Redhood	Popeala (CEOI16_popeala)	C++14	0 / 100	19 ms	2004 KiB

popeala

#include <bits/stdc++.h>
#define fi first
#define se second

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;


typedef long long ll;
typedef long double ld;

const int inf = 2e9 + 1;
const int T = 20'000;
const int S = 51;
int dp[2][T];

vector<int>id[T];

vector<int>pref;
int get(int l , int r){
 return pref[r] - (l == 0 ? 0 : pref[l - 1]);
}
void solve(int bt, int l , int r , int optl , int optr){
    int mid = (l + r) >> 1;

    int opt = -1;
    int mx = inf;
    int cand =-1;
    for(int i = optl; i < min(optr+1, mid); ++i){

        int cost = dp[bt^1][i];
        cost += (lower_bound(all(id[mid]), i+1)-id[mid].begin()) * get(i+1, mid);

//        cout << " mid " << mid << ' ';
//        for(auto &x : id[mid])cout << x << ' ';
//        cout << '\n';
//        cerr << " fuk " << (lower_bound(all(id[mid]), i+1)-id[mid].begin()) << ' ' << bt << ' ' << mid << ' ' << i << endl;
        if(cost < mx){
            mx = cost;
            cand = i;
        }
    }
    dp[bt][mid] = mx;
    if(l <= mid - 1)
        solve(bt, l , mid - 1 , optl , cand);
    if(mid + 1 <= r)
        solve(bt, mid + 1 , r , cand , optr);
}
int main()
{
    int t, n , s;
    cin >> n >> t >> s;
    vector < int > score(t);
    for(auto &i : score)
    cin >> i;


    vector < string > capble;
    for(int i = 0; i < n; ++i){
        string s;
        cin >> s;
        capble.pb(s);
    }

    pref.resize(t);
    pref[0] = score[0];
    for(int i = 1; i < t; ++i){
        pref[i] = pref[i - 1] + score[i];
    }



    int left[t][n];

    for(int i = 0;i < n; ++i){
        int cur = -1;
        for(int j = 0; j < t; ++j){
            if(capble[i][j] == '0')
                cur = j;
            left[j][i] = cur;
        }

    }
//    return 0;
    /// yo
    for(int i = 0; i < 2; ++i)
        fill(dp[i] , dp[i] + T , inf);
//    return 0;
    vector<int>ans(s + 1);
    int bt = 0;
    for(int i = 0; i < t; ++i){
        int c = 0;
        for(int f=0;f<n;++f){
            if(left[i][f]==-1)
                c++;
        }

        dp[bt][i] = get(0,i) * c;
    }
//    return 0;
    for(int i = 0; i < t; ++i){
        for(int j = 0; j < n; ++j){
            id[i].pb(left[i][j]);
        }
        sort(all(id[i]));
    }
//    cout << " ID \n";
//    for(int i = 0; i < t; ++i){
//        cout << "i " << i << '\n';
//        for(auto &u : id[i])cout << u << ' ';
//        cout << '\n';
//    }
    ans[1] = dp[bt][t - 1];
    for(int k = 2; k <= s; ++k){
        bt ^= 1;
        fill(dp[bt], dp[bt] + T, inf);
        solve(bt, 0, t-1, 0 , t-1);
        ans[k] = dp[bt][t - 1];
    }
    for(int k = 1; k <= s; ++k)
        cout << ans[k] << ' ';
    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'void solve(int, int, int, int, int)':
popeala.cpp:29:9: warning: unused variable 'opt' [-Wunused-variable]
   29 |     int opt = -1;
      |         ^~~

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