oj.uz

Submission #741433

# Submission time Handle Problem Language Result Execution time Memory
741433 2023-05-14T05:14:38 Z abcvuitunggio Popeala (CEOI16_popeala) C++17
100 / 100
 275 ms 18764 KB 
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int INF=1e18;
int dp[20001][51],n,T,s,t[20001],last[20001][51],a[51];
string score[51];
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> T >> s;
    for (int i=1;i<=T;i++){
        cin >> t[i];
        t[i]+=t[i-1];
    }
    for (int i=0;i<n;i++)
        cin >> score[i];
    for (int i=1;i<=T;i++){
        last[i][n]=i;
        for (int j=0;j<n;j++)
            last[i][j]=(score[j][i-1]=='0'?i:last[i-1][j]);
    }
    for (int i=1;i<=T;i++)
        sort(last[i],last[i]+n+1);
    for (int i=1;i<=T;i++)
        dp[i][0]=INF;
    for (int i=1;i<=s;i++){
        for (int j=0;j<=n;j++)
            a[j]=INF;
        dp[0][i]=INF;
        for (int j=1;j<=T;j++){
            dp[j][i]=INF;
            for (int k=0;k<=n;k++){
                for (int l=last[j-1][k]+1;l<=last[j][k];l++)
                    a[k]=min(a[k],dp[l-1][i-1]-t[l-1]*k);
                dp[j][i]=min(dp[j][i],a[k]+t[j]*k);
            }
        }
        cout << dp[T][i] << '\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 6 ms 720 KB Output is correct
3 Correct 8 ms 724 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2328 KB Output is correct
2 Correct 51 ms 3028 KB Output is correct
3 Correct 53 ms 4012 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 6 ms 720 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 40 ms 2328 KB Output is correct
7 Correct 51 ms 3028 KB Output is correct
8 Correct 53 ms 4012 KB Output is correct
9 Correct 73 ms 6328 KB Output is correct
10 Correct 117 ms 8148 KB Output is correct
11 Correct 196 ms 18616 KB Output is correct
12 Correct 189 ms 18764 KB Output is correct
13 Correct 265 ms 18716 KB Output is correct
14 Correct 275 ms 18760 KB Output is correct
15 Correct 264 ms 18760 KB Output is correct