oj.uz

Submission #988059

# Submission time Handle Problem Language Result Execution time Memory
988059 2024-05-24T02:06:25 Z vjudge1 Feast (NOI19_feast) C++17
22 / 100
 171 ms 6908 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 or
			dp[i] == dp[prev] + sum - lambda and ppl[i] < ppl[prev] + 1)
		{
			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;
}

Compilation message

feast.cpp: In function 'std::pair<long long int, int> solve(long long int)':
feast.cpp:182:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  182 |    dp[i] == dp[prev] + sum - lambda and ppl[i] < ppl[prev] + 1)

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6460 KB Output is correct
2 Correct 118 ms 6836 KB Output is correct
3 Correct 120 ms 6896 KB Output is correct
4 Correct 119 ms 6780 KB Output is correct
5 Correct 117 ms 6808 KB Output is correct
6 Correct 115 ms 6408 KB Output is correct
7 Correct 114 ms 6484 KB Output is correct
8 Correct 120 ms 6788 KB Output is correct
9 Correct 115 ms 6480 KB Output is correct
10 Correct 117 ms 6736 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5656 KB Output is correct
2 Correct 85 ms 5784 KB Output is correct
3 Correct 84 ms 5712 KB Output is correct
4 Incorrect 84 ms 5712 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 6840 KB Output is correct
2 Correct 149 ms 6708 KB Output is correct
3 Correct 144 ms 6808 KB Output is correct
4 Correct 143 ms 6688 KB Output is correct
5 Correct 144 ms 6860 KB Output is correct
6 Correct 149 ms 6800 KB Output is correct
7 Correct 146 ms 6820 KB Output is correct
8 Correct 171 ms 6740 KB Output is correct
9 Correct 146 ms 6908 KB Output is correct
10 Correct 144 ms 6788 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 6460 KB Output is correct
2 Correct 118 ms 6836 KB Output is correct
3 Correct 120 ms 6896 KB Output is correct
4 Correct 119 ms 6780 KB Output is correct
5 Correct 117 ms 6808 KB Output is correct
6 Correct 115 ms 6408 KB Output is correct
7 Correct 114 ms 6484 KB Output is correct
8 Correct 120 ms 6788 KB Output is correct
9 Correct 115 ms 6480 KB Output is correct
10 Correct 117 ms 6736 KB Output is correct
11 Correct 85 ms 5656 KB Output is correct
12 Correct 85 ms 5784 KB Output is correct
13 Correct 84 ms 5712 KB Output is correct
14 Incorrect 84 ms 5712 KB Output isn't correct
15 Halted 0 ms 0 KB -