Submission #1294682
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<bool> tree;
void init() {
tree = vector<bool>(4*K, false);
}
void upd(int idx, bool 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];
}
bool quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return false;
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 |
2007 Byte |
Status |
TLE |
Exec Time |
2119 ms |
Memory |
204672 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 |
256 KB |
1_007.txt |
AC |
2 ms |
256 KB |
1_008.txt |
AC |
15 ms |
1664 KB |
1_009.txt |
AC |
16 ms |
1664 KB |
1_010.txt |
AC |
10 ms |
1664 KB |
1_011.txt |
AC |
1 ms |
384 KB |
1_012.txt |
AC |
10 ms |
1664 KB |
1_013.txt |
AC |
1 ms |
384 KB |
1_014.txt |
AC |
1 ms |
384 KB |
1_015.txt |
AC |
12 ms |
1664 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 |
7 ms |
1152 KB |
1_020.txt |
AC |
1 ms |
384 KB |
1_021.txt |
AC |
5 ms |
896 KB |
1_022.txt |
AC |
3 ms |
512 KB |
1_023.txt |
AC |
1 ms |
384 KB |
1_024.txt |
AC |
7 ms |
1024 KB |
1_025.txt |
AC |
10 ms |
1280 KB |
2_026.txt |
AC |
2 ms |
256 KB |
2_027.txt |
AC |
3 ms |
384 KB |
2_028.txt |
AC |
3 ms |
384 KB |
2_029.txt |
TLE |
2118 ms |
203904 KB |
2_030.txt |
TLE |
2119 ms |
203776 KB |
2_031.txt |
TLE |
2118 ms |
204672 KB |
2_032.txt |
AC |
3 ms |
1408 KB |
2_033.txt |
TLE |
2118 ms |
204672 KB |
2_034.txt |
AC |
3 ms |
1408 KB |
2_035.txt |
AC |
3 ms |
1408 KB |
2_036.txt |
TLE |
2118 ms |
203136 KB |
2_037.txt |
AC |
6 ms |
640 KB |
2_038.txt |
AC |
7 ms |
640 KB |
2_039.txt |
AC |
7 ms |
640 KB |
2_040.txt |
TLE |
2116 ms |
170240 KB |
2_041.txt |
AC |
1621 ms |
109440 KB |
2_042.txt |
TLE |
2116 ms |
165504 KB |
2_043.txt |
AC |
1731 ms |
101376 KB |
2_044.txt |
AC |
1879 ms |
111488 KB |
2_045.txt |
AC |
861 ms |
55936 KB |
2_046.txt |
AC |
1594 ms |
103680 KB |
2_047.txt |
TLE |
2116 ms |
158208 KB |
2_048.txt |
TLE |
2118 ms |
200320 KB |
2_049.txt |
TLE |
2118 ms |
200320 KB |
2_050.txt |
TLE |
2119 ms |
200448 KB |