oj.uz

Submission #722658

# Submission time Handle Problem Language Result Execution time Memory
722658 2023-04-12T14:18:23 Z Zanite Feast (NOI19_feast) C++17
12 / 100
 104 ms 9700 KB 
// 赤コーダーになりたい
// お願い いいですか？

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si	= short int;
using ll	= long long;
using lll	= __int128;
using ld	= long double;

// Pairs
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pll	= pair<ll, ll>;
using plll	= pair<lll, lll>;
using pld	= pair<ld, ld>;
#define fi	first
#define se	second

// For
#define Frue(i, n, N)		for (int i = (n); i <= (N); i++)
#define  Fru(i, n, N)		for (int i = (n); i <  (N); i++)
#define Frde(i, n, N)		for (int i = (n); i >= (N); i--)
#define  Frd(i, n, N)		for (int i = (n); i >  (N); i--)

// PBDS
template<typename Z>
using ordered_set	= tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs
template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
	return os << '(' << p.fi << ',' << p.se << ')';
}
template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) {
	os << '{'; bool _first = 1;
	for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;}
	return os << '}';
}
template<typename Z, unsigned long long sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) {
	os << '{'; bool _first = 1;
	for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;}
	return os << '}';
}

// Quick macro functions
#define sqr(x)			((x)*(x))
#define debug(x)		cout << #x << " = " << (x) << '\n'
#define debugV(v, x)	cout << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define rrebug(x)		cerr << #x << " = " << (x) << '\n'
#define rrebugV(v, x)	cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n'

#define All(x)			x.begin(), x.end()
#define Sort(x)			sort(All(x))
#define Reverse(x)		reverse(All(x))
#define Uniqueify(x)	Sort(x); x.erase(unique(All(x)), x.end())

#define RandomSeed			chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases	int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Check min and max
template<typename Z> void chmin(Z &a, Z b) {a = min(a, b);}
template<typename Z> void chmax(Z &a, Z b) {a = max(a, b);}
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
	int v;
	ModInt() : v(0) {}
	ModInt(long long _v) {
		v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
		if (v < 0) v += MOD;
	}
 
	friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;}
	friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;}
	friend bool operator< (const ModInt &a, const ModInt &b) {return a.v <  b.v;}
	friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;}
	friend bool operator> (const ModInt &a, const ModInt &b) {return a.v >  b.v;}
	friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;}
 
	ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;}
	ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;}
	ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;}
	ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);}
 
	friend ModInt pow(ModInt a, long long x) {
		ModInt res = 1;
		for (; x; x /= 2, a *= a) if (x & 1) res *= a;
		return res;
	}
	friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);}
 
	ModInt operator+ () const {return ModInt( v);}
	ModInt operator- () const {return ModInt(-v);}
	ModInt operator++() const {return *this += 1;}
	ModInt operator--() const {return *this -= 1;}
 
	friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;}
	friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;}
	friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;}
	friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;}
 
	friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;}
	friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;}
};
const int ModA	= 998244353;
const int ModC	= 1e9 + 7;
using MintA	= ModInt<ModA>;
using MintC	= ModInt<ModC>;

// Other constants
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

const int maxN	= 3e5 + 5;
const ll maxA	= 1e9;

ll N, K, A[maxN], pf[maxN];
pll dp[maxN];

pll sub(pll x, pll y) {return {x.fi - y.fi, x.se - y.se};}

pll calc(ll C) {
	// debug(C);
	dp[0] = {0, 0};
	pll mx = {pf[N], 0};
	for (int i = 1; i <= N; i++) {
		dp[i] = max(
			dp[i-1],
			sub(mx, {pf[N] - pf[i] + C, -1})
		);
		chmax(mx, {dp[i].fi + pf[N] - pf[i], dp[i].se});
		// debugV(dp, i);
	}
	// debug(dp[N]);
	return dp[N];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> N >> K;
	Frue(i, 1, N) {
		cin >> A[i];
		pf[i] = pf[i-1] + A[i];
	}

	// Find max(F) -> because F is convex, max(F) is G_0
	pll hmx = calc(0);
	// debug(hmx);
	if (hmx.se <= K) {
		cout << hmx.fi << '\n';
		return 0;
	}

	// Find max X s.t. dF(K) <= X
	// Binser on X
	ll l = -maxA, r = maxA, ans, bt;
	while (l <= r) {
		ll m = (l + r) / 2;

		// Find max Y s.t. dF(Y) >= m
		pll Y = calc(m);
		if (Y.se < K) {
			r = m-1;
		} else {
			ans = m;
			bt = Y.fi + K * ans;
			l = m+1;
		}
	}
	cout << bt << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9408 KB Output is correct
2 Correct 83 ms 9480 KB Output is correct
3 Correct 64 ms 9700 KB Output is correct
4 Correct 60 ms 9520 KB Output is correct
5 Correct 65 ms 9580 KB Output is correct
6 Correct 60 ms 9312 KB Output is correct
7 Correct 61 ms 9296 KB Output is correct
8 Correct 62 ms 9508 KB Output is correct
9 Correct 58 ms 9432 KB Output is correct
10 Correct 59 ms 9528 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9472 KB Output is correct
2 Correct 45 ms 9660 KB Output is correct
3 Correct 49 ms 9460 KB Output is correct
4 Correct 51 ms 9564 KB Output is correct
5 Correct 67 ms 9380 KB Output is correct
6 Correct 46 ms 9428 KB Output is correct
7 Correct 49 ms 9684 KB Output is correct
8 Correct 60 ms 9548 KB Output is correct
9 Correct 62 ms 9368 KB Output is correct
10 Correct 56 ms 9536 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 9552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9408 KB Output is correct
2 Correct 83 ms 9480 KB Output is correct
3 Correct 64 ms 9700 KB Output is correct
4 Correct 60 ms 9520 KB Output is correct
5 Correct 65 ms 9580 KB Output is correct
6 Correct 60 ms 9312 KB Output is correct
7 Correct 61 ms 9296 KB Output is correct
8 Correct 62 ms 9508 KB Output is correct
9 Correct 58 ms 9432 KB Output is correct
10 Correct 59 ms 9528 KB Output is correct
11 Correct 44 ms 9472 KB Output is correct
12 Correct 45 ms 9660 KB Output is correct
13 Correct 49 ms 9460 KB Output is correct
14 Correct 51 ms 9564 KB Output is correct
15 Correct 67 ms 9380 KB Output is correct
16 Correct 46 ms 9428 KB Output is correct
17 Correct 49 ms 9684 KB Output is correct
18 Correct 60 ms 9548 KB Output is correct
19 Correct 62 ms 9368 KB Output is correct
20 Correct 56 ms 9536 KB Output is correct
21 Incorrect 104 ms 9552 KB Output isn't correct
22 Halted 0 ms 0 KB -