oj.uz

Submission #963793

# Submission time Handle Problem Language Result Execution time Memory
963793 2024-04-15T16:56:42 Z LucaIlie Popeala (CEOI16_popeala) C++17
100 / 100
 1308 ms 24144 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 50;
const int MAX_T = 50000;
const int MAX_S = 50;
const long long INF = 1e15;

bool solved[MAX_N][MAX_T + 1];
int points[MAX_T + 1], last0[MAX_N][MAX_T + 1], add[MAX_T + 1];
long long dp[MAX_T + 1][MAX_S + 1], minFunc[MAX_T + 1][MAX_N + 1];

int main() {
    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 j = 0; j < n; j++ ) {
        for ( int i = 1; i <= t; i++ ) {
            char ch;
            cin >> ch;
            solved[j][i] = ch - '0';
            last0[j][i] = (!solved[j][i] ? i : last0[j][i - 1]);
        }
    }

    for ( int i = 0; i <= t; i++ ) {
        for ( int k = 0; k <= s; k++ )
            dp[i][k] = INF;
    }
    dp[0][0] = 0;
    for ( int k = 1; k <= s; k++ ) {
        for ( int i = 0; i <= t; i++ ) {
            for ( int c = 0; c <= n; c++ )
                minFunc[i][c] = min( (i == 0 ? INF : minFunc[i - 1][c]), dp[i][k - 1] - c * points[i] );
        }
        for ( int i = 1; i <= t; i++ ) {
            vector<int> pos;
            pos.push_back( i );
            for ( int j = 0; j < n; j++ ) {
                if ( last0[j][i] != 0 ) {
                    pos.push_back( last0[j][i] );
                    add[last0[j][i]]++;
                }
            }
            sort( pos.begin(), pos.end() );
            pos.resize( unique( pos.begin(), pos.end() ) - pos.begin() );
            reverse( pos.begin(), pos.end() );

            int c = n;
            for ( int j: pos ) {
                c -= add[j];
                add[j] = 0;
                dp[i][k] = min( dp[i][k], minFunc[j - 1][c] + (long long)c * points[i] );
            }
        }
    }

    for ( int k = 1; k <= s; k++ )
        cout << dp[t][k] << "\n";

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1372 KB Output is correct
2 Correct 26 ms 1372 KB Output is correct
3 Correct 29 ms 1376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3168 KB Output is correct
2 Correct 218 ms 4192 KB Output is correct
3 Correct 253 ms 5280 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 36 ms 1372 KB Output is correct
4 Correct 26 ms 1372 KB Output is correct
5 Correct 29 ms 1376 KB Output is correct
6 Correct 152 ms 3168 KB Output is correct
7 Correct 218 ms 4192 KB Output is correct
8 Correct 253 ms 5280 KB Output is correct
9 Correct 288 ms 9696 KB Output is correct
10 Correct 492 ms 11820 KB Output is correct
11 Correct 940 ms 23980 KB Output is correct
12 Correct 1084 ms 24144 KB Output is correct
13 Correct 1308 ms 24068 KB Output is correct
14 Correct 1242 ms 24076 KB Output is correct
15 Correct 1280 ms 24072 KB Output is correct