Submission #58044
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | #include <bits/stdc++.h> #define F first #define S second #define MP make_pair #define pb push_back #define all(a) a.begin(), a.end() #define lcm( a, b ) (a)/__gcd((a),(b))*(b) #define endl '\n' using namespace std; typedef long long LL; typedef pair< int , int > P; typedef pair< LL, LL > LP; static const int INF = INT_MAX; static const LL LINF = LLONG_MAX; static const int MIN = INT_MIN; static const LL LMIN = LLONG_MIN; static const int MOD = 1000000007; static const int SIZE = 200005; const int dx[] = {0, -1, 1, 0}; const int dy[] = {-1, 0, 0, 1}; LL fac[SIZE], finv[SIZE], inv[SIZE]; void combInit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for ( int i = 2; i < SIZE; ++i ) { fac[i] = (fac[i - 1] * i) % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; finv[i] = (finv[i - 1] * inv[i]) % MOD; } } LL comb( int n, int k) { if ( n < k ) return 0; if ( n < 0 || k < 0 ) return 0; return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD; } vector< int > Div( int n ) { vector< int > ret; for ( int i = 1; i * i <= n; ++i ) { if ( n % i == 0 ) { ret.pb( i ); if ( i * i != n ) ret.pb( n / i ); } } sort( all( ret ) ); return ret; } typedef unsigned long long ull; int main() { ios::sync_with_stdio( false ); cin.tie(0); int n; ull k; cin >> n >> k; vector< ull > v(n); for ( int i = 0; i < n; ++i ) { cin >> v[i]; } int l, r; l = 0; r = 0; int res = -1; int bicnt[64] = {}; ull tmp = v[0]; int cnt = 0; while ( tmp > 0 ) { bicnt[cnt] += tmp & 1; tmp >>= 1; ++cnt; } if ( v[0] > k ) res = 1; while ( l < n ) { if ( r < n ) { ++r; while ( r < n ) { tmp = v[r]; cnt = 0; while ( tmp > 0 ) { bicnt[cnt] += tmp & 1; tmp >>= 1; ++cnt; } ull sum = 0; for ( int i = 0; i < 64; ++i ) { if ( bicnt[i] == r - l + 1 ) { sum += (ull)1 << i; } } if ( sum <= k ) { break ; } res = max(res, r - l + 1); ++r; } } tmp = v[l]; cnt = 0; while ( tmp > 0 ) { bicnt[cnt] -= tmp & 1; tmp >>= 1; ++cnt; } ++l; ull sum = 0; for ( int i = 0; i < 64; ++i ) { if ( bicnt[i] == r - l + 1 ) { sum += (ull)1 << i; } } if ( sum > k ) { res = max(res, r - l + 1); } } cout << res << endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 1254 - AND AND AND... |
ユーザー名 | ei1903 |
投稿日時 | 2020-01-09 00:13:26 |
言語 | C++14 |
状態 | Accepted |
得点 | 10 |
ソースコード長 | 3010 Byte |
最大実行時間 | 78 ms |
最大メモリ使用量 | 1652 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 10 / 10 | in* |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in01.txt | AC | 56 ms | 1372 KB |
1
|
in02.txt | AC | 41 ms | 1176 KB |
1
|
in03.txt | AC | 40 ms | 1244 KB |
1
|
in04.txt | AC | 37 ms | 1180 KB |
1
|
in05.txt | AC | 33 ms | 1376 KB |
1
|
in06.txt | AC | 41 ms | 1436 KB |
1
|
in07.txt | AC | 43 ms | 1372 KB |
1
|
in08.txt | AC | 46 ms | 1308 KB |
1
|
in09.txt | AC | 38 ms | 1244 KB |
1
|
in10.txt | AC | 54 ms | 1180 KB |
1
|
in11.txt | AC | 59 ms | 1244 KB |
1
|
in12.txt | AC | 51 ms | 1304 KB |
1
|
in13.txt | AC | 46 ms | 1364 KB |
1
|
in14.txt | AC | 46 ms | 1300 KB |
1
|
in15.txt | AC | 52 ms | 1488 KB |
1
|
in16.txt | AC | 47 ms | 1428 KB |
1
|
in17.txt | AC | 38 ms | 1368 KB |
1
|
in18.txt | AC | 47 ms | 1304 KB |
1
|
in19.txt | AC | 45 ms | 1496 KB |
1
|
in20.txt | AC | 42 ms | 1436 KB |
1
|
in21.txt | AC | 46 ms | 1504 KB |
1
|
in22.txt | AC | 45 ms | 1564 KB |
1
|
in23.txt | AC | 41 ms | 1372 KB |
1
|
in24.txt | AC | 52 ms | 1308 KB |
1
|
in25.txt | AC | 42 ms | 1368 KB |
1
|
in26.txt | AC | 51 ms | 1428 KB |
1
|
in27.txt | AC | 56 ms | 1364 KB |
1
|
in28.txt | AC | 52 ms | 1300 KB |
1
|
in29.txt | AC | 43 ms | 1360 KB |
1
|
in30.txt | AC | 46 ms | 1424 KB |
1
|
in31.txt | AC | 42 ms | 1356 KB |
1
|
in32.txt | AC | 39 ms | 1292 KB |
1
|
in33.txt | AC | 49 ms | 1480 KB |
1
|
in34.txt | AC | 51 ms | 1420 KB |
1
|
in35.txt | AC | 44 ms | 1484 KB |
1
|
in36.txt | AC | 51 ms | 1544 KB |
1
|
in37.txt | AC | 41 ms | 1612 KB |
1
|
in38.txt | AC | 47 ms | 1544 KB |
1
|
in39.txt | AC | 47 ms | 1480 KB |
1
|
in40.txt | AC | 47 ms | 1544 KB |
1
|
in41.txt | AC | 49 ms | 1476 KB |
1
|
in42.txt | AC | 56 ms | 1404 KB |
1
|
in43.txt | AC | 47 ms | 1472 KB |
1
|
in44.txt | AC | 47 ms | 1536 KB |
1
|
in45.txt | AC | 49 ms | 1472 KB |
1
|
in46.txt | AC | 54 ms | 1408 KB |
1
|
in47.txt | AC | 57 ms | 1600 KB |
1
|
in48.txt | AC | 50 ms | 1540 KB |
1
|
in49.txt | AC | 47 ms | 1604 KB |
1
|
in50.txt | AC | 51 ms | 1532 KB |
1
|
in51.txt | AC | 39 ms | 1468 KB |
1
|
in52.txt | AC | 54 ms | 1532 KB |
1
|
in53.txt | AC | 45 ms | 1468 KB |
1
|
in54.txt | AC | 50 ms | 1404 KB |
1
|
in55.txt | AC | 18 ms | 824 KB |
1
|
in56.txt | AC | 15 ms | 904 KB |
1
|
in57.txt | AC | 18 ms | 728 KB |
1
|
in58.txt | AC | 77 ms | 1588 KB |
1
|
in59.txt | AC | 78 ms | 1520 KB |
1
|
in60.txt | AC | 73 ms | 1584 KB |
1
|
in61.txt | AC | 45 ms | 1652 KB |
1
|
in62.txt | AC | 42 ms | 1460 KB |
1
|
sample01.txt | AC | 17 ms | 880 KB | |
sample02.txt | AC | 16 ms | 708 KB | |
sample03.txt | AC | 24 ms | 668 KB |