oj.uz

Submission #988056

# Submission time Handle Problem Language Result Execution time Memory
988056 2024-05-24T01:53:51 Z vjudge1 Feast (NOI19_feast) C++17
22 / 100
 152 ms 8116 KB 
//Code by Patcas Csaba aka SleepyOverlord
#include <vector>
#include <array>
#include <string> 
#include <set> 
#include <map> 
#include <unordered_set>
#include <unordered_map>
#include <queue> 
#include <bitset> 
#include <stack>
#include <list>

#include <numeric> 
#include <algorithm> 
#include <random>
#include <chrono>

#include <cstdio>
#include <fstream>
#include <iostream> 
#include <sstream> 
#include <iomanip>
#include <climits>

#include <cctype>
#include <cmath> 
#include <ctime>
#include <cassert>

using namespace std;

#define ULL unsigned long long
#define LL long long
#define PII pair <int, int>
#define PLL pair <LL, LL>
#define VB vector <bool>
#define VI vector <int>
#define VLL vector <LL>
#define VD vector <double>
#define VS vector <string>
#define VPII vector <pair <int, int> >
#define VVI vector < VI >
#define VVLL vector < VLL >
#define VVB vector < VB >
#define SI set < int >
#define USI unordered_set <int>
#define MII map <int, int>
#define UMII unordered_map <int, int>

#define FORN(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define MX(x, y) x = max(x, y)
#define MN(x, y) x = min(x, y)

#define SZ size()
#define BG begin() 
#define EN end() 
#define CL clear()
#define X first
#define Y second
#define RS resize
#define PB push_back
#define MP make_pair
#define ALL(x) x.begin(), x.end()
#define INS insert
#define ER erase
#define CNT count

template <class T> ostream& operator <<(ostream & os, const vector<T> &vec)
{
	for (int i = 0; i < vec.size() - 1; ++i) os << vec[i] << ' ';
	return os << vec[vec.size() - 1];
}

template <class T1, class T2> ostream& operator <<(ostream & os, const pair<T1, T2> &p)
{
	return os << p.X << " " << p.Y;
}

template <typename T>
void pr(T var1)
{
	cout << var1 << '\n';
}
template <typename T, typename... Types>
void pr(T var1, Types... var2)
{
	cout << var1;
	pr(var2...);
}

void in(int &n, VI &a) //array of ints
{
	cin >> n;
	a.CL, a.RS(n + 1);
	FOR(i, 1, n) cin >> a[i];
}

void in(int &n, VS &a) //array of strings
{
	cin >> n;
	a.CL, a.RS(n + 1);
	FOR(i, 1, n) cin >> a[i];
}

void in(int &n, VPII &a) //array of pairs
{
	cin >> n;
	a.CL, a.RS(n + 1);
	FOR(i, 1, n) cin >> a[i].X >> a[i].Y;
}

void in(int &n, int &m, VVI &g) //unweighted graph
{
	cin >> n >> m;
	g.CL, g.RS(n + 1);
	FOR(i, 1, n)
	{
		int x, y;
		cin >> x >> y;
		g[x].PB(y);
		g[y].PB(x);
	}
}

void in(int &n, VVI &g) //unweighted tree
{
	cin >> n;
	g.CL, g.RS(n + 1);
	FOR(i, 1, n - 1)
	{
		int x, y;
		cin >> x >> y;
		g[x].PB(y);
		g[y].PB(x);
	}
}

void in(int &n, int &m, vector <VPII> &g) //weighted graph
{
	cin >> n >> m;
	g.CL, g.RS(n + 1);
	FOR(i, 1, n)
	{
		int x, y, z;
		cin >> x >> y >> z;
		g[x].PB({y, z});
		g[y].PB({x, z});
	}
}

void in(int &n, vector <VPII> &g) //weighted tree
{
	cin >> n;
	g.CL, g.RS(n + 1);
	FOR(i, 1, n - 1)
	{
		int x, y, z;
		cin >> x >> y >> z;
		g[x].PB({y, z});
		g[y].PB({x, z});
	}
}

int n, k;
VI a;

pair <LL, int> solve(LL lambda)
{
	VLL dp(n + 1);
	VI ppl(n + 1);
	LL sum = 0;
	int prev = 0;
	FOR(i, 1, n)
	{
		sum += a[i];
		if (sum < 0) sum = 0, prev = i;
		dp[i] = dp[i - 1], ppl[i] = ppl[i - 1];
		if (dp[i] < sum - lambda)
		{
			dp[i] = sum - lambda;
			ppl[i] = 1;
		}
		if (sum > 0 and dp[i] < dp[prev] + sum - lambda)
		{
			dp[i] = dp[prev] + sum - lambda;
			ppl[i] = ppl[prev] + 1;
		}
	}
	return {dp[n], ppl[n]};
}

int main()
{
	#ifdef AT_HOME
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	#endif

	cin >> n >> k;
	a.RS(n + 1);
	FOR(i, 1, n) cin >> a[i];

	LL l = 0, r = 1e18;
	while (r - l > 1)
	{
		LL m = (r + l) / 2;
		auto aux = solve(m);
		if (aux.Y > k) l = m;
		else r = m;
	}
	auto aux = solve(r);
	pr(aux.X + aux.Y * r);

	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 7748 KB Output is correct
2 Correct 124 ms 7868 KB Output is correct
3 Correct 146 ms 7972 KB Output is correct
4 Correct 121 ms 7820 KB Output is correct
5 Correct 121 ms 7816 KB Output is correct
6 Correct 119 ms 7688 KB Output is correct
7 Correct 118 ms 7732 KB Output is correct
8 Correct 120 ms 7868 KB Output is correct
9 Correct 119 ms 7692 KB Output is correct
10 Correct 137 ms 7764 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5976 KB Output is correct
2 Correct 87 ms 6224 KB Output is correct
3 Correct 98 ms 6048 KB Output is correct
4 Incorrect 87 ms 6104 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 8020 KB Output is correct
2 Correct 144 ms 7872 KB Output is correct
3 Correct 151 ms 7972 KB Output is correct
4 Correct 144 ms 7836 KB Output is correct
5 Correct 145 ms 7952 KB Output is correct
6 Correct 149 ms 8116 KB Output is correct
7 Correct 148 ms 8112 KB Output is correct
8 Correct 148 ms 8020 KB Output is correct
9 Correct 146 ms 8092 KB Output is correct
10 Correct 152 ms 8056 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 7748 KB Output is correct
2 Correct 124 ms 7868 KB Output is correct
3 Correct 146 ms 7972 KB Output is correct
4 Correct 121 ms 7820 KB Output is correct
5 Correct 121 ms 7816 KB Output is correct
6 Correct 119 ms 7688 KB Output is correct
7 Correct 118 ms 7732 KB Output is correct
8 Correct 120 ms 7868 KB Output is correct
9 Correct 119 ms 7692 KB Output is correct
10 Correct 137 ms 7764 KB Output is correct
11 Correct 86 ms 5976 KB Output is correct
12 Correct 87 ms 6224 KB Output is correct
13 Correct 98 ms 6048 KB Output is correct
14 Incorrect 87 ms 6104 KB Output isn't correct
15 Halted 0 ms 0 KB -