Submission #955280

#	Time	Username	Problem	Language	Result	Execution time	Memory
955280		parlimoos	Popeala (CEOI16_popeala)	C++14	0 / 100	68 ms	12912 KiB

popeala

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

const int INF = int(2e9) + 1;

int n , m , k;
vector<int> a;
bool ans[50][20000];
int dp[51][20000] , opt[51][20000];
int psans[50][20000] , chs[20000][2];

void init(){
    for(int i = 0 ; i < m ; i++){
        for(int j = 0 ; j < n ; j++){
            psans[i][j] = int(ans[i][j]);
            if(j > 0) psans[i][j] += psans[i][j - 1];
        }
    }
    for(int i = 1 ; i < n ; i++) a[i] += a[i - 1];
}
void initTr(int l = 0 , int r = n - 1){
    int c = (r + l) >> 1;
    int ch1 = (c - 1 + l) >> 1 , ch2 = (r + c + 1) >> 1;
    if(c - 1 < l) ch1 = -1;
    if(c + 1 > r) ch2 = -1;
    chs[c][0] = ch1 , chs[c][1] = ch2;
    if(ch1 != -1) initTr(l , c - 1);
    if(ch2 != -1) initTr(c + 1 , r);
}
int getSg(int l , int r){
    int res = 0;
    for(int i = 0 ; i < m ; i++){
        int d = psans[i][r];
        if(l > 0) d -= psans[i][l - 1];
        if(d == r - l + 1){
            res += a[r];
            if(l > 0) res -= a[l - 1];
        }
    }
    return res;
}
void getOpt(int i , int l , int r , int s){
    if(i + s > n){
        opt[s][i] = n - 1 , dp[s][i] = INF;
        if(chs[i][0] != -1) getOpt(chs[i][0] , opt[s][i] , r , s);
        if(chs[i][1] != -1) getOpt(chs[i][1] , l , opt[s][i] , s);
        return;
    }
    opt[s][i] = i , dp[s][i] = getSg(i , i) + dp[s - 1][i + 1];
    for(int j = max(l , i) ; j <= min(r , n - s) ; j++){
        int d = getSg(i , j) + dp[s - 1][j + 1];
        if(d <= dp[s][i]) opt[s][i] = j , dp[s][i] = d;
    }
    if(chs[i][0] != -1) getOpt(chs[i][0] , opt[s][i] , r , s);
    if(chs[i][1] != -1) getOpt(chs[i][1] , l , opt[s][i] , s);
}
void f(){
    for(int i = 0 ; i < n ; i++){
        opt[1][i] = n - 1 , dp[1][i] = getSg(i , n - 1);
    }
    for(int s = 2 ; s <= k ; s++) getOpt((n - 1) >> 1 , 0 , n - 1 , s);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> m >> n >> k;
    for(int i = 0 ; i < n ; i++){
        int d;
        cin >> d;
        a.pb(d);
    }
    for(int i = 0 ; i < m ; i++){
        for(int j = 0 ; j < n ; j++){
            char d;
            cin >> d;
            ans[i][j] = (d == '1');
        }
    }
    init() , initTr() , f();
    for(int i = 1 ; i <= k ; i++) cout << dp[i][0] << endl;
}

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