Submission #1231431


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;
    rep(i, n)
    {

        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) {
                    cnt++;
                    break;
                }
            }
        }
    }
    cout << n - cnt << endl;
}

Submission Info

Submission Time
Task D - No Need
User uenoku
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1337 Byte
Status WA
Exec Time 112 ms
Memory 512 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 300 / 300 0 / 300
Status
AC × 3
AC × 26
AC × 29
WA × 22
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 512 KB
0_001.txt AC 1 ms 512 KB
0_002.txt AC 1 ms 512 KB
1_003.txt AC 1 ms 512 KB
1_004.txt AC 1 ms 512 KB
1_005.txt AC 1 ms 512 KB
1_006.txt AC 1 ms 512 KB
1_007.txt AC 1 ms 512 KB
1_008.txt AC 81 ms 512 KB
1_009.txt AC 80 ms 512 KB
1_010.txt AC 49 ms 512 KB
1_011.txt AC 5 ms 512 KB
1_012.txt AC 49 ms 512 KB
1_013.txt AC 5 ms 512 KB
1_014.txt AC 4 ms 512 KB
1_015.txt AC 112 ms 512 KB
1_016.txt AC 1 ms 512 KB
1_017.txt AC 1 ms 512 KB
1_018.txt AC 1 ms 512 KB
1_019.txt AC 44 ms 512 KB
1_020.txt AC 6 ms 512 KB
1_021.txt AC 54 ms 512 KB
1_022.txt AC 13 ms 512 KB
1_023.txt AC 4 ms 512 KB
1_024.txt AC 46 ms 512 KB
1_025.txt AC 61 ms 512 KB
2_026.txt AC 1 ms 512 KB
2_027.txt WA 2 ms 512 KB
2_028.txt AC 2 ms 512 KB
2_029.txt WA 2 ms 256 KB
2_030.txt WA 2 ms 256 KB
2_031.txt WA 3 ms 256 KB
2_032.txt WA 3 ms 256 KB
2_033.txt WA 2 ms 256 KB
2_034.txt WA 2 ms 256 KB
2_035.txt WA 2 ms 256 KB
2_036.txt WA 2 ms 256 KB
2_037.txt WA 2 ms 384 KB
2_038.txt AC 2 ms 512 KB
2_039.txt WA 2 ms 512 KB
2_040.txt WA 2 ms 256 KB
2_041.txt WA 2 ms 256 KB
2_042.txt WA 2 ms 256 KB
2_043.txt WA 2 ms 256 KB
2_044.txt WA 2 ms 256 KB
2_045.txt WA 2 ms 256 KB
2_046.txt WA 2 ms 256 KB
2_047.txt WA 2 ms 256 KB
2_048.txt WA 2 ms 256 KB
2_049.txt WA 2 ms 256 KB
2_050.txt WA 2 ms 256 KB