제출 #536935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536935		FatihSolak	조교 (CEOI16_popeala)	C++17	0 / 100	120 ms	262144 KiB

popeala

#include <bits/stdc++.h>
#define T 20005
#define N 55
using namespace std;
long long mini[T][N][N];
int st[T][N];
long long dp[T][N];
int points[T];
int nxt[N][T];
void solve(){
    int n,t,s;
    cin >> n >> t >> s;
    for(int i=1;i<=t;i++){
        cin >> points[i];
        points[i] += points[i-1];
    }
    for(int i=1;i<=n;i++){
        string ss;
        cin >> ss;
        nxt[i][t+1] = t+1;
        for(int j = t;j>=0;j--){
            if(j && ss[j-1] == '0')
                nxt[i][j] = j;
            else nxt[i][j] = nxt[i][j+1];
        }
    }
    for(int i=0;i<=t;i++){
        vector<int> v;
        for(int j = 1;j<=n;j++){
            v.push_back(nxt[j][i]);
        }
        sort(v.begin(),v.end());
        int cnt = n;
        st[i][cnt] = i;
        for(auto u:v){
            cnt--;
            st[i][cnt] = u;
        }
    }
    for(int i = 0;i<T;i++){
        for(int j = 0;j<N;j++){
            for(int c = 0;c<N;c++){
                mini[i][j][c] = 2e18;
            }
            dp[i][j] = 2e18;
        }
    }
    dp[0][0] = 0;
    for(int x = 0;x<s;x++){
        for(int i = 0;i<t;i++){
            for(int j = 0;j<=n;j++){
                //cout << st[i + 1][j] << " ";
                mini[st[i + 1][j]][x+1][j] = min(mini[st[i + 1][j]][x+1][j], dp[i][x] - j * points[i]);
            }
            //cout << endl;
        }
        //cout << endl;
        for(int i = 1;i<=t;i++){
            for(int j = 0;j<=n;j++){
                mini[i][x+1][j] = min(mini[i][x+1][j],mini[i-1][x+1][j]);
                dp[i][x+1] = min(dp[i][x+1], mini[i][x+1][j] + j * points[i]);
            }
            //cout << x+1 << " " << i << " " << dp[i][x+1] << endl;
        }
        //cout << endl;
    }
    for(int i=1;i<=s;i++){
        cout << dp[t][i] << endl;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

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