oj.uz

Submission #260243

# Submission time Handle Problem Language Result Execution time Memory
260243 2020-08-09T21:39:20 Z kimbj0709 Popeala (CEOI16_popeala) C++14
26 / 100
 1266 ms 262144 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] << " ";
                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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 128760 KB Output is correct
2 Correct 67 ms 128760 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 128892 KB Output is correct
2 Correct 85 ms 128892 KB Output is correct
3 Correct 85 ms 129016 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 129604 KB Output is correct
2 Correct 807 ms 130168 KB Output is correct
3 Correct 1266 ms 130680 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 128760 KB Output is correct
2 Correct 67 ms 128760 KB Output is correct
3 Correct 85 ms 128892 KB Output is correct
4 Correct 85 ms 128892 KB Output is correct
5 Correct 85 ms 129016 KB Output is correct
6 Correct 444 ms 129604 KB Output is correct
7 Correct 807 ms 130168 KB Output is correct
8 Correct 1266 ms 130680 KB Output is correct
9 Runtime error 253 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -