hackercupai/hackercup
Data Preview The data available in this preview contains a 10 row dataset: Sample Dataset ("sample"): This is a subset of the full dataset, containing data from 2023. To view full dataset, download output_dataset.parquet. This contains data from 2011 to 2023. Fields The dataset include the following fields: name (string) year (string) round (string) statement (string) input (string) solution (string) code (string) sample_input (string) sample_output (string)… See the full description on the dataset page: https://huggingface.co/datasets/hackercupai/hackercup.
242.2k
1// Running on Fumes - Chapter 1
2// Solution by Jacob Plachta
3
4#include <algorithm>
5#include <functional>
6#include <numeric>
7#include <iostream>
8#include <iomanip>
9#include <cstdio>
10#include <cmath>
11#include <complex>
12#include <cstdlib>
13#include <ctime>
14#include <cstring>
15#include <cassert>
16#include <string>
17#include <vector>
18#include <list>
19#include <map>
20#include <set>
21#include <deque>
22#include <queue>
23#include <stack>
24#include <bitset>
25#include <sstream>
26using namespace std;
27
28#define LL long long
29#define LD long double
30#define PR pair<int,int>
31
32#define Fox(i,n) for (i=0; i<n; i++)
33#define Fox1(i,n) for (i=1; i<=n; i++)
34#define FoxI(i,a,b) for (i=a; i<=b; i++)
35#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
36#define FoxR1(i,n) for (i=n; i>0; i--)
37#define FoxRI(i,a,b) for (i=b; i>=a; i--)
38#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
39#define Min(a,b) a=min(a,b)
40#define Max(a,b) a=max(a,b)
41#define Sz(s) int((s).size())
42#define All(s) (s).begin(),(s).end()
43#define Fill(s,v) memset(s,v,sizeof(s))
44#define pb push_back
45#define mp make_pair
46#define x first
47#define y second
48
49template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
50template<typename T> T Sqr(T x) { return(x * x); }
51string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }
52
53const int INF = (int)1e9;
54const LD EPS = 1e-12;
55const LD PI = acos(-1.0);
56
57#define GETCHAR getchar_unlocked
58
59bool Read(int& x)
60{
61 char c, r = 0, n = 0;
62 x = 0;
63 for (;;)
64 {
65 c = GETCHAR();
66 if ((c < 0) && (!r))
67 return(0);
68 if ((c == '-') && (!r))
69 n = 1;
70 else
71 if ((c >= '0') && (c <= '9'))
72 x = x * 10 + c - '0', r = 1;
73 else
74 if (r)
75 break;
76 }
77 if (n)
78 x = -x;
79 return(1);
80}
81
82#define LIM 1000008
83#define IMP 1e18
84
85int N, M;
86int C[LIM];
87deque<pair<int, LL>> D; // <city, min. cost to be there with full tank>
88
89LL ProcessCase()90{
91 int i;
92 // input
93 Read(N), Read(M);
94 Fox(i, N)
95 Read(C[i]);
96 // iterate over cities while maintaining deque of min. costs
97 D.clear();
98 D.push_back(mp(0, 0));
99 Fox(i, N)
100 {
101 // remove entries too far back to reach current city
102 while (!D.empty() && D.front().x < i - M)
103 D.pop_front();
104 // impossible to make it this far?
105 if (D.empty())
106 return(-1);
107 // consider refueling here
108 if (C[i])
109 {
110 LL d = D.front().y + C[i];
111 // remove no-longer-relevant entries
112 while (!D.empty() && d <= D.back().y)
113 D.pop_back();
114 D.push_back(mp(i, d));
115 }
116 }
117 return(D.front().y);
118}
119
120int main()
121{
122 int T, t;
123 Read(T);
124 Fox1(t, T)
125 printf("Case #%d: %lld\n", t, ProcessCase());
126 return(0);
127}