oj.uz

Submission #908681

# Submission time Handle Problem Language Result Execution time Memory
908681 2024-01-16T16:28:51 Z vjudge1 Popeala (CEOI16_popeala) C++17
8 / 100
 187 ms 7768 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's the baby, that's not my baby

typedef long long ll;

const int TMAX = 2e4;
const int NMAX = 50;
const int SMAX = 50;

int dp[TMAX + 1][SMAX + 1];
int a[TMAX + 1];
bool b[NMAX + 1][TMAX + 1];
int sum[NMAX + 1][TMAX + 1];
int price[TMAX + 1];
int last[NMAX + 1];

signed main() {
  int n, t, s;
  std::cin >> n >> t >> s;

  for (int i = 1; i <= t; i++) {
    std::cin >> a[i];
    price[i] = price[i - 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= t; j++) {
      char ch;
      std::cin >> ch;
      b[i][j] = ch - '0';
      sum[i][j] = sum[i][j - 1] + b[i][j];
    }
  }

  for (int i = 0; i <= TMAX; i++) {
    for (int j = 0; j <= SMAX; j++) {
      dp[i][j] = 2e9 + 5;
    }
  }

  dp[0][0] = 0;

  for (int i = 1; i <= t; i++) {
    std::vector<int> where;
    for (int p = 1; p <= n; p++) {
      if (b[p][i] == 0) {
        last[p] = i;
      }
      where.push_back(last[p]);
//      std::cout << last[p] << ' ';
    }
//    std::cout << '\n';
    std::sort(where.begin(), where.end());
    std::reverse(where.begin(), where.end());
    int cnt0 = std::count(where.begin(), where.end(), 0);
    dp[i][1] = (ll) cnt0 * price[i];
    where.push_back(0);
    for (int j = 2; j <= s & j <= i; j++) {
      if (where[0] != i) {
        dp[i][j] = dp[where[0]][j - 1] + (ll) n * (price[i] - price[where[0]]);
      }
      for (int zero = 1; zero <= n; zero++) {
        for (int k = where[zero - 1]; k > where[zero]; k--) {
          dp[i][j] = std::min((ll) dp[i][j], (ll) dp[k - 1][j - 1] + (ll) (n - zero) * (price[i] - price[k - 1]));
        }
      }
    }
//    std::cout << '\n';
  }

  for (int i = t; i <= t; i++) {
    for (int j = 1; j <= s; j++) {
      std::cout << dp[i][j] << ' ';
    }
    std::cout << '\n';
  }

  return 0;
}

Compilation message

popeala.cpp:5:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    5 | #warning That's the baby, that's not my baby
      |  ^~~~~~~
popeala.cpp: In function 'int main()':
popeala.cpp:60:23: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   60 |     for (int j = 2; j <= s & j <= i; j++) {
      |                     ~~^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7256 KB Output is correct
2 Incorrect 14 ms 7768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 17 ms 7256 KB Output is correct
4 Incorrect 14 ms 7768 KB Output isn't correct
5 Halted 0 ms 0 KB -