oj.uz

Submission #609877

# Submission time Handle Problem Language Result Execution time Memory
609877 2022-07-28T02:40:05 Z juancarlovieri Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 43784 KB 
#include <bits/stdc++.h>
using namespace std;
  
#define int long long

int n, t, s;
int pts[20005];
int pre[20005];
int nxt[55][20005];
int can[55][20005];
int dp[20005][55];

struct Point {
  int x, c;
  int eval (int m) {
    return m * x + c;
  }


};

int rek(int cur, int gr) {
  if (cur >= t) {
    if (gr != 0) return 1e12;
    // if (gr == s) return 1e12;
    return 0;
  }
  if (gr == 0) return 1e12;
  int& res = dp[cur][gr];
  if (res != -1) return res;

  res = 1e12;
  res = min(1ll * res, 1ll * rek(cur + 1, gr - 1) + 1ll * pts[cur] * n);
  vector<int> block;
  for (int i = 0; i < n; ++i) {
    block.push_back(nxt[i][cur]);
  }

  sort(block.begin(), block.end());
  // cout << "LST FOR " << cur << endl;  
  // for (auto i : block) cout << i << ' ';
  //   cout << endl;
  // for (int i = cur; i < t; ++i) {
  //   block.push_back(i);
  // }
  int act = n;
  vector<int> vis(n);
  for (auto i : block) {
    if (i == t) break;
    for (int j = 0; j < n; ++j) {
      if (vis[j]) continue;
      if (nxt[j][i] <= i) {
        vis[j] = 1;
        --act;
      }
    }
    // --act;
    res = min(1ll * res, 1ll * rek(i + 1, gr - 1) + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act);
  // cout << "CUR " << cur << endl;
    // cout << i << ' ' <<   act << ' ' << 1ll * rek(i + 1, gr - 1) + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act << endl;
  }
  // cout << endl;
  res = min(1ll * res, 1ll * rek(t, gr - 1) + 1ll * (pre[t - 1] - (cur ? pre[cur - 1] : 0)) * act);
  // cout << act << endl;
  return res;
}

signed main() {
  memset(dp, -1, sizeof dp);
  cin >> n >> t >> s;
  for (int i = 0; i < t; ++i) cin >> pts[i];
    pre[0] = pts[0];
  for (int i = 1; i < t; ++i) pre[i] = pre[i - 1] + pts[i];
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < t; ++j) {
      if (s[j] == '0') can[i][j] = 0;
      else can[i][j] = 1;
    }
  }

  for (int i = 0; i < n; ++i) {
    nxt[i][t] = t;
    for (int j = t - 1; j >= 0; --j) {
      if (can[i][j] == 0) nxt[i][j] = j;
      else nxt[i][j] = nxt[i][j + 1];
    }
  }
  for (int i = 0; i <= t; ++i) {
    for (int j = 0; j <= s; ++j) {

    dp[i][j] = 1e12;
    }
  }
  dp[t][0] = 0;
  vector<vector<int>> hasil(t, vector<int>(n + 3, 1e12));

  for (int gr = 1; gr <= s; ++gr) {
    for (int cur = 0; cur < t; ++cur) {
      int& res = dp[cur][gr];

      res = 1e12;
      res = min(1ll * res, 1ll * dp[cur + 1][gr - 1] + 1ll * pts[cur] * n);
      vector<int> block;
      for (int i = 0; i < n; ++i) {
        block.push_back(nxt[i][cur]);
      }

      sort(block.begin(), block.end());
      // cout << "LST FOR " << cur << endl;  
      // for (auto i : block) cout << i << ' ';
      //   cout << endl;
      // for (int i = cur; i < t; ++i) {
      //   block.push_back(i);
      // }
      int act = n;
      vector<int> vis(n);
      int last = -1;
      for (auto i : block) {
        if (i == t) break;
        if (last == -1) last = i;
        else {
          // puts("TES");
          res = min(res , hasil[last][act] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act);
          // cout << gr << ' ' << act << ' ' << cur << ' ' << i << ' ' << hasil[act][cur] << endl;
          // cout << hasil[act][act] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act << endl;
        }
        last = i;
        // for (int j = 0; j < n; ++j) {
        //   if (vis[j]) continue;
        //   if (nxt[j][i] <= i) {
        //     vis[j] = 1;
        //     --act;
        //   }
        // }
        --act;
        res = min(1ll * res, 1ll * dp[i + 1][gr - 1] + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act);
      // cout << "CUR " << cur << endl;
        // cout << i << ' ' <<   act << ' ' << 1ll * rek(i + 1, gr - 1) + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act << endl;
      }
      if (last != -1) {
        res = min(res, hasil[last][act] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act);
        //   cout << hasil[act][cur] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act << endl;
      }
      // cout << endl;
      res = min(1ll * res, 1ll * dp[t][gr - 1] + 1ll * (pre[t - 1] - (cur ? pre[cur - 1] : 0)) * act);
      // cout << act << endl;
      // return res;
    }
    hasil = vector<vector<int>>(t, vector<int>(n + 3, 1e12));
    for (int i = t - 1; i >= 0; --i) {
      for (int j = 0; j <= n; ++j) {
        if (i < t - 1) hasil[i][j] = hasil[i + 1][j];
        hasil[i][j] = min(hasil[i][j], dp[i + 1][gr] + j * pre[i]);
      }
    }
  }
  // cout << rek(2, 1) << endl;
  // cout << rek(0, 2) << endl;
  // for (int i = 1; i <= s; ++i) {
  //   cout << rek(0, i) << endl;
  // }
  for (int i = 1; i <= s; ++i) {
    cout << dp[0][i] << endl;
  }
  // cout << rek(0, 0) << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 9172 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10204 KB Output is correct
2 Correct 48 ms 10168 KB Output is correct
3 Correct 51 ms 10260 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 13000 KB Output is correct
2 Correct 281 ms 14600 KB Output is correct
3 Correct 431 ms 16328 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 9172 KB Output is correct
3 Correct 58 ms 10204 KB Output is correct
4 Correct 48 ms 10168 KB Output is correct
5 Correct 51 ms 10260 KB Output is correct
6 Correct 191 ms 13000 KB Output is correct
7 Correct 281 ms 14600 KB Output is correct
8 Correct 431 ms 16328 KB Output is correct
9 Correct 517 ms 20684 KB Output is correct
10 Correct 831 ms 24172 KB Output is correct
11 Correct 1664 ms 42484 KB Output is correct
12 Correct 1511 ms 43784 KB Output is correct
13 Execution timed out 2069 ms 43752 KB Time limit exceeded
14 Halted 0 ms 0 KB -