oj.uz

Submission #968386

# Submission time Handle Problem Language Result Execution time Memory
968386 2024-04-23T11:16:29 Z berr Popeala (CEOI16_popeala) C++17
100 / 100
 508 ms 15696 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4+30;
 
int gh[57][57];
int pref[55][N];
vector<int> v;
 int n, s, t;
long long dis[N][55];

int r(int l, int r){
    int ans=0;
    for(int i=0; i<n; i++){
        int val=pref[i][r];
        if(l>0) val-=pref[i][l-1];

        if(val==r-l+1) ans++;
    }
    return ans;
}
long long calc(int ri, int l, int f, long long kac){
    if(l<=t && f <= s && ri <t){
        if(dis[l][f]==(long long)1e10) return (long long)1e10;
        long long h = dis[l][f];
        long long gh = v[ri];
        if(l) gh-=v[l-1];
        return h+kac*gh;
    }
    return (long long) 1e10;
};

void solve(){
     cin >> n >> t >> s;
    v.resize(t);
    for(int i=0; i<=t; i++){
        for(int l=0; l<=s; l++){
            dis[i][l] = 1e10;
        }
    }
 
    for(auto &i: v) cin >> i;
 
    vector<string> se(n);
 
    for(auto &i: se){
        cin >> i;
    } 
    
    for(int i=0; i<n; i++){
        if(se[i][0]=='1') pref[i][0]++;
        for(int l=1; l<t; l++){
            pref[i][l] = pref[i][l-1] + se[i][l]-'0';

        }
    }

    for(int i=1; i<t; i++) v[i] += v[i-1];
 
    int h=0;
 
 
    for(int i=0; i<55; i++){
        for(int l=0; l<55; l++){
            gh[i][l]=-1;
        }
    }
 
   // assert((h < 55*t));
    gh[0][0]=0;
    dis[0][0]=0;
        
    vector<int> val(t, n);
    vector<int> last(t, -1);

    for(int i=0; i<=t; i++){
        //hah;  

         for(int j=0; j<50; j++){
            for(int el=0; el<=50; el++){
                if(gh[j][el]!=-1){
                    if(i!=0)
                    dis[i][j+1] = min(dis[i][j+1], calc(i-1, gh[j][el], j, val[gh[j][el]]));
                 
                }
            }
        }


    
        val[i]=n;
        for(int l=0; l<n; l++){
            if(se[l][i]=='0'){
                for(int j=i; j>last[l]; j--){
                    val[j]--;
                }
                last[l] = i;
            }
        }
   

        if(i!=t)
        for(int l=0; l<n; l++){
            if(se[l][i]=='0'){
                for(int j=i-1; j>=0; j--){
                    if(se[l][j]=='0') break;
                    
                    int el = val[j];// kaç tane
         
                    for(int k=0; k<s; k++){
         
                        if(gh[k][el]==-1) gh[k][el]=j;
                        else{
                            int tel = val[gh[k][el]];
                            int val_new = calc(i, j, k, el);
                            int val_old = calc(i, gh[k][el], k, tel);
                            if(val_new < val_old){
                                gh[k][el] = j;  
                            }
                        }
                    }
                }
            }
        }
        int el = val[i]; // kaç tane
         
         
        for(int k=0; k<s; k++){

            if(gh[k][el]==-1) gh[k][el]=i;
            else{
                int tel = r(gh[k][el], i);
                int val_new = calc(i, i, k, el);
                int val_old = calc(i, gh[k][el], k, tel);
                if(val_new < val_old){
                    gh[k][el] = i;  
                }
            }
        }
    
    
    }
 
    for(int i=1; i<=s; i++) cout<<dis[t][i]<<"\n";
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    /*freopen("popeala.in", "r", stdin);
    freopen("popeala.out", "w", stdout);
*/
    solve();

    cerr<<clock()/1000.0;
}

Compilation message

popeala.cpp: In function 'void solve()':
popeala.cpp:59:9: warning: unused variable 'h' [-Wunused-variable]
   59 |     int h=0;
      |         ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6744 KB Output is correct
2 Correct 13 ms 6864 KB Output is correct
3 Correct 13 ms 6748 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 7040 KB Output is correct
2 Correct 77 ms 7004 KB Output is correct
3 Correct 102 ms 7260 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 13 ms 6744 KB Output is correct
4 Correct 13 ms 6864 KB Output is correct
5 Correct 13 ms 6748 KB Output is correct
6 Correct 55 ms 7040 KB Output is correct
7 Correct 77 ms 7004 KB Output is correct
8 Correct 102 ms 7260 KB Output is correct
9 Correct 155 ms 9564 KB Output is correct
10 Correct 223 ms 10068 KB Output is correct
11 Correct 486 ms 15196 KB Output is correct
12 Correct 494 ms 15696 KB Output is correct
13 Correct 505 ms 15544 KB Output is correct
14 Correct 508 ms 15448 KB Output is correct
15 Correct 495 ms 15576 KB Output is correct