/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Wrong Answer 23ms 592.0 KiB
#3 Wrong Answer 45ms 572.0 KiB

Code

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <deque>
#include <climits>
#include <cmath>
#include <numeric>
#include <string>
#include <bitset>
#include <assert.h>
#include <iomanip>
using namespace std;
 
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
/*
#include <bits/stdc++.h>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrand(l, r) uniform_int_distribution<int>(l, r)(rng)
*/
 
const long long infl = 1e18 + 1;
const int inf = 1e9 + 1;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const long double eps = 1e-7;
const int mod = mod1;
 
int add(int a, int b) { return (a + b) % mod; }
int sub(int a, int b) { return (a - b + mod) % mod; }
int mul(int a, int b) { return (int)((long long)a * b % mod); }
int pwr(int a, int b = mod - 2)
{
	int res = 1;
	for(; b > 0; b >>= 1, a = mul(a, a))
		if(b & 1)
			res = mul(res, a);
	return res;
}
template <typename T>
bool chmax(T &a, T b)
{
	if(b > a)
	{
		a = b;
		return true;
	}
	return false;
}
template <typename T>
bool chmin(T &a, T b)
{
	if(b < a)
	{
		a = b;
		return true;
	}
	return false;
}

void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for(auto &i: a)
		cin >> i;
	if(n == k)
	{
		cout << accumulate(a.begin(), a.end(), 0ll);
		return;
	}
	vector spt(n, vector<int>(21, 0));
	for(int i = 0; i < n; i++)
		spt[i][0] = a[i];
	for(int j = 1; j < 21; j++)
		for(int i = 0;  i + (1 << (j - 1)) < n; i++)
			spt[i][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
	auto query = [&](int l, int r) -> int
	{
		int lg = __lg(r - l + 1);
		return min(spt[l][lg], spt[r - (1 << lg) + 1][lg]);
	};
	vector spt2(n, vector<int>(21, 0));
	for(int i = 0; i < n; i++)
		spt2[i][0] = a[i];
	for(int j = 1; j < 21; j++)
		for(int i = 0; i + (1 << (j - 1)) < n; i++)
			spt2[i][j] = max(spt2[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
	auto query2 = [&](int l, int r) -> int
	{
		int lg = __lg(r - l + 1);
		return max(spt2[l][lg], spt2[r - (1 << lg) + 1][lg]);
	};
	vector<long long> pref(n);
	for(int i = 0; i < n; i++)
	{
		if(i)
			pref[i] = pref[i - 1];
		pref[i] += a[i];
	}
	long long mn = infl;
	for(int i = k - 1; i < n; i++)
	{
		int add = inf;
		if(i == k - 1)
			add = min(add, query(i + 1, n - 1));
		else if(i == n - 1)
			add = min(add, query(0, i - k));
		else
			add = min({add, query(0, i - k), query(i + 1, n - 1)});
		int mx = query2(i - k + 1, i);
		mn = min(mn, pref[i] - (i == k - 1 ? 0 : pref[i - k]));
		mn = min(mn, pref[i] - (i == k - 1 ? 0 : pref[i - k]) - mx + add);
	}

	cout << mn;
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t = 1;
	cin >> t;
 
	while (t--)
	{
		solve();
		cout << (t ? "\n" : "");
	}
}

Information

Submit By
Type
Submission
Problem
P1149 Swap and Minimize
Contest
LU IUJPC : Sylhet Division 2024 Replay Contest
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-10 09:18:39
Judged At
2024-12-10 09:18:39
Judged By
Score
1
Total Time
45ms
Peak Memory
592.0 KiB