Submission #127292

#	Time	Username	Problem	Language	Result	Execution time	Memory
127292		DodgeBallMan	Popeala (CEOI16_popeala)	C++14	0 / 100	58 ms	44064 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int K = 55;
int dp[N][K], last[N][K], t, n, s, qs[N];
int main()
{
    memset( dp, 127, sizeof dp );
    scanf("%d %d %d",&n,&t,&s);
    for( int i = 1, va ; i <= t ; i++ ) {
        scanf("%d",&va);
        qs[i] = qs[i-1] + va;
    }
    for( int i = 1 ; 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 = 1 ; i <= t ; i++ ) {
        last[i][n+1] = i;
        sort( last[i] + 1, last[i] + 2 + n );
    }
    // for( int j = 1 ; j <= t ; j++ ) {
    //     for( int i = 1 ; i <= n ; i++ ) {
    //         printf("%d ",last[j][i]);
    //     }
    //     printf("\n");
    // }
    dp[0][0] = 0;
    for( int i = 1 ; i <= t ; i++ ) dp[i][1] = 0;
    for( int i = 1 ; i <= t ; i++ ) {
        for( int j = 1 ; j <= n ; j++ ) {
            if( last[i][j] == 0 ) dp[i][1] += qs[i];
        }
    }
    for( int i = 1 ; i <= t ; i++ ) {
        for( int j = 2 ; j <= min( s, i ) ; j++ ) {
            int cnt = 0;
            for( int k = n ; k >= 1 ; k-- ) if( last[i][k] == i ) cnt++;  
            dp[i][j] = min( dp[i][j], dp[i-1][j-1] + ( qs[i] - qs[i-1] ) * ( n - cnt ) );
            for( int k = n - cnt ; k >= 1 ; k-- ) {
                if( last[i][k] != last[i][k-1] ) dp[i][j] = min( dp[i][j], dp[last[i][k]-1][j-1] + ( qs[i] - qs[last[i][k]-1] ) * (  k - 1 ) );
            }
        }
    }
    // printf("\n");
    // for( int i = 1 ; i <= t ; i++ ) {
    //     for( int j = 1 ; j <= s ; j++ ) {
    //         printf("%d ",dp[i][j]);
    //     }
    //     printf("\n");
    // }
    // printf("\n");
    for( int i = 1 ; i <= s ; i++ ) printf("%d\n", dp[t][i] );
    return 0;
}

Compilation message (stderr)

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);
         ~~~~~^~~~~~~~~~
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: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74