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
AC × 2
AC × 20
AC × 39
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