Submission #1351268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351268		hminhat	Collecting Stamps 4 (JOI25_stamps4)	C++20	0 / 100	24 ms	3808 KiB

Main

/*	
	ROAD TO TST 
*/
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define el "\n"
#define pb push_back
#define all(v) v.begin(), v.end()

#define rep(i, x, y) for(int i = x, _y = y; i <= _y; i++)
#define rev(i, x, y) for(int i = x, _y = y; i >= _y; i--)

void file() {
	#define name "test"
	if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	else {
		#undef name
		#define name "C:\\Users\\hminh\\Desktop\\2026\\AIO\\test"
		if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	}
}

const int nmax = 1e6 + 7;

int n, x, q, a[nmax], last[nmax >> 1];
ll C[nmax], dp[nmax];

struct fenwick {
	int fw[nmax << 1];

	void update(int u, int val) {
		for(;u <= (n << 1); u += u & (-u)) fw[u] += val;
	}

	int get(int u) {
		int res = 0;
		for(;u >= 1; u -= u & (-u)) res += fw[u];
		return res;
	}

	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
} fw;

int main()
{
	file();
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> x;
	n <<= 1;
	rep(i, 1, n) cin >> a[i], dp[i] = 2e18;
	rep(i, 1, n) cin >> C[i];
	dp[0] = 2e18;
	int cnt = 0;
	rep(i, 1, n) {
		if(last[a[i]]) fw.update(i, 1);
		else cnt += fw.get(1, i);
		last[a[i]] = i;
	}
	dp[cnt] = C[1];
	rep(i, 2, n) {
		int p = last[a[i - 1]];
		cnt -= (n + i - p - 1) - fw.get(p, n + i - 2);
		fw.update(p, -1);
		cnt += fw.get(1, p);
		last[a[i - 1]] = n + i - 1;
		fw.update(n + i - 1, 1);
		dp[cnt] = min(dp[cnt], C[i]);
	}
	rev(i, n * (n - 1) / 2, 0) dp[i] = min(dp[i], dp[i + 1] + x);
	cin >> q;
	while(q -- ) {
		ll k;
		cin >> k;
		cout << dp[1LL * n * n / 4 - k] << el;
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void file()':
Main.cpp:21:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:84: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 5
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 19
• Subtask 6: 0 / 21
• Subtask 7: 0 / 15