Submission #1168357
Source Code Expand
//{{{
#include <bits/stdc++.h>
using namespace std;
//types
typedef long long ll;
typedef pair<int,int> pii;
//input
bool SR(int &_x){return scanf("%d",&_x)==1;}bool SR(ll &_x){return scanf("%lld",&_x)==1;}
bool SR(double &_x){return scanf("%lf",&_x)==1;}bool SR(char *_s){return scanf("%s",_s)==1;}
bool RI(){return true;}
template<typename I,typename... T>bool RI(I &_x,T&... _tail){return SR(_x) && RI(_tail...);}
//output
void SP(const int _x){printf("%d",_x);}void SP(const ll _x){printf("%lld",_x);}
void SP(const double _x){printf("%.16lf",_x);}void SP(const char *s){printf("%s",s);}
void PL(){puts("");}
template<typename I,typename... T>void PL(const I _x,const T... _tail)
{SP(_x);if(sizeof...(_tail)) putchar(' ');PL(_tail...);}
//macro
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<int(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=int(b);i++)
#define PER1(i,a,b) for(int i=(a);i>=int(b);i--)
#define pb push_back
#define mkp make_pair
#define F first
#define S second
//debug
#ifdef darry140
template<typename A,typename B>
ostream& operator <<(ostream&_s, const pair<A,B> &_p){return _s<<"("<<_p.F<<","<<_p.S<<")";}
template<typename It>
ostream& _OUTC(ostream &_s,It _b,It _e)//container
{
_s<<"{";
for(auto _it=_b;_it!=_e;_it++) _s<<(_it==_b?"":" ")<<*_it;
_s<<"}";
return _s;
}
template<typename A,typename B>
ostream& operator <<(ostream&_s, const map<A,B> &_c){return _OUTC(_s,ALL(_c));}
template<typename T>
ostream& operator <<(ostream&_s, const set<T> &_c){return _OUTC(_s,ALL(_c));}
template<typename T>
ostream& operator <<(ostream&_s, const vector<T> &_c){return _OUTC(_s,ALL(_c));}
template<typename I>
void _DOING(const char *_s,I&& _x){cerr<<_s<<"="<<_x<<endl;}//without ','
template<typename I,typename... T>
void _DOING(const char *_s,I&& _x,T&&... _tail)//with ','
{
int _c=0;
static const char _bra[]="({[";
static const char _ket[]=")}]";
while(*_s!=',' || _c!=0)//eg. mkp(a,b)
{
if(strchr(_bra,*_s)) _c++;
if(strchr(_ket,*_s)) _c--;
cerr<<*_s++;
}
cerr<<"="<<_x<<", ";
_DOING(_s+1,_tail...);
}
#define debug(...) do{\
fprintf(stderr,"%s:%d - ",__PRETTY_FUNCTION__,__LINE__);\
_DOING(#__VA_ARGS__,__VA_ARGS__);\
}while(0)
#else
#define debug(...)
#endif
//}}}
const int maxn=5e3+3;
//bool dpl[maxn][maxn],dpr[maxn][maxn];
int a[maxn],n,k;
void read()
{
RI(n,k);
REP1(i,1,n) RI(a[i]);
}
int tl[maxn],tr[maxn];
void build()
{
REP1(i,1,n) a[i]=min(a[i],k);
//dpl[0][0]=1;
memset(tl,0x3f,sizeof(int)*maxn);
tl[0]=0;
REP1(i,1,n)
{
//memcpy(dpl[i-1],dpl[i],sizeof(bool)*maxn);
for(int j=maxn-1;j>=a[i];j--)
tl[j]=min(tl[j],max(tl[j-a[i]],i));
}
//dpr[n+1][0]=1;
tr[0]=n+1;
PER1(i,n,1)
{
//memcpy(dpr[i+1],dpr[i],sizeof(bool)*maxn);
for(int j=maxn-1;j>=a[i];j--)//dpr[i][j]|=dpr[i+1][j-a[i]];
tr[j]=max(tr[j],min(tr[j-a[i]],i));
}
}
void sol()
{
int ans=0;
REP1(i,1,n)
{
bool exist=0;
vector<int> sum(maxn);
REP(j,maxn) sum[j]=(tr[j]>i);
REP1(j,1,maxn-1) sum[j]+=sum[j-1];
REP1(x,0,k-1)
{
int l=max((k-a[i])-x,0);
int r=(k-1)-x;
debug(i,a[i],x,l,r);
if(tl[x]<i && sum[r]-(l-1>=0?sum[l-1]:0))
{exist=1;break;}
}
debug(i,a[i],exist);
if(!exist) ans++;
}
PL(ans);
}
int main()
{
read();
build();
sol();
return 0;
}
/*End Of File*/
Submission Info
Submission Time |
|
Task |
D - No Need |
User |
darry140 |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
3774 Byte |
Status |
AC |
Exec Time |
178 ms |
Memory |
384 KB |
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
300 / 300 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
Subtask |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
1 ms |
256 KB |
0_001.txt |
AC |
1 ms |
256 KB |
0_002.txt |
AC |
1 ms |
256 KB |
1_003.txt |
AC |
1 ms |
256 KB |
1_004.txt |
AC |
1 ms |
256 KB |
1_005.txt |
AC |
1 ms |
256 KB |
1_006.txt |
AC |
2 ms |
256 KB |
1_007.txt |
AC |
2 ms |
256 KB |
1_008.txt |
AC |
13 ms |
256 KB |
1_009.txt |
AC |
14 ms |
256 KB |
1_010.txt |
AC |
13 ms |
256 KB |
1_011.txt |
AC |
13 ms |
256 KB |
1_012.txt |
AC |
13 ms |
256 KB |
1_013.txt |
AC |
13 ms |
256 KB |
1_014.txt |
AC |
13 ms |
256 KB |
1_015.txt |
AC |
14 ms |
256 KB |
1_016.txt |
AC |
1 ms |
256 KB |
1_017.txt |
AC |
2 ms |
256 KB |
1_018.txt |
AC |
2 ms |
256 KB |
1_019.txt |
AC |
14 ms |
384 KB |
1_020.txt |
AC |
13 ms |
256 KB |
1_021.txt |
AC |
14 ms |
256 KB |
1_022.txt |
AC |
7 ms |
256 KB |
1_023.txt |
AC |
5 ms |
256 KB |
1_024.txt |
AC |
14 ms |
256 KB |
1_025.txt |
AC |
14 ms |
256 KB |
2_026.txt |
AC |
1 ms |
256 KB |
2_027.txt |
AC |
2 ms |
256 KB |
2_028.txt |
AC |
2 ms |
256 KB |
2_029.txt |
AC |
170 ms |
384 KB |
2_030.txt |
AC |
178 ms |
256 KB |
2_031.txt |
AC |
88 ms |
256 KB |
2_032.txt |
AC |
153 ms |
384 KB |
2_033.txt |
AC |
87 ms |
256 KB |
2_034.txt |
AC |
151 ms |
256 KB |
2_035.txt |
AC |
150 ms |
384 KB |
2_036.txt |
AC |
122 ms |
256 KB |
2_037.txt |
AC |
2 ms |
256 KB |
2_038.txt |
AC |
2 ms |
256 KB |
2_039.txt |
AC |
2 ms |
256 KB |
2_040.txt |
AC |
102 ms |
256 KB |
2_041.txt |
AC |
138 ms |
384 KB |
2_042.txt |
AC |
128 ms |
256 KB |
2_043.txt |
AC |
80 ms |
256 KB |
2_044.txt |
AC |
112 ms |
256 KB |
2_045.txt |
AC |
117 ms |
256 KB |
2_046.txt |
AC |
145 ms |
256 KB |
2_047.txt |
AC |
140 ms |
256 KB |
2_048.txt |
AC |
135 ms |
256 KB |
2_049.txt |
AC |
126 ms |
256 KB |
2_050.txt |
AC |
120 ms |
256 KB |