Submission #7432517
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
out<<'[';
for(const T &i: a) out<<i<<',';
out<<']';
return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
out<<'{';
for(const T &i: a) out<<i<<',';
out<<'}';
return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
out<<'{';
for(auto &i: a) out<<i<<',';
out<<'}';
return out;
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
signed main(void)
{
cin.tie(0);
ios::sync_with_stdio(false);
ll n;
cin >> n;
vector<ll> a(n);
REP(i, n-1) cin >> a[i];
ll sum = 0;
FOR(i, 2, n-1) sum += a[i];
deque<ll> dp(sum+1);
REP(i, sum+1) dp[i] = i;
FOR(i, 2, n-1) {
// dp[1]~dp[a[i]] を逆順にしてpush
vector<ll> v;
REP(j, a[i]) v.push_back(dp[j+1]);
REP(j, a[i]) dp.push_front(v[j]);
}
ll q;
cin >> q;
while(q--) {
ll x;
cin >> x;
if(sum <= x) {
cout << x-sum+a[0]-a[1] << endl;
} else {
cout << dp[x]+a[0]-a[1] << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
H - Tokaido |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2484 Byte |
Status |
AC |
Exec Time |
417 ms |
Memory |
25964 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
700 / 700 |
900 / 900 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
dataset1 |
sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt |
dataset2 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
58 ms |
18248 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
AC |
19 ms |
16840 KB |
01-04.txt |
AC |
44 ms |
17352 KB |
01-05.txt |
AC |
58 ms |
18248 KB |
01-06.txt |
AC |
59 ms |
18248 KB |
01-07.txt |
AC |
36 ms |
17096 KB |
01-08.txt |
AC |
56 ms |
18248 KB |
01-09.txt |
AC |
57 ms |
18248 KB |
01-10.txt |
AC |
21 ms |
20660 KB |
01-11.txt |
AC |
25 ms |
24160 KB |
01-12.txt |
AC |
41 ms |
23172 KB |
01-13.txt |
AC |
42 ms |
22600 KB |
01-14.txt |
AC |
42 ms |
25652 KB |
01-15.txt |
AC |
41 ms |
24372 KB |
01-16.txt |
AC |
33 ms |
25964 KB |
01-17.txt |
AC |
14 ms |
1792 KB |
01-18.txt |
AC |
14 ms |
1792 KB |
01-19.txt |
AC |
13 ms |
1792 KB |
02-01.txt |
AC |
71 ms |
17096 KB |
02-02.txt |
AC |
396 ms |
20168 KB |
02-03.txt |
AC |
394 ms |
18632 KB |
02-04.txt |
AC |
394 ms |
18632 KB |
02-05.txt |
AC |
355 ms |
17480 KB |
02-06.txt |
AC |
401 ms |
18632 KB |
02-07.txt |
AC |
417 ms |
18760 KB |
02-08.txt |
AC |
358 ms |
21912 KB |
02-09.txt |
AC |
356 ms |
21736 KB |
02-10.txt |
AC |
372 ms |
24760 KB |
02-11.txt |
AC |
399 ms |
22448 KB |
02-12.txt |
AC |
393 ms |
23736 KB |
02-13.txt |
AC |
378 ms |
24752 KB |
02-14.txt |
AC |
368 ms |
25964 KB |
02-15.txt |
AC |
345 ms |
3328 KB |
02-16.txt |
AC |
349 ms |
3328 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |