Submission #991207

#TimeUsernameProblemLanguageResultExecution timeMemory
991207yoav_sTortoise (CEOI21_tortoise)C++17
8 / 100
97 ms15396 KiB
#include <bits/stdc++.h> using namespace std; typedef int ll; typedef vector<ll> v; typedef vector<v> vv; typedef vector<vv> vvv; typedef vector<vvv> vvvv; typedef pair<ll, ll> p; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef pair<ll, p> tri; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; #define f first #define s second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() #define setmax(a, b) a = (a > b? a : b) const ll INF = 1e18; const ll mod = 1e9 + 7; ll solve(ll N, v &a, ll firstPos, ll secondPos, ll lastEaten, ll state, map<pair<p,p>,ll> &dp, v &firstParkLeft, v &firstParkRight){ if (firstPos >= 2 * N || lastEaten >= N) return 0; if (dp.count({{firstPos, secondPos},{lastEaten, state}}) > 0) return dp[{{firstPos, secondPos},{lastEaten, state}}]; if (state == 0) { ll res = solve(N, a, firstPos, secondPos, lastEaten + 1, state, dp, firstParkLeft, firstParkRight); if (a[lastEaten] == 1) { ll distance = abs(secondPos - lastEaten); if ((firstPos + distance) / 2 <= lastEaten) { setmax(res, solve(N, a, firstPos + distance, lastEaten, lastEaten + 1, 1, dp, firstParkLeft, firstParkRight) + 1); } } dp[{{firstPos, secondPos},{lastEaten, state}}] = res; return res; } ll res = 0; if (firstParkLeft[secondPos] > -1) { ll distance = abs(secondPos - firstParkLeft[secondPos]); if (firstPos + distance < 2 * N) setmax(res, solve(N, a, firstPos + distance, firstParkLeft[secondPos], lastEaten,0, dp, firstParkLeft, firstParkRight)); } if (firstParkRight[secondPos] < N) { ll distance = abs(secondPos - firstParkRight[secondPos]); if (firstPos + distance < 2 * N) setmax(res, solve(N, a, firstPos + distance, firstParkRight[secondPos], lastEaten,0, dp, firstParkLeft, firstParkRight)); } dp[{{firstPos, secondPos},{lastEaten, state}}] = res; return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll N; cin >> N; v a(N); for (ll i = 0; i < N; i++) cin >> a[i]; v firstParkLeft(N, -1), firstParkRight(N, N); ll lastPark = -1; for (ll i = 0; i < N; i++) { if (a[i] == -1) lastPark = i; firstParkLeft[i] = lastPark; } lastPark = N; for (ll i = N - 1; i >= 0; i--) { if (a[i] == -1) lastPark = i; firstParkRight[i] = lastPark; } map<pair<p, p>, ll> dp; ll res = solve(N, a, 0, 0, 0, 0, dp, firstParkLeft, firstParkRight); ll sum = 0; for (auto x : a) if (x > 0) sum += x; cout << sum - res << "\n"; return 0; }

Compilation message (stderr)

tortoise.cpp:29:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   29 | const ll INF = 1e18;
      |                ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...