oj.uz

Submission #988058

# Submission time Handle Problem Language Result Execution time Memory
988058 2024-05-24T02:01:58 Z vjudge1 Feast (NOI19_feast) C++17
22 / 100
 152 ms 8108 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] < 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 118 ms 7760 KB Output is correct
2 Correct 124 ms 7836 KB Output is correct
3 Correct 128 ms 7832 KB Output is correct
4 Correct 118 ms 8108 KB Output is correct
5 Correct 116 ms 7876 KB Output is correct
6 Correct 114 ms 7684 KB Output is correct
7 Correct 117 ms 7760 KB Output is correct
8 Correct 116 ms 7828 KB Output is correct
9 Correct 121 ms 7892 KB Output is correct
10 Correct 117 ms 7760 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6120 KB Output is correct
2 Correct 86 ms 6200 KB Output is correct
3 Correct 86 ms 6044 KB Output is correct
4 Incorrect 83 ms 6100 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 143 ms 8072 KB Output is correct
2 Correct 143 ms 7916 KB Output is correct
3 Correct 152 ms 8104 KB Output is correct
4 Correct 144 ms 7912 KB Output is correct
5 Correct 144 ms 8032 KB Output is correct
6 Correct 146 ms 8060 KB Output is correct
7 Correct 145 ms 8096 KB Output is correct
8 Correct 143 ms 8016 KB Output is correct
9 Correct 148 ms 8108 KB Output is correct
10 Correct 145 ms 8104 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 118 ms 7760 KB Output is correct
2 Correct 124 ms 7836 KB Output is correct
3 Correct 128 ms 7832 KB Output is correct
4 Correct 118 ms 8108 KB Output is correct
5 Correct 116 ms 7876 KB Output is correct
6 Correct 114 ms 7684 KB Output is correct
7 Correct 117 ms 7760 KB Output is correct
8 Correct 116 ms 7828 KB Output is correct
9 Correct 121 ms 7892 KB Output is correct
10 Correct 117 ms 7760 KB Output is correct
11 Correct 85 ms 6120 KB Output is correct
12 Correct 86 ms 6200 KB Output is correct
13 Correct 86 ms 6044 KB Output is correct
14 Incorrect 83 ms 6100 KB Output isn't correct
15 Halted 0 ms 0 KB -