oj.uz

Submission #988064

# Submission time Handle Problem Language Result Execution time Memory
988064 2024-05-24T02:49:11 Z vjudge1 Feast (NOI19_feast) C++17
53 / 100
 1000 ms 25992 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});
	}
}

const LL INF = 1e18;

int n, k;
VI a;

PLL solve(LL lambda)
{
	vector < vector <PLL> > dp(n + 1, vector <PLL> (2, {-INF, 0}));
	dp[0][0] = {0, 0};
	FOR(i, 1, n)
	{
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		dp[i][1] = max(
			MP(dp[i - 1][0].X + a[i] - lambda, dp[i - 1][0].Y + 1),
			MP(dp[i - 1][1].X + a[i], dp[i - 1][1].Y));
	}
	return max(dp[n][0], dp[n][1]);
}

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 = 3e14;
	while (r - l > 1)
	{
		LL m = (l + r) / 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 950 ms 22348 KB Output is correct
2 Correct 984 ms 25356 KB Output is correct
3 Correct 952 ms 25716 KB Output is correct
4 Correct 945 ms 25612 KB Output is correct
5 Correct 965 ms 25400 KB Output is correct
6 Correct 930 ms 25036 KB Output is correct
7 Correct 894 ms 24924 KB Output is correct
8 Correct 979 ms 25672 KB Output is correct
9 Correct 937 ms 25276 KB Output is correct
10 Correct 930 ms 25288 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 22176 KB Output is correct
2 Correct 935 ms 23860 KB Output is correct
3 Correct 883 ms 23588 KB Output is correct
4 Correct 910 ms 23796 KB Output is correct
5 Correct 944 ms 25324 KB Output is correct
6 Correct 931 ms 23404 KB Output is correct
7 Correct 930 ms 24128 KB Output is correct
8 Correct 940 ms 25540 KB Output is correct
9 Correct 889 ms 24844 KB Output is correct
10 Correct 955 ms 24012 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 22780 KB Output is correct
2 Correct 967 ms 25408 KB Output is correct
3 Correct 944 ms 25592 KB Output is correct
4 Correct 967 ms 25636 KB Output is correct
5 Correct 977 ms 25516 KB Output is correct
6 Correct 1000 ms 25836 KB Output is correct
7 Execution timed out 1032 ms 25992 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 4 ms 348 KB Output is correct
22 Correct 4 ms 348 KB Output is correct
23 Correct 4 ms 344 KB Output is correct
24 Correct 4 ms 344 KB Output is correct
25 Correct 4 ms 348 KB Output is correct
26 Correct 4 ms 356 KB Output is correct
27 Correct 4 ms 348 KB Output is correct
28 Correct 4 ms 348 KB Output is correct
29 Correct 5 ms 348 KB Output is correct
30 Correct 5 ms 344 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 22348 KB Output is correct
2 Correct 984 ms 25356 KB Output is correct
3 Correct 952 ms 25716 KB Output is correct
4 Correct 945 ms 25612 KB Output is correct
5 Correct 965 ms 25400 KB Output is correct
6 Correct 930 ms 25036 KB Output is correct
7 Correct 894 ms 24924 KB Output is correct
8 Correct 979 ms 25672 KB Output is correct
9 Correct 937 ms 25276 KB Output is correct
10 Correct 930 ms 25288 KB Output is correct
11 Correct 919 ms 22176 KB Output is correct
12 Correct 935 ms 23860 KB Output is correct
13 Correct 883 ms 23588 KB Output is correct
14 Correct 910 ms 23796 KB Output is correct
15 Correct 944 ms 25324 KB Output is correct
16 Correct 931 ms 23404 KB Output is correct
17 Correct 930 ms 24128 KB Output is correct
18 Correct 940 ms 25540 KB Output is correct
19 Correct 889 ms 24844 KB Output is correct
20 Correct 955 ms 24012 KB Output is correct
21 Correct 971 ms 22780 KB Output is correct
22 Correct 967 ms 25408 KB Output is correct
23 Correct 944 ms 25592 KB Output is correct
24 Correct 967 ms 25636 KB Output is correct
25 Correct 977 ms 25516 KB Output is correct
26 Correct 1000 ms 25836 KB Output is correct
27 Execution timed out 1032 ms 25992 KB Time limit exceeded
28 Halted 0 ms 0 KB -