Submission #609529

#	Time	Username	Problem	Language	Result	Execution time	Memory
609529		Redhood	Popeala (CEOI16_popeala)	C++14	100 / 100	379 ms	29728 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;
#define int long long
const int inf = 2e11 + 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]);
}

signed 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]));
        reverse(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];

    int mn[t][n+1];
    for(int k = 2; k <= s; ++k){
        bt ^= 1;
        fill(dp[bt], dp[bt] + T, inf);


        for(int i = 0 ; i < t; ++i){
            for(int j = 0;j <= n; ++j){
                if(dp[bt^1][i] == inf)
                    mn[i][j]=inf;
                else
                    mn[i][j] = dp[bt^1][i] - pref[i] * j;
                if(i - 1 >= 0)
                    mn[i][j]=min(mn[i][j],mn[i-1][j]);
            }
        }
        for(int i = 0; i < t; ++i){
            int ptr = 0;
            int x=n;

            if(i - 1 >= 0)
            dp[bt][i] = min(dp[bt][i], mn[i-1][n] + pref[i] *n);

            while(ptr < sz(id[i])){
                x--;
                while(ptr + 1 < sz(id[i]) && id[i][ptr + 1] == id[i][ptr]){
                    ptr++;
                    x--;
                }
                if(id[i][ptr] <= 0)
                    break;
                int ps = id[i][ptr]-1;


                if(mn[ps][x]!=inf)
                dp[bt][i] = min(dp[bt][i],mn[ps][x] + pref[i] * x);
                ptr++;
            }
        }

        ans[k] = dp[bt][t - 1];
    }
    for(int k = 1; k <= s; ++k)
        cout << ans[k] << '\n';
    return 0;
}

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