Submission #2374364
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define mmax(x,y) (x>y?x:y) #define mmin(x,y) (x<y?x:y) #define maxch(x,y) x=mmax(x,y) #define minch(x,y) x=mmin(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt __builtin_popcount #define INF 1e16 #define mod 1000000007 ll n,D,q; ll d[500001]; ll pre[500001]; ll dp[500001]; int main(){ cin>>n>>D; rep(i,n)cin>>d[i]; dp[n]=1; for(ll i=n-1;i>=0;i--){ if(dp[i+1]<=d[i]/2){ dp[i]=dp[i+1]; }else{ dp[i]=dp[i+1]+d[i]; } } rep(i,n){ pre[i]=D; if(d[i]<=D){ D-=d[i]; }else if(d[i]<=2*D){ D=d[i]-D; } } cin>>q; while(q--){ ll t; cin>>t; t--; if(pre[t]<dp[t+1]){ cout<<"NO"<<endl; }else{ cout<<"YES"<<endl; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Alice in linear land |
User | yamad |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 1168 Byte |
Status | AC |
Exec Time | 1113 ms |
Memory | 13696 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
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 | 2 ms | 4352 KB |
00-01.txt | AC | 2 ms | 4352 KB |
00-02.txt | AC | 2 ms | 4352 KB |
01-00.txt | AC | 2 ms | 4352 KB |
01-01.txt | AC | 2 ms | 4352 KB |
01-02.txt | AC | 1113 ms | 13568 KB |
01-03.txt | AC | 1103 ms | 13568 KB |
01-04.txt | AC | 1072 ms | 13568 KB |
01-05.txt | AC | 1092 ms | 13568 KB |
01-06.txt | AC | 1085 ms | 13696 KB |
01-07.txt | AC | 1098 ms | 13696 KB |
01-08.txt | AC | 1078 ms | 13440 KB |
01-09.txt | AC | 1072 ms | 13440 KB |
01-10.txt | AC | 1072 ms | 13440 KB |