Submission #941804

#	Time	Username	Problem	Language	Result	Execution time	Memory
941804		vjudge1	Copy and Paste 3 (JOI22_copypaste3)	C++17	5 / 100	14 ms	604 KiB

copypaste3

#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 (stderr)

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
• Subtask 2: 5 / 5
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38