Submission #260243

#	Time	Username	Problem	Language	Result	Execution time	Memory
260243		kimbj0709	Popeala (CEOI16_popeala)	C++14	26 / 100	1266 ms	262144 KiB

popeala

#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,t,s;
    cin >> n >> t >> s;
    vector<int> points;
    int input1;
    points.push_back(0);
    for(int i=0;i<t;i++){
        cin >> input1;
        points.push_back(input1);
        points[i+1] += points[i];
    }
    char input;
    int prefix[n][t+1];
    for(int i=0;i<n;i++){
        for(int j=1;j<=t;j++){
            cin >> input;
            if(input=='1'){
                prefix[i][j] = 0;
            }
            else{
                prefix[i][j] = 1;
            }
        }
        for(int j=1;j<=t;j++){
            prefix[i][j] += prefix[i][j-1];
        }
    }
    int pre[4050][4050];
    memset(pre,0,sizeof(pre));
    for(int tt=0;tt<n;tt++){
        for(int i=1;i<=t;i++){
            for(int j=i;j<=t;j++){
                if(prefix[tt][j]-prefix[tt][i-1]>0){
                    pre[i][j]++;
                }
            }
        }
    }
    vector<int> dp(t+1,INT_MAX);
    dp[0] = 0;
    /*for(int i=1;i<=t;i++){
        for(int j=1;j<=t;j++){
            cout << pre[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "\n-------------\n";*/
    for(int tt=0;tt<s;tt++){
        vector<int> temp(t+1,INT_MAX);
        for(int i=0;i<=t;i++){
            for(int j=i+1;j<=t;j++){
                //cout << (points[j]-points[i])*(n-pre[i+1][j])+dp[i] << " ";
                temp[j] = min(temp[j],(points[j]-points[i])*(n-pre[i+1][j])+dp[i]);
            }
            //cout << endl;
        }
        dp = temp;
        cout << dp[t] << "\n";
    }

}

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