oj.uz

답안 #260256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260256 2020-08-09T22:02:11 Z kimbj0709 조교 (CEOI16_popeala) C++14
8 / 100
 2000 ms 129656 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++){
                vector<int> tried(50,0);
                if(tried[pre[i+1][j]]==1){
                  continue;
                }
                temp[j] = min(temp[j],(points[j]-points[i])*(n-pre[i+1][j])+dp[i]);
                tried[pre[i+1][j]] = 1;
            }
            //cout << endl;
        }
        dp = temp;
        cout << dp[t] << "\n";
    }

}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 128760 KB Output is correct
2 Correct 73 ms 128864 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 588 ms 129016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2101 ms 129656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 128760 KB Output is correct
2 Correct 73 ms 128864 KB Output is correct
3 Incorrect 588 ms 129016 KB Output isn't correct
4 Halted 0 ms 0 KB -