Submission #9589333
Source Code Expand
#pragma GCC optimize ("O3")
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <set>
#include <algorithm>
#include <numeric>
#include <list>
using namespace std;
using QWORD = uint64_t;
using SQWORD = int64_t;
using DWORD = uint32_t;
using SDWORD = int32_t;
using WORD = uint16_t;
using SWORD = int16_t;
using BYTE = uint8_t;
using SBYTE = int8_t;
using DOUBLE = double;
using FLOAT = float;
#define MIN_SDWORD (-2147483648)
#define MAX_SDWORD (2147483647)
#define MIN_SBYTE (-128)
#define MAX_SBYTE (127)
#define MIN_SQWORD (0x8000000000000000)
#define MAX_SQWORD (0x7FFFFFFFFFFFFFFF)
#define MAX_QWORD (0xFFFFFFFFFFFFFFFF)
#define MAX_DWORD (0xFFFFFFFF)
#define MAX_WORD (0xFFFF)
#define MAX_BYTE (0xFF)
#define MAX_DOUBLE (1.0e+308)
#define DOUBLE_EPS (1.0e-12)
#define MIN_DOUBLE_N (-1.0e+308)
#define ArrayLength(a) (sizeof(a) / sizeof(a[0]))
static inline DOUBLE MAX(DOUBLE a, DOUBLE b) { return a > b ? a : b; }
static inline QWORD MAX(QWORD a, QWORD b) { return a > b ? a : b; }
static inline DWORD MAX(DWORD a, DWORD b) { return a > b ? a : b; }
static inline SDWORD MAX(SDWORD a, SDWORD b) { return a > b ? a : b; }
static inline DOUBLE MIN(DOUBLE a, DOUBLE b) { return a < b ? a : b; }
static inline QWORD MIN(QWORD a, QWORD b) { return a < b ? a : b; }
static inline DWORD MIN(DWORD a, DWORD b) { return a < b ? a : b; }
static inline SDWORD MIN(SDWORD a, SDWORD b) { return a < b ? a : b; }
#define BYTE_BITS (8)
#define WORD_BITS (16)
#define DWORD_BITS (32)
#define QWORD_BITS (64)
static inline void inputStringSpSeparated(char *pcStr)
{
char *pcCur = pcStr;
for (;;) {
char c = getchar();
if (('\n' == c) || (EOF == c) || (' ' == c)) {
break;
}
*pcCur = c;
pcCur++;
}
*pcCur = '\0';
}
static inline void inputString(char *pcStr)
{
char *pcCur = pcStr;
for (;;) {
char c = getchar();
if (('\n' == c) || (EOF == c)) {
break;
}
*pcCur = c;
pcCur++;
}
*pcCur = '\0';
}
static inline SQWORD inputSQWORD(void)
{
SQWORD sqNumber = 0;
SQWORD sqMultiplier = 1;
bool bRead = false;
for (;;) {
char c = getchar();
if (!bRead) {
if ('-' == c) {
sqMultiplier = -1;
}
}
if (('0' <= c) && (c <= '9')) {
sqNumber *= 10LL;
sqNumber += (SQWORD)(c - '0');
bRead = true;
} else {
if (bRead) {
return sqNumber * sqMultiplier;
}
}
}
}
static inline SDWORD inputSDWORD(void)
{
SDWORD lNumber = 0;
SDWORD lMultiplier = 1;
bool bRead = false;
for (;;) {
char c = getchar();
if (!bRead) {
if ('-' == c) {
lMultiplier = -1;
}
}
if (('0' <= c) && (c <= '9')) {
lNumber *= 10;
lNumber += (c - '0');
bRead = true;
} else {
if (bRead) {
return lNumber * lMultiplier;
}
}
}
}
static inline DOUBLE inputFP(void)
{
DOUBLE dInt = 0.0;
DOUBLE dFrac = 0.0;
DOUBLE dMultiplier = 1.0;
DWORD dwFpCnt = 0;
DOUBLE *pdCur = &dInt;
bool bRead = false;
for (;;) {
char c = getchar();
if (!bRead) {
if ('-' == c) {
dMultiplier = -1;
}
}
if ('.' == c) {
pdCur = &dFrac;
} else if (('0' <= c) && (c <= '9')) {
(*pdCur) *= 10;
(*pdCur) += (DOUBLE)(c - '0');
bRead = true;
if (pdCur == &dFrac) {
dwFpCnt++;
}
} else {
if (bRead) {
return dMultiplier * (dInt + dFrac / (pow((DOUBLE)10.0 , (DOUBLE)dwFpCnt)));
}
}
}
}
/*----------------------------------------------*/
/**
* mod による操作ライブラリ
*/
#define ANS_MOD (1000000007)
class MODINT {
static SQWORD MOD;
SQWORD m_x;
public:
MODINT(SQWORD val) {
m_x = (val % MOD + MOD) % MOD;
};
MODINT() {
m_x = 0;
}
static void Init(SQWORD sqMod) {
MOD = sqMod;
}
MODINT& operator+= (const MODINT a)
{
m_x = (m_x + a.m_x) % MOD;
return *this;
};
MODINT& operator-= (const MODINT a)
{
m_x = (m_x - a.m_x + MOD) % MOD;
return *this;
};
MODINT& operator*= (const MODINT a)
{
m_x = (m_x * a.m_x) % MOD;
return *this;
};
MODINT pow(SQWORD t) const {
if (!t) return 1;
MODINT a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
MODINT operator+ (const MODINT a) const {
MODINT res(*this);
return (res += a);
}
MODINT operator- (const MODINT a) const {
MODINT res(*this);
return (res -= a);
}
MODINT operator* (const MODINT a) const {
MODINT res(*this);
return (res *= a);
}
MODINT operator/ (const MODINT a) const {
MODINT res(*this);
return (res /= a);
}
/* 逆元 */
MODINT inv() const {
return pow(MOD-2);
}
/* 除算 */
MODINT& operator/=(const MODINT a) {
return (*this) *= a.inv();
}
/* 整数版 */
MODINT& operator+= (const SQWORD a) {*this += MODINT(a); return *this;};
MODINT& operator-= (const SQWORD a) {*this -= MODINT(a); return *this;};
MODINT& operator*= (const SQWORD a) {*this *= MODINT(a); return *this;};
MODINT& operator/= (const SQWORD a) {*this /= MODINT(a); return *this;};
SQWORD getVal() { return m_x; };
};
SQWORD MODINT::MOD = ANS_MOD;
/*----------------------------------------------*/
static void printVector(vector<SQWORD> vec)
{
for (SQWORD sqIdx = 0; sqIdx < vec.size(); sqIdx++) {
printf("%lld ", vec[sqIdx]);
}
printf("\n");
}
static bool isNeeded(
const vector<SQWORD> &vsqA,
SQWORD sqTestIdx,
SQWORD sqK)
{
vector<SQWORD> vsqDp(sqK, 0);
// printf("-- test: %lld\n", vsqA[sqTestIdx]);
if (sqK <= vsqA[sqTestIdx]) {
return true;
}
vsqDp[0] = 1;
for (SQWORD sqCardIdx = 0; sqCardIdx < vsqA.size(); sqCardIdx++) {
if (sqCardIdx != sqTestIdx) {
for (SQWORD sqDpIdx = vsqDp.size() - 1; 0 <= sqDpIdx; sqDpIdx--) {
SQWORD sqNextIdx = sqDpIdx + vsqA[sqCardIdx];
if (sqNextIdx < sqK) {
vsqDp[sqNextIdx] += vsqDp[sqDpIdx];
// printf("|>> %lld %lld %lld\n", sqK, vsqA[sqTestIdx], sqNextIdx);
if ((0 < vsqDp[sqDpIdx]) && (sqK - vsqA[sqTestIdx] <= sqNextIdx)) {
return true;
}
}
}
}
}
return false;
}
int solverOld(SQWORD sqN, SQWORD sqK, const vector<SQWORD> &vsqA)
{
SQWORD sqAns = 0;
for (SQWORD sqTestIdx = 0; sqTestIdx < vsqA.size(); sqTestIdx++) {
if (!isNeeded(vsqA, sqTestIdx, sqK)) {
sqAns++;
}
}
printf("%lld\n", sqAns);
return 0;
}
/*----------------------------------------------*/
static SQWORD countNeedCards(
const vector<SQWORD> &vsqA,
SQWORD sqK)
{
/* dp(i)[j] i枚目までを考慮したとき、合計がjになるような場合の数 */
vector<SQWORD> vsqDp(sqK, 0);
vsqDp[0] = 1;
for (SQWORD sqCardIdx = 0; sqCardIdx < vsqA.size(); sqCardIdx++) {
for (SQWORD sqDpIdx = vsqDp.size() - 1; 0 <= sqDpIdx; sqDpIdx--) {
SQWORD sqNextIdx = sqDpIdx + vsqA[sqCardIdx];
if (sqNextIdx < sqK) {
vsqDp[sqNextIdx] += vsqDp[sqDpIdx];
}
}
}
#if 0
printf("DP\n");
printVector(vsqDp);
#endif
/* k番目のカードがない場合の逆算をする
* dp(k+1)[j] = dp(k)[j] + dp(k)[j-A[k+1]]
* dp(k)[j] = dp(k+1)[j] - dp(k)[j-A[k+1]]
*/
SQWORD sqAns = 0;
for (SQWORD sqTestIdx = 0; sqTestIdx < vsqA.size(); sqTestIdx++) {
vector<SQWORD> vsqDp2(sqK, 0);
for (SQWORD sqDp2Idx = 0; sqDp2Idx < vsqDp2.size(); sqDp2Idx++) {
if (sqDp2Idx < vsqA[sqTestIdx]) {
vsqDp2[sqDp2Idx] = vsqDp[sqDp2Idx];
} else {
vsqDp2[sqDp2Idx] = vsqDp[sqDp2Idx] - vsqDp2[sqDp2Idx - vsqA[sqTestIdx]];
}
if (sqK <= sqDp2Idx + vsqA[sqTestIdx]) {
if (0 < vsqDp2[sqDp2Idx]) {
sqAns++;
// printf("-->b\n");
break;
}
}
}
#if 0
printf("DP2 [%lld]\n", vsqA[sqTestIdx]);
printVector(vsqDp2);
#endif
}
return sqAns;
}
static void solverNew(SQWORD sqN, SQWORD sqK, const vector<SQWORD> &vsqA)
{
SQWORD sqNeeded = countNeedCards(vsqA, sqK);
printf("%lld\n", sqN - sqNeeded);
}
int main(void)
{
SQWORD sqN = inputSQWORD();
SQWORD sqK = inputSQWORD();
vector<SQWORD> vsqA;
for (SQWORD sqIdx = 0; sqIdx < sqN; sqIdx++) {
vsqA.emplace_back(inputSQWORD());
}
if (20000000000LL < sqN * sqN * sqK) {
solverNew(sqN, sqK, vsqA);
} else {
solverOld(sqN, sqK, vsqA);
}
return 0;
}
Submission Info
Submission Time
2020-01-19 11:56:09+0900
Task
D - No Need
User
yeye
Language
C++14 (GCC 5.4.1)
Score
300
Code Size
9780 Byte
Status
WA
Exec Time
199 ms
Memory
384 KB
Compile Error
./Main.cpp: In function ‘void printVector(std::vector<long int>)’:
./Main.cpp:258:35: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long int> >::value_type {aka long int}’ [-Wformat=]
printf("%lld ", vec[sqIdx]);
^
./Main.cpp: In function ‘int solverOld(SQWORD, SQWORD, const std::vector<long int>&)’:
./Main.cpp:305:27: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘SQWORD {aka long int}’ [-Wformat=]
printf("%lld\n", sqAns);
^
./Main.cpp: In function ‘void solverNew(SQWORD, SQWORD, const std::vector<long int>&)’:
./Main.cpp:368:36: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘SQWORD {aka long int}’ [-Wformat=]
printf("%lld\n", sqN - sqNeeded);
^
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
1 ms
256 KB
1_007.txt
AC
1 ms
256 KB
1_008.txt
AC
199 ms
256 KB
1_009.txt
AC
199 ms
256 KB
1_010.txt
AC
1 ms
256 KB
1_011.txt
AC
1 ms
256 KB
1_012.txt
AC
1 ms
256 KB
1_013.txt
AC
1 ms
256 KB
1_014.txt
AC
1 ms
256 KB
1_015.txt
AC
2 ms
256 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
2 ms
256 KB
1_020.txt
AC
1 ms
256 KB
1_021.txt
AC
1 ms
256 KB
1_022.txt
AC
1 ms
256 KB
1_023.txt
AC
1 ms
256 KB
1_024.txt
AC
34 ms
256 KB
1_025.txt
AC
41 ms
256 KB
2_026.txt
AC
1 ms
256 KB
2_027.txt
AC
2 ms
256 KB
2_028.txt
AC
2 ms
256 KB
2_029.txt
AC
91 ms
384 KB
2_030.txt
AC
91 ms
384 KB
2_031.txt
AC
25 ms
384 KB
2_032.txt
AC
2 ms
384 KB
2_033.txt
AC
24 ms
384 KB
2_034.txt
AC
2 ms
384 KB
2_035.txt
AC
2 ms
384 KB
2_036.txt
WA
42 ms
384 KB
2_037.txt
AC
2 ms
256 KB
2_038.txt
AC
2 ms
256 KB
2_039.txt
AC
2 ms
256 KB
2_040.txt
AC
20 ms
384 KB
2_041.txt
WA
23 ms
384 KB
2_042.txt
WA
34 ms
384 KB
2_043.txt
WA
23 ms
384 KB
2_044.txt
WA
24 ms
384 KB
2_045.txt
WA
13 ms
256 KB
2_046.txt
AC
29 ms
384 KB
2_047.txt
AC
39 ms
384 KB
2_048.txt
AC
48 ms
384 KB
2_049.txt
AC
42 ms
384 KB
2_050.txt
AC
39 ms
384 KB