Submission #1231441
Source Code Expand
#include <algorithm> #include <cmath> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; lli MOD = 1e9 + 7; int main() { //つまり考えるべきことはi以外でもっともSに近いものを作るてその総和+a_iがKを超えれば不必要ではない //これはk>=a_i + S つまり(k-a_i)<=s&&s<kなるsの存在判定 //iで毎回dpすればn^2kで部分点 lli n, k; lli a[100005]; cin >> n >> k; rep(i, n) cin >> a[i]; if (n > 500) return 0; int cnt = 0; int u = n; int l = 0; while (u - l > 1) { int i = (u + l) / 2; bool dp[410][510] = {}; dp[0][0] = true; rep(j, n) rep(l, k) { if (dp[j][l]) dp[j + 1][l] = true; if (i == j) continue; if (dp[j][l] && a[j] + l < k) { dp[j + 1][a[j] + l] = true; } } rrep(l, k) { if (dp[n][l]) { if (l + a[i] >= k) { u = i; break; } } } l = i; } cout << u << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - Go Home |
User | uenoku |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1410 Byte |
Status | WA |
Exec Time | 2103 ms |
Memory | 512 KB |
Judge Result
Set Name | Sample | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | ||||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | WA | 1 ms | 512 KB |
0_001.txt | AC | 1 ms | 512 KB |
0_002.txt | WA | 1 ms | 512 KB |
1_003.txt | TLE | 2103 ms | 256 KB |
1_004.txt | TLE | 2103 ms | 256 KB |
1_005.txt | AC | 1 ms | 256 KB |
1_006.txt | TLE | 2103 ms | 256 KB |
1_007.txt | TLE | 2103 ms | 256 KB |
1_008.txt | TLE | 2103 ms | 256 KB |
1_009.txt | TLE | 2103 ms | 256 KB |
1_010.txt | TLE | 2103 ms | 256 KB |
1_011.txt | TLE | 2103 ms | 256 KB |
1_012.txt | TLE | 2103 ms | 256 KB |
1_013.txt | TLE | 2103 ms | 256 KB |
1_014.txt | TLE | 2103 ms | 256 KB |
1_015.txt | TLE | 2103 ms | 256 KB |
1_016.txt | TLE | 2103 ms | 256 KB |
1_017.txt | TLE | 2103 ms | 256 KB |