Submission #1167860
Source Code Expand
#include<bits/stdc++.h> #define mp make_pair #define PII pair<int,int> #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define ui unsigned int #define sci(x) scanf("%d",&x) #define scs(s) scanf("%s",s) #define scc(c) scanf("%c",c) #define scd(d) scanf("%lf",&d) #define scld(ld) scanf("%Lf",&ld) using namespace std; //******************************************** //Error tracking #define show(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); } vector<string> split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.emplace_back(x); return move(v); } void err(vector<string>::iterator it) {} template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n'; err(++it, args...); } //******************************************** const int NMAX = 5005; int n, k, a[NMAX]; bitset<NMAX>pref[NMAX], suf[NMAX]; int sum[2][NMAX]; void Knapsack() { int i, j; //prefix pref[0][0] = 1; for (i = 1; i <= n; i++) for (j = 0; j < NMAX; j++) { pref[i][j] = pref[i - 1][j]; if (j >= a[i] && pref[i - 1][j - a[i]]) pref[i][j] = 1; } //sufix suf[n + 1][0] = 1; for (i = n ; i >= 1; i--) for (j = 0; j < NMAX; j++) { suf[i][j] = suf[i + 1][j]; if (j >= a[i] && suf[i + 1][j - a[i]]) suf[i][j] = 1; } } int main() { // freopen("input","r",stdin); // freopen("output","w",stdout); cin.sync_with_stdio(false); int i; cin >> n >> k; for (i = 1; i <= n; i++) cin >> a[i]; Knapsack(); //answer int j, ans = 0; for (i = 1; i <= n; i++) { int st = max(0, k - a[i]), dr = k - 1; //the interval to search //partial sums for (j = 0; j < NMAX; j++) { sum[0][j] = pref[i - 1][j]; sum[1][j] = suf[i + 1][j]; } for (j = 1; j < NMAX; j++) for (int l = 0; l <= 1; l++) sum[l][j] += sum[l][j - 1]; bool ok = 0; for (j = 0; j <= dr; j++) if (pref[i - 1][j] != 0) //search for other { int left = max(0, st - j), right = dr - j; int minus = 0; if (left > 0) minus = sum[1][left - 1]; if (sum[1][right] - minus > 0) ok = 1; } if (!ok) ans++; } cout << ans << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - No Need |
User | Archazey |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 2483 Byte |
Status | AC |
Exec Time | 306 ms |
Memory | 6528 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 | 2 ms | 2304 KB |
0_001.txt | AC | 2 ms | 2304 KB |
0_002.txt | AC | 2 ms | 2304 KB |
1_003.txt | AC | 2 ms | 2304 KB |
1_004.txt | AC | 2 ms | 2304 KB |
1_005.txt | AC | 2 ms | 2304 KB |
1_006.txt | AC | 2 ms | 2304 KB |
1_007.txt | AC | 2 ms | 2304 KB |
1_008.txt | AC | 21 ms | 2560 KB |
1_009.txt | AC | 21 ms | 2560 KB |
1_010.txt | AC | 18 ms | 2560 KB |
1_011.txt | AC | 18 ms | 2560 KB |
1_012.txt | AC | 21 ms | 2560 KB |
1_013.txt | AC | 21 ms | 2560 KB |
1_014.txt | AC | 25 ms | 2560 KB |
1_015.txt | AC | 26 ms | 2560 KB |
1_016.txt | AC | 2 ms | 2304 KB |
1_017.txt | AC | 2 ms | 2304 KB |
1_018.txt | AC | 2 ms | 2304 KB |
1_019.txt | AC | 22 ms | 2560 KB |
1_020.txt | AC | 22 ms | 2560 KB |
1_021.txt | AC | 25 ms | 2560 KB |
1_022.txt | AC | 11 ms | 2432 KB |
1_023.txt | AC | 8 ms | 2432 KB |
1_024.txt | AC | 23 ms | 2560 KB |
1_025.txt | AC | 23 ms | 2560 KB |
2_026.txt | AC | 2 ms | 2304 KB |
2_027.txt | AC | 3 ms | 2304 KB |
2_028.txt | AC | 3 ms | 2432 KB |
2_029.txt | AC | 306 ms | 6528 KB |
2_030.txt | AC | 306 ms | 6528 KB |
2_031.txt | AC | 232 ms | 6528 KB |
2_032.txt | AC | 208 ms | 6528 KB |
2_033.txt | AC | 232 ms | 6528 KB |
2_034.txt | AC | 208 ms | 6528 KB |
2_035.txt | AC | 254 ms | 6528 KB |
2_036.txt | AC | 303 ms | 6528 KB |
2_037.txt | AC | 2 ms | 2304 KB |
2_038.txt | AC | 2 ms | 2304 KB |
2_039.txt | AC | 2 ms | 2304 KB |
2_040.txt | AC | 234 ms | 6528 KB |
2_041.txt | AC | 302 ms | 6528 KB |
2_042.txt | AC | 303 ms | 6528 KB |
2_043.txt | AC | 184 ms | 6272 KB |
2_044.txt | AC | 247 ms | 6400 KB |
2_045.txt | AC | 227 ms | 6400 KB |
2_046.txt | AC | 250 ms | 6528 KB |
2_047.txt | AC | 264 ms | 6528 KB |
2_048.txt | AC | 275 ms | 6528 KB |
2_049.txt | AC | 269 ms | 6528 KB |
2_050.txt | AC | 265 ms | 6528 KB |