oj.uz

Submission #609529

# Submission time Handle Problem Language Result Execution time Memory
609529 2022-07-27T16:54:24 Z Redhood Popeala (CEOI16_popeala) C++14
100 / 100
 379 ms 29728 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1072 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1748 KB Output is correct
2 Correct 8 ms 1684 KB Output is correct
3 Correct 9 ms 1804 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4052 KB Output is correct
2 Correct 51 ms 5332 KB Output is correct
3 Correct 77 ms 6772 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1072 KB Output is correct
3 Correct 10 ms 1748 KB Output is correct
4 Correct 8 ms 1684 KB Output is correct
5 Correct 9 ms 1804 KB Output is correct
6 Correct 39 ms 4052 KB Output is correct
7 Correct 51 ms 5332 KB Output is correct
8 Correct 77 ms 6772 KB Output is correct
9 Correct 104 ms 10312 KB Output is correct
10 Correct 135 ms 13180 KB Output is correct
11 Correct 329 ms 28892 KB Output is correct
12 Correct 319 ms 29692 KB Output is correct
13 Correct 379 ms 29592 KB Output is correct
14 Correct 364 ms 29728 KB Output is correct
15 Correct 358 ms 29516 KB Output is correct