oj.uz

Submission #941804

# Submission time Handle Problem Language Result Execution time Memory
941804 2024-03-09T13:11:36 Z vjudge1 Copy and Paste 3 (JOI22_copypaste3) C++17
5 / 100
 14 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

/*
x = lungimea
y = aparitii

cost_nor = A * len * ap
cost_cut = A * len + B + C * ap

A * len * ap - A * len - B - C * ap > 0

A*x*y - A*x - C*y - B > 0
y*(A*x-C) > A * x + B
y > (A * x + B) / (A * x - C)x
*/

const int INF = 1e9, BASE = 23, MOD = 1e9 + 7, N = 205;
int p[N];
void precalc() {
  p[0] = 1;
  for (int i = 1; i < N; ++i) p[i] = p[i - 1] * BASE % MOD;
}

int n, A, B, C;
string s;

int dp[N][N];
int calc(int l, int r) {
  if (dp[l][r] != -1) return dp[l][r];
  if (r < l) {
    dp[l][r] = 0;
    return dp[l][r];
  }
  
  for (int len = 1; len <= r - l + 1; ++len) {
    unordered_map<int, vector<int>> ap{};
    
    int hash = 0;
    for (int i = 0; i < len; ++i) hash = (hash + p[i] * s[l + i] % MOD) % MOD;
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  precalc();
  
  cin >> n >> s >> A >> B >> C;
  
  bool all_a = true;
  for (int i = 0; i < n; ++i) all_a &= (s[i] == 'a');
  if (all_a) {
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
      dp[i] = dp[i - 1] + A;
      for (int len = 1; len < i; ++len) {
        dp[i] = min(dp[i], dp[len] + B + C * (i / len) + A * (i % len));
      }
    }
    cout << dp[n];
    return 0;
  }
  
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) dp[i][j] = -1;
  }
}

Compilation message

copypaste3.cpp: In function 'll calc(ll, ll)':
copypaste3.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
   51 | }
      | ^

Subtask #1
0 / 1.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 8 ms 348 KB Output is correct
4 Correct 9 ms 604 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 12 ms 344 KB Output is correct
7 Correct 14 ms 348 KB Output is correct
8 Correct 14 ms 500 KB Output is correct
9 Correct 14 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 32.0

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

Subtask #6
0 / 38.0

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