Submission #9593574
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; /*----------------------------------------------*/ /*----------------------------------------------*/ struct PARAMS { vector<SQWORD> vsqA; SQWORD sqK; SQWORD sqN; }; static bool isNeeded( SQWORD sqTest, const PARAMS *pstParams) { vector<SQWORD> vsqDp(pstParams->sqK, 0); if (sqTest < 0) { return false; } if (pstParams->vsqA.size() <= sqTest) { return true; } if (pstParams->sqK <= pstParams->vsqA[sqTest]) { return true; } vsqDp[0] = 1; for (SQWORD sqCardIdx = 0; sqCardIdx < pstParams->vsqA.size(); sqCardIdx++) { if (sqCardIdx != sqTest) { for (SQWORD sqDpIdx = vsqDp.size() - 1; 0 <= sqDpIdx; sqDpIdx--) { SQWORD sqNextIdx = sqDpIdx + pstParams->vsqA[sqCardIdx]; if (sqNextIdx < pstParams->sqK) { vsqDp[sqNextIdx] += vsqDp[sqDpIdx]; if ((0 < vsqDp[sqDpIdx]) && (pstParams->sqK - pstParams->vsqA[sqTest] <= sqNextIdx)) { return true; } } } } } return false; } static SQWORD binarySearch( bool (*pfJudge)(SQWORD, const PARAMS*), SQWORD sqInitLower, SQWORD sqInitUpper, const PARAMS *pstParam) { SQWORD sqOk = sqInitUpper; SQWORD sqNg = sqInitLower; while (1LL < sqOk - sqNg) { SQWORD sqMid = (sqNg + sqOk) / 2LL; if (pfJudge(sqMid, pstParam)) { sqOk = sqMid; } else { sqNg = sqMid; } } return sqOk; } int main(void) { PARAMS stParams; stParams.sqN = inputSQWORD(); stParams.sqK = inputSQWORD(); for (SQWORD sqIdx = 0; sqIdx < stParams.sqN; sqIdx++) { stParams.vsqA.emplace_back(inputSQWORD()); } sort(stParams.vsqA.begin(), stParams.vsqA.end()); SQWORD sqBorderIdx = binarySearch(isNeeded, -1, stParams.sqN, &stParams); SQWORD sqAns = sqBorderIdx; printf("%lld\n", sqAns); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - No Need |
User | yeye |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 8161 Byte |
Status | AC |
Exec Time | 1033 ms |
Memory | 384 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:335: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); ^
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 | 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 | 5 ms | 256 KB |
1_009.txt | AC | 5 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 | 1 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 | 1 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 | 2 ms | 256 KB |
1_025.txt | AC | 2 ms | 256 KB |
2_026.txt | AC | 1 ms | 256 KB |
2_027.txt | AC | 1 ms | 256 KB |
2_028.txt | AC | 1 ms | 256 KB |
2_029.txt | AC | 954 ms | 384 KB |
2_030.txt | AC | 1033 ms | 384 KB |
2_031.txt | AC | 2 ms | 384 KB |
2_032.txt | AC | 2 ms | 384 KB |
2_033.txt | AC | 1 ms | 384 KB |
2_034.txt | AC | 1 ms | 384 KB |
2_035.txt | AC | 2 ms | 384 KB |
2_036.txt | AC | 11 ms | 384 KB |
2_037.txt | AC | 1 ms | 256 KB |
2_038.txt | AC | 1 ms | 256 KB |
2_039.txt | AC | 1 ms | 256 KB |
2_040.txt | AC | 42 ms | 384 KB |
2_041.txt | AC | 6 ms | 384 KB |
2_042.txt | AC | 9 ms | 384 KB |
2_043.txt | AC | 94 ms | 256 KB |
2_044.txt | AC | 84 ms | 384 KB |
2_045.txt | AC | 10 ms | 256 KB |
2_046.txt | AC | 213 ms | 384 KB |
2_047.txt | AC | 101 ms | 384 KB |
2_048.txt | AC | 330 ms | 384 KB |
2_049.txt | AC | 213 ms | 384 KB |
2_050.txt | AC | 225 ms | 384 KB |