Submission #127824

#	Time	Username	Problem	Language	Result	Execution time	Memory
127824		DodgeBallMan	Popeala (CEOI16_popeala)	C++14	17 / 100	102 ms	44280 KiB

popeala

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 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 );
                dp[i][j] = min( dp[i][j], mi[k] + va[j] * k );
            }
        }
        printf("%d\n",dp[i][t]);
    }
    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[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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74