oj.uz

Submission #127830

# Submission time Handle Problem Language Result Execution time Memory
127830 2019-07-10T06:55:59 Z DodgeBallMan Popeala (CEOI16_popeala) C++14
17 / 100
 77 ms 5496 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e4 + 10;
const int K = 55;
int dp[K][N], last[N][K], t, n, s, va[N], mi[K];
int main()
{
    memset( dp, 127, sizeof dp );
    scanf("%d %d %d",&n,&t,&s);
    for( int i = 1 ; i <= t ; i++ ) {
        scanf("%d",&va[i]);
        va[i] += va[i-1];
    }
    for( int i = 0 ; i < n ; i++ ) {
        char score[N];
        scanf("%s",score);
        for( int j = 1 ; j <= t ; j++ ) {
            if( score[j-1] == '1' ) last[j][i] = last[j-1][i];
            else last[j][i] = j;
        }
    }
    for( int i = 0 ; i <= t ; i++ ) {
        last[i][n] = i;
        sort( last[i], last[i] + 1 + n );
    }
    dp[0][0] = 0;
    for( int i = 1 ; i <= s ; i++ ) {
        memset( mi, 127, sizeof mi );
        for( int j = 1 ; j <= t ; j++ ) {
            for( int k = 0 ; k <= n ; k++ ) {
                for( int l = last[j-1][k] ; l < last[j][k] ; l++ ) mi[k] = min( mi[k], dp[i-1][l] - va[l] * k );
                if( last[j][k] > 0 ) dp[i][j] = min( dp[i][j], mi[k] + va[j] * k );
            }
        }
        printf("%d\n",dp[i][t]);
    }
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&t,&s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
popeala.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&va[i]);
         ~~~~~^~~~~~~~~~~~~
popeala.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",score);
         ~~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4728 KB Output is correct
2 Correct 6 ms 4600 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4728 KB Output is correct
2 Correct 14 ms 4728 KB Output is correct
3 Correct 15 ms 4728 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5112 KB Output is correct
2 Correct 69 ms 5368 KB Output is correct
3 Incorrect 77 ms 5496 KB Output isn't correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4728 KB Output is correct
2 Correct 6 ms 4600 KB Output is correct
3 Correct 15 ms 4728 KB Output is correct
4 Correct 14 ms 4728 KB Output is correct
5 Correct 15 ms 4728 KB Output is correct
6 Correct 51 ms 5112 KB Output is correct
7 Correct 69 ms 5368 KB Output is correct
8 Incorrect 77 ms 5496 KB Output isn't correct