Submission #1294676
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
int N, K;
vector<int> arr;
vector<vector<int> > ccp;
int dpp(int n, int k) {
if(n == -1) return k == 0;
int &ret = ccp[n][k];
if(ret != -1) return ret;
return ret = (arr[n] <= k && dpp(n - 1, k - arr[n])) | dpp(n - 1, k);
}
vector<vector<int> > ccs;
int dps(int n, int k) {
if(n == N) return k == 0;
int &ret = ccs[n][k];
if(ret != -1) return ret;
return ret = (arr[n] <= k && dps(n + 1, k - arr[n])) | dps(n + 1, k);
}
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4*K, 0);
}
void upd(int idx, int val, int l, int r, int n) {
if(idx < l || r < idx) return;
if(l == r) {
tree[n] = val;
return;
}
int m = (l + r)>>1;
upd(idx, val, l, m, 2*n);
upd(idx, val, m + 1, r, 2*n + 1);
tree[n] = tree[2*n] | tree[2*n + 1];
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return 0;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return L | R;
}
};
vector<BIT> B;
int main() {
scanf("%d %d", &N, &K);
arr.resize(N);
for(int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
ccp = ccs = vector<vector<int> >(N, vector<int>(K, -1));
B.resize(N);
for(int i = 0; i < N; i++) {
B[i].init();
for(int j = 0; j < K; j++) B[i].upd(j, dps(i, j), 0, K - 1, 1);
}
int cnt = N;
for(int i = 0; i < N; i++) {
int lb = max(0, K - arr[i]);
for(int j = 0; j < K; j++) {
if(j == 0 || (i != 0 && dpp(i - 1, j))) if(max(0, lb - j) == 0 || (i != N - 1 && B[i + 1].quer(lb - j, K - 1 - j, 0, K - 1, 1))) {
cnt--;
break;
}
}
}
printf("%d", cnt);
}
Submission Info
Submission Time |
|
Task |
D - No Need |
User |
choikiwon |
Language |
C++14 (GCC 5.4.1) |
Score |
300 |
Code Size |
1995 Byte |
Status |
TLE |
Exec Time |
2141 ms |
Memory |
515328 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:51:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &K);
^
./Main.cpp:54:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i]);
^
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
0 / 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 |
384 KB |
1_007.txt |
AC |
2 ms |
384 KB |
1_008.txt |
AC |
13 ms |
4096 KB |
1_009.txt |
AC |
14 ms |
4096 KB |
1_010.txt |
AC |
8 ms |
4096 KB |
1_011.txt |
AC |
1 ms |
384 KB |
1_012.txt |
AC |
8 ms |
4096 KB |
1_013.txt |
AC |
1 ms |
384 KB |
1_014.txt |
AC |
1 ms |
384 KB |
1_015.txt |
AC |
10 ms |
4096 KB |
1_016.txt |
AC |
1 ms |
256 KB |
1_017.txt |
AC |
1 ms |
256 KB |
1_018.txt |
AC |
1 ms |
256 KB |
1_019.txt |
AC |
6 ms |
2688 KB |
1_020.txt |
AC |
1 ms |
384 KB |
1_021.txt |
AC |
5 ms |
2048 KB |
1_022.txt |
AC |
3 ms |
1024 KB |
1_023.txt |
AC |
1 ms |
384 KB |
1_024.txt |
AC |
6 ms |
2304 KB |
1_025.txt |
AC |
9 ms |
3072 KB |
2_026.txt |
AC |
2 ms |
384 KB |
2_027.txt |
AC |
3 ms |
640 KB |
2_028.txt |
AC |
3 ms |
640 KB |
2_029.txt |
TLE |
2137 ms |
498304 KB |
2_030.txt |
TLE |
2140 ms |
497152 KB |
2_031.txt |
TLE |
2138 ms |
515328 KB |
2_032.txt |
AC |
3 ms |
1280 KB |
2_033.txt |
TLE |
2140 ms |
514944 KB |
2_034.txt |
AC |
3 ms |
1280 KB |
2_035.txt |
AC |
3 ms |
1280 KB |
2_036.txt |
TLE |
2135 ms |
472448 KB |
2_037.txt |
AC |
6 ms |
1408 KB |
2_038.txt |
AC |
6 ms |
1536 KB |
2_039.txt |
AC |
6 ms |
1536 KB |
2_040.txt |
TLE |
2136 ms |
481152 KB |
2_041.txt |
MLE |
1418 ms |
306816 KB |
2_042.txt |
TLE |
2072 ms |
471424 KB |
2_043.txt |
MLE |
1532 ms |
284928 KB |
2_044.txt |
MLE |
1673 ms |
312832 KB |
2_045.txt |
AC |
764 ms |
155904 KB |
2_046.txt |
MLE |
1429 ms |
290944 KB |
2_047.txt |
TLE |
2134 ms |
444672 KB |
2_048.txt |
TLE |
2140 ms |
507264 KB |
2_049.txt |
TLE |
2141 ms |
509824 KB |
2_050.txt |
TLE |
2141 ms |
509568 KB |