oj.uz

Submission #536947

# Submission time Handle Problem Language Result Execution time Memory
536947 2022-03-14T07:59:43 Z FatihSolak Popeala (CEOI16_popeala) C++17
100 / 100
 714 ms 249932 KB 
#include <bits/stdc++.h>
#define T 20005
#define N 55
using namespace std;
int mini[T][N][N];
int st[T][N];
int dp[T][N];
int points[T];
int nxt[N][T];
void solve(){
    int n,t,s;
    cin >> n >> t >> s;
    for(int i=1;i<=t;i++){
        cin >> points[i];
        points[i] += points[i-1];
    }
    for(int i=1;i<=n;i++){
        string ss;
        cin >> ss;
        nxt[i][t+1] = t+1;
        for(int j = t;j>=0;j--){
            if(j && ss[j-1] == '0')
                nxt[i][j] = j;
            else nxt[i][j] = nxt[i][j+1];
        }
    }
    for(int i=0;i<=t;i++){
        vector<int> v;
        for(int j = 1;j<=n;j++){
            v.push_back(nxt[j][i]);
        }
        sort(v.begin(),v.end());
        int cnt = n;
        st[i][cnt] = i;
        for(auto u:v){
            cnt--;
            st[i][cnt] = u;
        }
    }
    for(int i = 0;i<T;i++){
        for(int j = 0;j<N;j++){
            for(int c = 0;c<N;c++){
                mini[i][j][c] = 2e9;
            }
            dp[i][j] = 2e9;
        }
    }
    dp[0][0] = 0;
    for(int x = 0;x<s;x++){
        for(int i = 0;i<t;i++){
            for(int j = 0;j<=n;j++){
                //cout << st[i + 1][j] << " ";
                mini[st[i + 1][j]][x+1][j] = min(mini[st[i + 1][j]][x+1][j], dp[i][x] - j * points[i]);
            }
            //cout << endl;
        }
        //cout << endl;
        for(int i = 1;i<=t;i++){
            for(int j = 0;j<=n;j++){
                mini[i][x+1][j] = min(mini[i][x+1][j],mini[i-1][x+1][j]);
                dp[i][x+1] = min(dp[i][x+1], mini[i][x+1][j] + j * points[i]);
            }
            //cout << x+1 << " " << i << " " << dp[i][x+1] << endl;
        }
        //cout << endl;
    }
    for(int i=1;i<=s;i++){
        cout << dp[t][i] << endl;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 241376 KB Output is correct
2 Correct 133 ms 241608 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 241828 KB Output is correct
2 Correct 136 ms 241884 KB Output is correct
3 Correct 145 ms 241856 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 242528 KB Output is correct
2 Correct 185 ms 242860 KB Output is correct
3 Correct 244 ms 243292 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 241376 KB Output is correct
2 Correct 133 ms 241608 KB Output is correct
3 Correct 133 ms 241828 KB Output is correct
4 Correct 136 ms 241884 KB Output is correct
5 Correct 145 ms 241856 KB Output is correct
6 Correct 174 ms 242528 KB Output is correct
7 Correct 185 ms 242860 KB Output is correct
8 Correct 244 ms 243292 KB Output is correct
9 Correct 265 ms 244300 KB Output is correct
10 Correct 359 ms 245232 KB Output is correct
11 Correct 642 ms 249680 KB Output is correct
12 Correct 669 ms 249888 KB Output is correct
13 Correct 679 ms 249840 KB Output is correct
14 Correct 698 ms 249932 KB Output is correct
15 Correct 714 ms 249836 KB Output is correct