oj.uz

Submission #538456

# Submission time Handle Problem Language Result Execution time Memory
538456 2022-03-17T01:58:18 Z zaneyu Popeala (CEOI16_popeala) C++14
100 / 100
 467 ms 11464 KB 
/*input
2 3 3
4 3 5
101
110
0
1
2
-1
1
2
-1
-1
1
*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define pb push_back
const int maxn=2e4+5;
ll dp[maxn],ndp[maxn];
bool ok[maxn];
string s[maxn];
int cnt[55][maxn];
int turn[maxn][55];
ll mn[55];
int p[55];
int pref[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,S;
    cin>>n>>m>>S;
    REP1(i,m) cin>>pref[i],pref[i]+=pref[i-1];
    REP(i,n){
        cin>>s[i];
        s[i]="0"+s[i];
        REP1(j,m){
            char c=s[i][j];
            cnt[i][j]=cnt[i][j-1]+(c-'0');
        }
    }
    REP(j,n+1){
        int p=0;
        REP1(i,m){
            while(p<i){
                int ans=0;
                REP(a,n){
                    if(cnt[a][i]-cnt[a][p]!=(i-p)) ++ans;
                }
                if(ans<j) break;
                ++p;
            }
            turn[i][j]=p-1;
            //cout<<turn[i][j]<<'\n';
        }
    }
    REP(i,m+1) dp[i]=INT_MAX;
    dp[0]=0;
    REP1(asd,S){
        REP(i,n+1) mn[i]=INT_MAX,p[i]=0;
        REP1(i,m){
            ndp[i]=INT_MAX;
            REP(j,n+1){
                while(p[j]<=turn[i][j]) MNTO(mn[j],dp[p[j]]-(n-j)*pref[p[j]]),p[j]++;
                MNTO(ndp[i],mn[j]+(n-j)*pref[i]);
            }
            //cout<<ndp[i]<<' ';
        }
        REP1(j,m) dp[j]=ndp[j];
        dp[0]=INT_MAX;
        cout<<dp[m]<<'\n';
    }
}

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 1108 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1364 KB Output is correct
2 Correct 11 ms 1364 KB Output is correct
3 Correct 15 ms 1352 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2304 KB Output is correct
2 Correct 82 ms 2776 KB Output is correct
3 Correct 93 ms 3304 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 1108 KB Output is correct
3 Correct 13 ms 1364 KB Output is correct
4 Correct 11 ms 1364 KB Output is correct
5 Correct 15 ms 1352 KB Output is correct
6 Correct 62 ms 2304 KB Output is correct
7 Correct 82 ms 2776 KB Output is correct
8 Correct 93 ms 3304 KB Output is correct
9 Correct 133 ms 4656 KB Output is correct
10 Correct 194 ms 5580 KB Output is correct
11 Correct 342 ms 11252 KB Output is correct
12 Correct 413 ms 11456 KB Output is correct
13 Correct 464 ms 11432 KB Output is correct
14 Correct 467 ms 11464 KB Output is correct
15 Correct 467 ms 11464 KB Output is correct