CSES - Datatähti 2020 alku - Results
Submission details
Task:Ruudukko
Sender:lady-stardust
Submission time:2019-10-01 19:51:17 +0300
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#10.01 sdetails
#20.01 sdetails
#30.01 sdetails
#40.01 sdetails
#50.01 sdetails
#60.01 sdetails

Code

#include <bits/stdc++.h>
using namespace std;

#define kantama 0
#define hinta 1
#define seuraavaOptimiIndeksi 2
#define optimiHintaLoppuun 3
#define ll long long

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

	ll n; cin >> n;

	vector<tuple<ll, ll, ll, ll>> mastot;

	for (ll i = 0; i < n; i++) {
		ll a; cin >> a;
		mastot.push_back(make_tuple(a, 0, 10e12, 10e12));
	}

	for (ll i = 1; i < n; i++) {
		ll a; cin >> a;
		get<hinta>(mastot[i]) = a;
	}

	mastot.push_back(make_tuple(0, 0, 10e12, 0));

	ll viimeinenMastoIndeksi = mastot.size() - 1;

	for (ll i = viimeinenMastoIndeksi - 1; i >= 0; i--) {
		auto &masto = mastot[i];

		ll uusinOptimiHintaLoppuun = 10e15; // 10e12, 10e13 = wrong answer, 10e16 = time limit
		ll uusinSeuraavaOptimiIndeksi = 0;
		ll tutkittavaIndeksi = i + 1;
		ll viimeinenTutkittavaIndeksi = min(i + get<kantama>(masto), viimeinenMastoIndeksi);

		while (tutkittavaIndeksi <= viimeinenTutkittavaIndeksi) {
			auto &tutkittavaMasto = mastot[tutkittavaIndeksi];

			if (get<optimiHintaLoppuun>(tutkittavaMasto) < uusinOptimiHintaLoppuun) {
				uusinOptimiHintaLoppuun = get<optimiHintaLoppuun>(tutkittavaMasto);
				uusinSeuraavaOptimiIndeksi = tutkittavaIndeksi;
			}

			if (get<seuraavaOptimiIndeksi>(tutkittavaMasto) <= viimeinenTutkittavaIndeksi) {
				auto toisenMastonOpitimiHintaLoppuun = get<optimiHintaLoppuun>(tutkittavaMasto) - get<hinta>(tutkittavaMasto);

				if (toisenMastonOpitimiHintaLoppuun < uusinOptimiHintaLoppuun) {
					uusinOptimiHintaLoppuun = toisenMastonOpitimiHintaLoppuun;
					uusinSeuraavaOptimiIndeksi = get<seuraavaOptimiIndeksi>(tutkittavaMasto);
					tutkittavaIndeksi = get<seuraavaOptimiIndeksi>(tutkittavaMasto);
				}
			}


			tutkittavaIndeksi++;
		}

		get<seuraavaOptimiIndeksi>(masto) = uusinSeuraavaOptimiIndeksi;
		get<optimiHintaLoppuun>(masto) = uusinOptimiHintaLoppuun + get<hinta>(masto);
	}

	cout << get<optimiHintaLoppuun>(mastot[0]);
}

Test details

Test 1

Verdict:

input
1

correct output

user output
0

Test 2

Verdict:

input
2

correct output
1 2 
2 1 

user output
0

Test 3

Verdict:

input
5

correct output
1 2 3 4 5 
2 1 4 3 6 
3 4 1 2 7 
4 3 2 1 8 
5 6 7 8 1 

user output
0

Test 4

Verdict:

input
42

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
0

Test 5

Verdict:

input
99

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
0

Test 6

Verdict:

input
100

correct output
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
0