oj.uz

Submission #52861

# Submission time Handle Problem Language Result Execution time Memory
52861 2018-06-27T05:22:42 Z 강태규(#1381) Popeala (CEOI16_popeala) C++11
26 / 100
 457 ms 9960 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int inf = 2e9 + 7;
int n, t, s;
int pt[20001];
char res[50][20002];
int ep[20001][51];
int pr[20001];
int dp[20001];
int mn[20001][51];

int main() {
    scanf("%d%d%d", &n, &t, &s);
    for (int i = 1; i <= t; ++i) {
        scanf("%d", pt + i);
        pt[i] += pt[i - 1];
    }
    for (int i = 0; i < n; ++i) {
        scanf("%s", res[i] + 1);
        for (int j = 1; j <= t; ++j) {
            res[i][j] -= '0';
        }
    }
    for (int i = 0; i < n; ++i) {
        ep[t][i] = t + res[i][t];
    }
    for (int i = t; --i; ) {
        for (int j = 0; j < n; ++j) {
            ep[i][j] = res[j][i] ? ep[i + 1][j] : i;
        }
    }
    for (int i = 1; i <= t; ++i) {
        sort(ep[i], ep[i] + n);
    }
    for (int i = 1; i <= t; ++i) dp[i] = inf;
    for (int it = 0; it < s; ++it) {
        for (int i = 0; i <= t; ++i) {
            pr[i] = dp[i];
            dp[i] = inf;
            for (int j = 0; j <= n; ++j) {
                mn[i][j] = inf;
            }
        }
        for (int i = 1; i <= t; ++i) {
            int p = i;
            for (int j = n + 1; j--; ) {
                if (pr[i - 1] != inf)
                    mn[p][j] = min(mn[p][j], pr[i - 1] - j * pt[i - 1]);
                p = ep[i][n - j];
            }
        }
        for (int i = 1; i <= t; ++i) {
            for (int j = 0; j <= n; ++j) {
                mn[i][j] = min(mn[i][j], mn[i - 1][j]);
            }
        }
        for (int i = 1; i <= t; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (mn[i][j] != inf)
                    dp[i] = min(dp[i], mn[i][j] + j * pt[i]);
            }
        }
        printf("%d\n", dp[t]);
    }
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:31: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:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", pt + i);
         ~~~~~^~~~~~~~~~~~~~
popeala.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", res[i] + 1);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 612 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 944 KB Output is correct
2 Correct 13 ms 972 KB Output is correct
3 Correct 13 ms 1048 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1708 KB Output is correct
2 Correct 79 ms 2304 KB Output is correct
3 Correct 94 ms 2772 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 15 ms 944 KB Output is correct
4 Correct 13 ms 972 KB Output is correct
5 Correct 13 ms 1048 KB Output is correct
6 Correct 48 ms 1708 KB Output is correct
7 Correct 79 ms 2304 KB Output is correct
8 Correct 94 ms 2772 KB Output is correct
9 Correct 166 ms 3896 KB Output is correct
10 Correct 184 ms 4924 KB Output is correct
11 Incorrect 457 ms 9960 KB Output isn't correct
12 Halted 0 ms 0 KB -