oj.uz

Submission #260241

# Submission time Handle Problem Language Result Execution time Memory
260241 2020-08-09T21:38:45 Z kimbj0709 Popeala (CEOI16_popeala) C++14
0 / 100
 417 ms 129912 KB 
#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] << " ";
                if(n-pre[i+1][j]==0){
                  continue;
                }
                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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 128760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 128888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 417 ms 129912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 128760 KB Output isn't correct
2 Halted 0 ms 0 KB -