Submission #56550368

---

Source Code Expand

#include <bits/stdc++.h>
// 针对于线上比赛的 C++ 语言模板
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;

//#undef ONLINE_JUDGE // 如果是交互要改动这里
#define int long long

#ifndef ONLINE_JUDGE
#define endl '\n'
#define debug(x, ...) printf(x, __VA_ARGS__)
#else
#define debug(x, ...)
#endif

void clear() {
	// 请在这里完善初始化代码
}

int n, k;
pair<int, int> a[200005];
int dp[200005][13];

int dfs(int i, int k) {
	if (k == 0) return 1;
	if (i == n + 1) return -1ll << 50;
	if (dp[i][k] != -1) return dp[i][k];
	return dp[i][k] = max(dfs(i + 1, k), dfs(i + 1, k - 1) * a[i].first + a[i].second);
}

bool cmp1(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.first != b.first) return a.first < b.first;
	return a.second > b.second;
}
bool cmp2(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.first != b.first) return a.first > b.first;
	return a.second > b.second;
}
bool cmp3(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.first != b.first) return a.first < b.first;
	return a.second < b.second;
}
bool cmp4(const pair<int, int> &a, const pair<int, int> &b) {
	if (a.first != b.first) return a.first > b.first;
	return a.second < b.second;
}

void solve() {
	cin >> n >> k;
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].first >> a[i].second;
	}
	memset(dp, 255, sizeof(dp));
	sort(a + 1, a + n + 1, cmp1);
	ans = max(ans, dfs(1, k));
		memset(dp, 255, sizeof(dp));
		sort(a + 1, a + n + 1, cmp2);
		ans = max(ans, dfs(1, k));
			memset(dp, 255, sizeof(dp));
			sort(a + 1, a + n + 1, cmp3);
			ans = max(ans, dfs(1, k));
				memset(dp, 255, sizeof(dp));
				sort(a + 1, a + n + 1, cmp4);
				ans = max(ans, dfs(1, k)); mt19937 rnd(147744151);
	while (clock() * 1.0 / CLOCKS_PER_SEC <= 1.92) {
		shuffle(a + 1, a + n + 1, rnd);
		ans = max(ans, dfs(1, k));
	}
	cout << ans << "\n";
}

/*
abcde+1bcde+2cde+3de+4e+5
*/
signed main() {
	#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#endif

	int tc = 1;
//	cin >> tc; // 若不启用多测，请注释该内容
	while (tc--) {
		clear();
		solve();
	}
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘long long int dfs(long long int, long long int)’:
Main.cpp:68:37: warning: left shift of negative value [-Wshift-negative-value]
   68 |         if (i == n + 1) return -1ll << 50;
      |                                ~~~~~^~~~~

Judge Result