제출 #1299324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1299324		TrieTr	Copy and Paste 3 (JOI22_copypaste3)	C++20	25 / 100	15 ms	9548 KiB

copypaste3

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

void local() {
    #define taskname ""
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
}

#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;}
template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;}

const int N = 1e6 + 5;

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

namespace sub3 {
	bool check() {
		return n <= 30;
	}
	const int N = 30 + 5;
	const int mod = 1e9 + 321;
	const int base = 311;

	int Hash[N];
	int po[N];
	int get(int l, int r) {
		return (Hash[r] - 1ll * Hash[l - 1] * po[r - l + 1] + 1ll * mod * mod) % mod;
	}
	ll dp[N][N];

	void solve() {
		reverse(s.begin(), s.end()); s = '#' + s;
		for(int i = 1; i <= n; i++) Hash[i] = (1ll * Hash[i - 1] * base + s[i]) % mod;	
		po[0] = 1; for(int i = 1; i <= n; i++) po[i] = 1ll * po[i - 1] * base % mod;
		for(int l = n; l > 0; l--) {
			dp[l][l] = a;
			for(int r = l + 1; r <= n; r++) {
				dp[l][r] = 1ll * (r - l + 1) * a;
				for(int k = l; k < r; k++) {
					mini(dp[l][r], 1ll * (k - l + 1) * a + dp[k + 1][r]);
					int len = k - l + 1;
					int cntC = 1;
					for(int p = k + 1; p + len - 1 <= r; p++) {
						if(get(l, k) == get(p, p + len - 1)) {
							cntC++;
							p = p + len - 1;
						}
					}
					mini(dp[l][r], dp[l][k] + b + 1ll * cntC * c + 1ll * (r - l + 1 - 1ll * len * cntC) * a);
				}
			}
		}
		cout << dp[1][n];
	}
}

namespace sub4 {
	bool check() {
		return n <= 2e2;
	}
	const int N = 2e2 + 5;
	const int mod = 1e9 + 321;
	const int base = 311;

	int Hash[N];
	int po[N];
	int get(int l, int r) {
		return (Hash[r] - 1ll * Hash[l - 1] * po[r - l + 1] + 1ll * mod * mod) % mod;
	}
	ll dp[N][N];
	int cnt[N][N][N];

	void solve() {
		s = '#' + s;
		for(int i = 1; i <= n; i++) Hash[i] = (1ll * Hash[i - 1] * base + s[i]) % mod;	
		po[0] = 1; for(int i = 1; i <= n; i++) po[i] = 1ll * po[i - 1] * base % mod;
		for(int l = 1; l <= n; l++) {
			for(int r = l; r <= n; r++) {
				int len = r - l + 1;
				for(int i = r + len; i <= n; i++) {
					cnt[l][r][i] = cnt[l][r][i - 1];
					if(get(l, r) == get(i - len + 1, i)) {
						cnt[l][r][i] = cnt[l][r][i - len] + 1;
					}
				}
			}
		}
		for(int l = n; l > 0; l--) {
			dp[l][l] = a;
			for(int r = l + 1; r <= n; r++) {
				dp[l][r] = a + dp[l + 1][r];
				for(int k = l; k < r; k++) {
					int len = k - l + 1;
					int cntC = 1 + cnt[l][k][r];
					//cout << l << ' ' << r << ' ' << dp[l][k] + b + 1ll * cntC * c + 1ll * (r - l + 1 - 1ll * len * cntC) * a << '\n';
					mini(dp[l][r], dp[l][k] + b + 1ll * cntC * c + 1ll * (r - l + 1 - 1ll * len * cntC) * a);
				}
			}
		}
		cout << dp[1][n];
	}
}

int main() {
    fastio; local();
    cin >> n >> s >> a >> b >> c;
    if(sub4::check()) sub4::solve();
}

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

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

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