oj.uz

답안 #51798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51798 2018-06-21T08:23:59 Z evpipis 조교 (CEOI16_popeala) C++14
17 / 100
 2000 ms 2176 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int len = 2e4+5;
const ll inf = 1e15;
int po[len], can[55][len], n, s, t;
ll dp[len][55];

int val(int l, int r){
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (can[i][r]-can[i][l-1] == r-l+1)
            ans += po[r]-po[l-1];

    return ans;
}

ll solve(int i, int rem){
    if (i == t+1 && rem == 0) return 0;
    if (i == t+1 && rem != 0) return inf;
    if (rem == 1) return val(i, t);
    if (dp[i][rem] != -1) return dp[i][rem];

    ll ans = inf;
    for (int j = i; j <= t; j++)
        ans = min(ans, val(i, j) + solve(j+1, rem-1));

    //printf("i = %d, rem = %d, ans = %lld\n", i, rem, ans);
    return dp[i][rem] = ans;
}

int main(){
    scanf("%d %d %d", &n, &t, &s);
    for (int i = 1; i <= t; i++)
        scanf("%d", &po[i]);
    for (int i = 1; i <= n; i++){
        scanf(" ");
        for (int j = 1; j <= t; j++){
            char temp;
            scanf("%c", &temp);

            if (temp == '1')
                can[i][j] = 1;
        }
    }

    /*for (int i = 1; i <= n; i++){
        for (int j = 1; j <= t; j++)
            printf("%d", can[i][j]);
        printf("\n");
    }*/

    for (int j = 1; j <= t; j++)
        po[j] += po[j-1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= t; j++)
            can[i][j] += can[i][j-1];

    for (int i = 1; i <= t; i++)
        for (int j = 0; j <= s; j++)
            dp[i][j] = -1;

    //for (int i = 1; i <= t; i++)
      //  for (int j = i; j <= t; j++)
        //    printf("(%d, %d) = %d\n", i, j, val(i, j));

    for (int j = 1; j <= s; j++)
        printf("%lld\n", solve(1, j));
    return 0;
}
/*
2 5 5
2 1 3 5 6
10010
11011
*/

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:34: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:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &po[i]);
         ~~~~~^~~~~~~~~~~~~~
popeala.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" ");
         ~~~~~^~~~~
popeala.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &temp);
             ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 612 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 948 KB Output is correct
2 Correct 553 ms 1036 KB Output is correct
3 Correct 499 ms 1164 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2054 ms 2176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 612 KB Output is correct
3 Correct 553 ms 948 KB Output is correct
4 Correct 553 ms 1036 KB Output is correct
5 Correct 499 ms 1164 KB Output is correct
6 Execution timed out 2054 ms 2176 KB Time limit exceeded
7 Halted 0 ms 0 KB -