Submission #2827372


Source Code Expand

    #include "bits/stdc++.h"
    using namespace std;
     
    #define DEBUG(x) cout<<#x<<": "<<x<<endl;
    #define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
     
     
    typedef long long ll;
    #define vi vector<int>
    #define vl vector<ll>
    #define vii vector< vector<int> >
    #define vll vector< vector<ll> >
    #define vs vector<string>
    #define pii pair<int,int>
    #define pis pair<int,string>
    #define psi pair<string,int>
    #define pll pair<ll,ll>
    template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
    template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
    template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
    #define X first
    #define Y second
    #define rep(i,n) for(ll i=0;i<(ll)(n);i++)
    #define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
    #define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
    #define rrep1(i,n) for(ll i=(ll)(n);i>0;i--)
    #define REP(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
    #define in(x, a, b) (a <= x && x < b)
    #define all(v) v.begin(),v.end()
    #define UNIQUE(v) v.erase(unique(all(v)), v.end())
    template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
    template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
    const ll inf = 1000000001;
    const ll INF = 2e18;
    const ll MOD = 1000000007;
    const double pi = 3.14159265358979323846;
    #define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
    int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
    int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
    #define fio() cin.tie(0); ios::sync_with_stdio(false);
    #define mp make_pair
     
     
    int main() {
    	ll n, x0;
    	cin >> n >> x0;
    	vl d(n);
    	rep(i, n) {
    		cin >> d[i];
    	}
    	int q;
    	cin >> q;
    	vi idx(q);
    	rep(i, q) {
    		cin >> idx[i];
    	}
    	vl x(n + 1);
    	x[0] = x0;
    	rep(i, n) {
    		x[i + 1] = min(x[i], abs(x[i] - d[i]));
    	}
    	bool flag = true;
    	vl ng(n, 0);
    	rep(i, n) {
    		if (!flag) {
    			ng[i] = INF;
    			x.pop_back();
    		}
    		else if (x[i + 1] == 0) {
    			flag = false;
    		}
    	}
    	if (flag) {
    		rep(i, q) {
    			cout << "YES" << endl;
    		}
    		return 0;
    	}
    	n = x.size() - 1;
    	ng[n - 1] = 1;
    	//DEBUG(n);
    	//DEBUG_VEC(x);
    	//DEBUG_VEC(ng);
    	for (int i = n - 2; i >= 0; i--) {
    		if (d[i + 1] / 2 < ng[i + 1]) {
    			ng[i] = d[i + 1] + ng[i + 1];
    		}
    		else {
    			ng[i] = ng[i + 1];
    		}
    	}
    	//DEBUG_VEC(ng);
    	rep(i, q) {
    		int j = idx[i] - 1;
          if (j >= x.size()) {
            cout << "NO" << endl;
            continue;
          }
    		if (ng[j] <= x[j]) {
    			cout << "YES" << endl;
    		}
    		else {
    			cout << "NO" << endl;
    		}
    	}
    }

Submission Info

Submission Time
Task E - Alice in linear land
User fuppy0716
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3272 Byte
Status WA
Exec Time 1076 ms
Memory 15872 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 11
WA × 3
Set Name Test Cases
Sample 00-00.txt, 00-01.txt, 00-02.txt
All 00-00.txt, 00-01.txt, 00-02.txt, 01-00.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
Case Name Status Exec Time Memory
00-00.txt AC 1 ms 256 KB
00-01.txt AC 1 ms 256 KB
00-02.txt AC 1 ms 256 KB
01-00.txt AC 1 ms 256 KB
01-01.txt WA 1 ms 256 KB
01-02.txt AC 1073 ms 15616 KB
01-03.txt AC 1045 ms 15488 KB
01-04.txt AC 1048 ms 15616 KB
01-05.txt WA 1041 ms 15872 KB
01-06.txt AC 1075 ms 15616 KB
01-07.txt AC 1076 ms 15616 KB
01-08.txt WA 1051 ms 15360 KB
01-09.txt AC 1070 ms 15360 KB
01-10.txt AC 1051 ms 15360 KB