Submission #776291

#	Time	Username	Problem	Language	Result	Execution time	Memory
776291		marvinthang	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	653 ms	49860 KiB

copypaste3

/*************************************
*    author: marvinthang             *
*    created: 07.07.2023 21:33:29    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

namespace HASHING {

    const int NMOD = 2;
    const int MOD[] = {(int) 1e9 + 7, (int) 1e9 + 2277, (int) 1e9 + 5277, 
                            (int) 1e9 + 8277, (int) 1e9 + 9277};
    const int BASE = 31; // 311
    const int capital = 'a';
    const int MAX_SIZE = 2505 + 6;

    int pw[NMOD][MAX_SIZE];

    void prepareHashing(void) {
        for (int j = 0; j < NMOD; ++j) {
            pw[j][0] = 1;
            for (int i = 1; i < MAX_SIZE; ++i)
                pw[j][i] = 1LL * pw[j][i - 1] * BASE % MOD[j];
        }
    }

    struct Value {

            int val[NMOD];
        
            Value(int x = 0) { for (int i = 0; i < NMOD; ++i) val[i] = x; }

            Value(char c, int pos) {
                for (int i = 0; i < NMOD; ++i) 
                    val[i] = 1LL * c * pw[i][pos] % MOD[i];
            }

            Value shift(int step) const {
                Value res;
                for (int i = 0; i < NMOD; ++i)
                    res.val[i] = 1LL * val[i] * pw[i][step] % MOD[i];
                return res;
            }

            Value operator + (const Value &other) const {
                Value res;
                for (int i = 0; i < NMOD; ++i) {
                    res.val[i] = val[i] + other.val[i];
                    if (res.val[i] >= MOD[i]) res.val[i] -= MOD[i];
                }
                return res;
            }

            Value operator - (const Value &other) const {
                Value res;
                for (int i = 0; i < NMOD; ++i) {
                    res.val[i] = val[i] - other.val[i];
                    if (res.val[i] < 0) res.val[i] += MOD[i];
                }
                return res;
            }

            bool operator < (const Value& other) const { 
                for (int i = 0; i < NMOD; ++i)
                    if (val[i] != other.val[i]) return val[i] < other.val[i];
                return false;
            }

            bool operator == (const Value& other) const {
                for (int i = 0; i < NMOD; ++i)
                    if (val[i] != other.val[i]) return false;
                return true;
            }
        
            bool operator != (const Value& other) const {
                for (int i = 0; i < NMOD; ++i) 
                    if (val[i] != other.val[i]) return true;
                return false;
            }
    
    };

    struct Hash {

        string S;
        int len;
        Value *code, *rev_code;

        void Init_Hash(bool palin = false) {
            len = S.size();
            S = ' ' + S;
            code = new Value[len + 1];
            code[0] = 0;
            if (palin) {
                rev_code = new Value[len + 1];
                rev_code[0] = 0;
            }
            for (int i = 1; i <= len; ++i) {
                code[i] = code[i - 1] + Value(S[i] - capital + 1, i);
                if (palin) rev_code[i] = rev_code[i - 1] + Value(S[len - i + 1] - capital + 1, i);
            }
        }

        Hash() {}

        Hash(string s, bool palin = false) {
            S = s;
            Init_Hash(palin);
        }

        int getHash(int l, int r, int mod) const {
            assert(l <= r && l > 0 && r <= len);
            int res = code[r].val[mod] - code[l - 1].val[mod];
            if (res < 0) res += MOD[mod];
            res = 1LL * res * pw[mod][MAX_SIZE - l] % MOD[mod];
            return res;
        }

        Value getHash(int l, int r) const {
            assert(l <= r && l > 0 && r <= len);
            return (code[r] - code[l - 1]).shift(MAX_SIZE - l);
        }

        Value getRevHash(int l, int r) {
            assert(l <= r && l > 0 && r <= len);
            return (rev_code[r] - rev_code[l - 1]).shift(MAX_SIZE - l);
        }

        bool isPalin(int l, int r) {
            return getHash(l, r) == getRevHash(len - r + 1, len - l + 1);
        }

        Value getHash(void) const {
            return getHash(1, len);
        }

        bool operator == (Hash& other) const {
            return code[len] == other.code[other.len];
        }

        bool operator < (Hash& other) const{    
            return code[len] < other.code[other.len];
        }

        bool operator > (Hash& other) const{
            return !(code[len] < other.code[other.len] || code[len] == other.code[other.len]);
        }

        bool cmpSubstr(int l, int r, int u, int v) {
            assert(l <= r && u <= v); assert(l > 0 && u > 0); assert(r <= len && v <= len);
            int len = min(r - l + 1, v - u + 1);
            int max_same = 0;
            int Min = 1, Max = len;
            while (Min <= Max) {
                int mid = Min + Max >> 1;
                Value F1 = getHash(l, l + mid - 1);
                Value F2 = getHash(u, u + mid - 1);
                if (F1 == F2) {
                    max_same = mid;
                    Min = mid + 1;
                } else Max = mid - 1;
            }
            if (max_same == len) return r - l < v - u;
            return S[l + max_same] < S[u + max_same];
        }

    };

    bool cmpStr(Hash a, Hash b) {
        int len = min(a.len, b.len);
        int max_same = 0;
        int l = 1, r = len - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            Value F1 = a.getHash(1, mid);
            Value F2 = b.getHash(1, mid);
            if (F1 == F2) {
                max_same = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        if (max_same == len) return a.len < b.len;
        return a.S[max_same + 1] < b.S[max_same + 1];
    }

}

using namespace HASHING;

// end of template

const int MAX = 2505;

int N, A, B, C;
string S;
Hash h;

void init(void) {
	prepareHashing();
	cin >> N >> S >> A >> B >> C;
	h = Hash(S);
}

long long dp[MAX][MAX];

void process(void) {
	memset(dp, 0x3f, sizeof(dp));
	FORE(i, 1, N) dp[i][i] = A;
	FORE(len, 1, N) {
		map <Value, vector <int>> v;
		FORE(l, 1, N - len + 1) {
			int r = l + len - 1;
			minimize(dp[l][r], min(dp[l][r - 1], dp[l + 1][r]) + A);
			v[h.getHash(l, r)].push_back(l);
		}
		vector <int> nxt(N + 1);
		for (auto [love, v]: v) {
			int r = 0;
			for (int l: v) {
				while (r < v.size() && v[r] < l + len) ++r;
				nxt[l] = r < v.size() ? v[r] : 0;
			}
			for (int l: v) {
				int pos = l;
				int cnt = 0;
				while (pos) {
					++cnt;
					r = pos + len - 1; pos = nxt[pos];
					minimize(dp[l][r], dp[l][l + len - 1] + B + 1LL * C * cnt + 1LL * A * (r - l + 1 - cnt * len));
				}
			}
		}
	}
	cout << dp[1][N] << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("copypaste3");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message (stderr)

copypaste3.cpp: In member function 'bool HASHING::Hash::cmpSubstr(int, int, int, int)':
copypaste3.cpp:192:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  192 |                 int mid = Min + Max >> 1;
      |                           ~~~~^~~~~
copypaste3.cpp: In function 'bool HASHING::cmpStr(HASHING::Hash, HASHING::Hash)':
copypaste3.cpp:211:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  211 |             int mid = l + r >> 1;
      |                       ~~^~~
copypaste3.cpp: In function 'void process()':
copypaste3.cpp:257:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  257 |     while (r < v.size() && v[r] < l + len) ++r;
      |            ~~^~~~~~~~~~
copypaste3.cpp:258:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |     nxt[l] = r < v.size() ? v[r] : 0;
      |              ~~^~~~~~~~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:276:2: note: in expansion of macro 'file'
  276 |  file("copypaste3");
      |  ^~~~
copypaste3.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:276:2: note: in expansion of macro 'file'
  276 |  file("copypaste3");
      |  ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38