제출 #1123938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123938		kh0i	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	386 ms	49660 KiB

copypaste3

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 2503;

struct Hash1{
    const ll base = 311;
    const ll MOD = 1e9 + 3;

    int n;
    string s;
    vector<ll> p, hash;

    void precalc(int _n){
        hash.resize(_n + 2, 0);
        p.resize(_n + 2, 0);
        p[0] = 1;
        for(int i = 1; i <= _n; ++i)
            p[i] = (p[i - 1] * base) % MOD;
    }

    void init(string x){
        n = x.size();

        precalc(n);

        s = ' ' + x;
        for(int i = 1; i <= n; ++i)
            hash[i] = (hash[i - 1] * base + (s[i] - 'a' + 1)) % MOD;
    }

    ll get_hash(int l, int r){
        return (hash[r] - hash[l - 1] * p[r - l + 1] + MOD * MOD) % MOD;
    }

    ll get_single_hash(string x){
        ll res = 0;
        for(int i = 0; i < sz(x); ++i)
            res = (res * base + (x[i] - 'a' + 1)) % MOD;
        return res;
    }
} hsh1;

struct Hash2{
    const ll base = 31;
    const ll MOD = 1e9 +7;

    int n;
    string s;
    vector<ll> p, hash;

    void precalc(int _n){
        hash.resize(_n + 2, 0);
        p.resize(_n + 2, 0);
        p[0] = 1;
        for(int i = 1; i <= _n; ++i)
            p[i] = (p[i - 1] * base) % MOD;
    }

    void init(string x){
        n = x.size();

        precalc(n);

        s = ' ' + x;
        for(int i = 1; i <= n; ++i)
            hash[i] = (hash[i - 1] * base + (s[i] - 'a' + 1)) % MOD;
    }

    ll get_hash(int l, int r){
        return (hash[r] - hash[l - 1] * p[r - l + 1] + MOD * MOD) % MOD;
    }

    ll get_single_hash(string x){
        ll res = 0;
        for(int i = 0; i < sz(x); ++i)
            res = (res * base + (x[i] - 'a' + 1)) % MOD;
        return res;
    }
} hsh2;

int n;
string s;
ll a, b, c;

ll f[N][N];
int nx[N];

void mini(ll &x, ll y){
    if(x > y)
        x = y;
}

void solve(){
    cin >> n >> s >> a >> b >> c;

    hsh1.init(s);
    hsh2.init(s);

    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i <= n; ++i)
        f[i][i - 1] = 0;
    for(int len = 1; len <= n; ++len){
        vector<pair<pii, int>> vals;
        memset(nx, 0, sizeof(nx));
        for(int i = 1; i + len - 1 <= n; ++i)
            vals.emplace_back(make_pair(hsh1.get_hash(i, i + len - 1), hsh2.get_hash(i, i + len - 1)), i);
        sort(all(vals));
        for(int i = 0; i < sz(vals); ++i){
            int j = i;
            while(j + 1 < sz(vals) and vals[j + 1].F == vals[i].F)
                ++j;
            int k = i, l = i;
            while(true){
                while(l <= j and vals[k].S + len - 1 >= vals[l].S)
                    ++l;
                if(l > j)
                    break;
                nx[vals[k].S] = vals[l].S;
                ++k;
            }
            i = j;
        }
        for(int l = 1; l + len - 1 <= n; ++l){
            int r = l + len - 1;
            mini(f[l][r], f[l + 1][r] + a);
            mini(f[l][r], f[l][r - 1] + a);
            r = nx[l];
            ll cnt = 1;
            while(r and r + len - 1 <= n){
                ++cnt;
                mini(f[l][r + len - 1], f[l][l + len - 1] + b + c * cnt + (r + len - l - cnt * len) * a);
                r = nx[r];
            }
        }
    }

    cout << f[1][n];
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

copypaste3.cpp: In function 'int32_t main()':
copypaste3.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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