結果
問題 | No.45 回転寿司 |
ユーザー | kaoru murata |
提出日時 | 2021-09-15 21:24:09 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 1 ms / 5,000 ms |
コード長 | 5,053 bytes |
コンパイル時間 | 344 ms |
コンパイル使用メモリ | 34,944 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 22:42:27 |
合計ジャッジ時間 | 1,478 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | AC | 1 ms
5,376 KB |
testcase_27 | AC | 1 ms
5,376 KB |
testcase_28 | AC | 1 ms
5,376 KB |
testcase_29 | AC | 1 ms
5,376 KB |
testcase_30 | AC | 1 ms
5,376 KB |
testcase_31 | AC | 1 ms
5,376 KB |
testcase_32 | AC | 1 ms
5,376 KB |
testcase_33 | AC | 1 ms
5,376 KB |
コンパイルメッセージ
main.c: In function 'in': main.c:38:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 38 | while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; | ^~~~~~~~~~~~~~~~ main.c: In function 'out': main.c:57:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration] 57 | putchar_unlocked('-'); | ^~~~~~~~~~~~~~~~
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <assert.h> #include <math.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> /* signed integer */ typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; /* unsigned integer */ typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; /* floating point number */ typedef float f32; typedef double f64; typedef long double f80; /* input / output */ static inline i64 in(void) { i64 x = 0; i64 f = 1; i64 c; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline u64 inu(void) { u64 x = 0; u64 c; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } static inline void out(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } if (x >= 10) out(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void outu(u64 x) { if (x >= 10) outu(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void nl(void) { putchar_unlocked('\n'); } static inline void sp(void) { putchar_unlocked(' '); } /* bits */ static inline u64 ctz(u64 n) { return __builtin_ctzll(n); } static inline u64 clz(u64 n) { return __builtin_clzll(n); } static inline u64 popcnt(u64 n) { return __builtin_popcountll(n); } static inline u64 _gcd_(u64 a, u64 b) { i32 shift = 0; while (a && b && a != b) { bool c = !(a & 1); bool d = !(b & 1); if (c && d) { ++shift; a >>= 1; b >>= 1; } else if (c && !d) a >>= 1; else if (!c && d) b >>= 1; else if (a >= b) a = (a - b) >> 1; else { u64 tmp = a; a = (b - a) >> 1; b = tmp; } } return !a ? b << shift : a << shift; } static inline u64 _lcm_(u64 a, u64 b) { return a / _gcd_(a, b) * b; } static inline i32 ceil_pow2_32(i32 n) { return n <= 1 ? 0 : 32 - __builtin_clz(n - 1); } static inline i64 ceil_pow2_64(i64 n) { return n <= 1 ? 0 : 64 - __builtin_clzl(n - 1); } /* xorshift */ static u64 _rng = 88172645463325252ULL; u64 next_rand(void) { _rng = _rng ^ (_rng << 7); return _rng = _rng ^ (_rng >> 9); } /* modint */ static inline u64 _inv(u64 mod) { int i; u64 u = 1; u64 v = 0; u64 x = 1ULL << 63; for (i = 0; i < 64; i++) { if (u & 1){ u = (u + mod) / 2; v = v / 2 + x; } else { u >>= 1; v >>= 1; } } return -v; } static inline u64 _r2(u64 mod) { return (u128) (i128) -1 % mod + 1; } static inline u64 _one(u64 mod) { return -1ULL % mod + 1; } static inline u64 _MR(u128 x, u64 inv, u64 mod) { i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64); return z < 0 ? z + mod : (u64)z; } static inline u64 to_montgomery_form(u64 a, u64 r2, u64 inv, u64 mod) { return _MR((u128)a * r2, inv, mod); } static inline u64 from_montgomery_form(u64 a, u64 inv, u64 mod) { return _MR((u128)a, inv, mod); } static inline u64 addmod64(u64 x, u64 y, u64 mod) { return x + y >= mod ? x + y - mod : x + y; } static inline u64 submod64(u64 x, u64 y, u64 mod) { return x >= y ? x - y : x - y + mod; } static inline u64 mulmod64(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod); } static inline u64 powmod64(u64 a, u64 n, u64 r2, u64 inv, u64 mod) { u64 res = _one(mod); u64 A = to_montgomery_form(a, r2, inv, mod); while (n > 0) { if (n & 1) res = _MR((u128)res * A, inv, mod); A = _MR((u128)A * A, inv, mod); n >>= 1; } return from_montgomery_form(res, inv, mod); } static inline u64 divmod64(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { // assert(is_prime(mod)); u64 z = powmod64(y, mod - 2, r2, inv, mod); return mulmod64(x, z, r2, inv, mod); } static inline u64 is_prime(u64 n) { if (n < 2 || ((n % 6 != 1) && (n % 6 != 5))) return (n == 2) || (n == 3); u64 r2 = _r2(n); u64 inv = _inv(n); u64 s = ctz(n - 1); u64 d = (n - 1) >> s; u64 as[] = {2,325,9375,28178,450775,9780504,1795265022}; for (int i = 0; i < 7; i++) { u64 a = as[i]; if (_MR(a, inv, n) == 0) return 1; u64 res = powmod64(a, d, r2, inv, n); if (res == 1) continue; u64 ok = 1; for (u64 r = 0; r < s; r++) { if (res == n - 1) { ok = 0; break; } res = mulmod64(res, res, r2, inv, n); } if (ok) return 0; } return 1; } int dp[1010]; int max(int a, int b) { return (a > b) ? a : b; } void Main() { int i, N = in(); for (i = 0; i < N; i++) { int K = in(); dp[i + 1] = max(dp[i + 1], (i - 1 >= 0 ? dp[i - 1] : 0) + K); dp[i + 1] = max(dp[i + 1], dp[i]); } out(dp[N]); nl(); } int main() { Main(); return 0; }