提出 #47979826

ソースコード 拡げる

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 2e5 + 10;
int n;
int a[N];
bitset<N> f;
int main() {
  n = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  sort(a + 1, a + 1 + n);
  ll sum = 0;
  for(int i = 1; i < n; i++)sum += a[i];
  if(sum < a[n])return puts("-1"), 0;
  int ans = a[n]; sum = 0; f.set(0);
  for(int r = a[n] / 2, j = 1; r < a[n]; r++) {
    int pos = upper_bound(a + 1, a + 1 + n, r) - a;
    while(j < pos) {f |= (f << a[j]); sum += a[j]; j++;}
    int now = f._Find_next(a[pos] - r - 1);
    if(pos < n) {if(sum - now >= a[pos + 1] - r)ans = min(ans, r);}
    else if(sum - now >= r)ans = min(ans, r);
  }
  printf("%d\n", ans);
  return 0;
}

提出情報

提出日時
問題 D - Walk Around Neighborhood
ユーザ thebighead
言語 C++ 20 (gcc 12.2)
得点 1100
コード長 1112 Byte
結果 AC
実行時間 573 ms
メモリ 4720 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1100 / 1100
結果
AC × 3
AC × 70
セット名 テストケース
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 01_small_06.txt, 02_rand1_01.txt, 02_rand1_02.txt, 02_rand1_03.txt, 02_rand1_04.txt, 02_rand1_05.txt, 02_rand1_06.txt, 02_rand1_07.txt, 02_rand1_08.txt, 02_rand1_09.txt, 02_rand1_10.txt, 02_rand1_11.txt, 02_rand1_12.txt, 02_rand1_13.txt, 02_rand1_14.txt, 02_rand1_15.txt, 02_rand1_16.txt, 02_rand1_17.txt, 02_rand1_18.txt, 02_rand1_19.txt, 02_rand1_20.txt, 02_rand1_21.txt, 02_rand1_22.txt, 02_rand1_23.txt, 02_rand1_24.txt, 02_rand1_25.txt, 02_rand1_26.txt, 02_rand1_27.txt, 02_rand1_28.txt, 02_rand1_29.txt, 02_rand1_30.txt, 02_rand1_31.txt, 02_rand1_32.txt, 02_rand1_33.txt, 02_rand1_34.txt, 02_rand1_35.txt, 03_rand2_01.txt, 03_rand2_02.txt, 03_rand2_03.txt, 03_rand2_04.txt, 03_rand2_05.txt, 04_rand3_01.txt, 04_rand3_02.txt, 04_rand3_03.txt, 05_other_01.txt, 05_other_02.txt, 05_other_03.txt, 05_other_04.txt, 05_other_05.txt, 05_other_06.txt, 05_other_07.txt, 05_other_08.txt, 06_handmade_01.txt, 06_handmade_02.txt, 06_handmade_03.txt, 06_handmade_04.txt, 06_handmade_05.txt, 06_handmade_06.txt, 06_handmade_07.txt, 06_handmade_08.txt, 06_handmade_09.txt, 06_handmade_10.txt
ケース名 結果 実行時間 メモリ
00_sample_01.txt AC 1 ms 3712 KiB
00_sample_02.txt AC 1 ms 3772 KiB
00_sample_03.txt AC 1 ms 3520 KiB
01_small_01.txt AC 11 ms 3768 KiB
01_small_02.txt AC 3 ms 3768 KiB
01_small_03.txt AC 7 ms 3728 KiB
01_small_04.txt AC 26 ms 3728 KiB
01_small_05.txt AC 19 ms 3896 KiB
01_small_06.txt AC 15 ms 3768 KiB
02_rand1_01.txt AC 413 ms 4696 KiB
02_rand1_02.txt AC 397 ms 4460 KiB
02_rand1_03.txt AC 387 ms 4664 KiB
02_rand1_04.txt AC 421 ms 4644 KiB
02_rand1_05.txt AC 427 ms 4640 KiB
02_rand1_06.txt AC 408 ms 4672 KiB
02_rand1_07.txt AC 423 ms 4664 KiB
02_rand1_08.txt AC 377 ms 4640 KiB
02_rand1_09.txt AC 427 ms 4500 KiB
02_rand1_10.txt AC 393 ms 4692 KiB
02_rand1_11.txt AC 377 ms 4604 KiB
02_rand1_12.txt AC 391 ms 4644 KiB
02_rand1_13.txt AC 380 ms 4604 KiB
02_rand1_14.txt AC 425 ms 4544 KiB
02_rand1_15.txt AC 427 ms 4528 KiB
02_rand1_16.txt AC 416 ms 4544 KiB
02_rand1_17.txt AC 434 ms 4608 KiB
02_rand1_18.txt AC 442 ms 4440 KiB
02_rand1_19.txt AC 418 ms 4668 KiB
02_rand1_20.txt AC 420 ms 4504 KiB
02_rand1_21.txt AC 419 ms 4540 KiB
02_rand1_22.txt AC 448 ms 4504 KiB
02_rand1_23.txt AC 409 ms 4592 KiB
02_rand1_24.txt AC 2 ms 3724 KiB
02_rand1_25.txt AC 2 ms 3868 KiB
02_rand1_26.txt AC 2 ms 3920 KiB
02_rand1_27.txt AC 5 ms 3728 KiB
02_rand1_28.txt AC 5 ms 3664 KiB
02_rand1_29.txt AC 10 ms 3876 KiB
02_rand1_30.txt AC 8 ms 3872 KiB
02_rand1_31.txt AC 5 ms 3864 KiB
02_rand1_32.txt AC 6 ms 3668 KiB
02_rand1_33.txt AC 321 ms 4504 KiB
02_rand1_34.txt AC 324 ms 4660 KiB
02_rand1_35.txt AC 320 ms 4548 KiB
03_rand2_01.txt AC 443 ms 4672 KiB
03_rand2_02.txt AC 394 ms 4504 KiB
03_rand2_03.txt AC 427 ms 4528 KiB
03_rand2_04.txt AC 419 ms 4660 KiB
03_rand2_05.txt AC 395 ms 4444 KiB
04_rand3_01.txt AC 573 ms 4720 KiB
04_rand3_02.txt AC 569 ms 4440 KiB
04_rand3_03.txt AC 573 ms 4528 KiB
05_other_01.txt AC 449 ms 4600 KiB
05_other_02.txt AC 486 ms 4504 KiB
05_other_03.txt AC 450 ms 4660 KiB
05_other_04.txt AC 476 ms 4504 KiB
05_other_05.txt AC 455 ms 4488 KiB
05_other_06.txt AC 503 ms 4548 KiB
05_other_07.txt AC 492 ms 4692 KiB
05_other_08.txt AC 519 ms 4608 KiB
06_handmade_01.txt AC 1 ms 3568 KiB
06_handmade_02.txt AC 1 ms 3876 KiB
06_handmade_03.txt AC 79 ms 4464 KiB
06_handmade_04.txt AC 22 ms 4444 KiB
06_handmade_05.txt AC 265 ms 4456 KiB
06_handmade_06.txt AC 3 ms 4092 KiB
06_handmade_07.txt AC 10 ms 4692 KiB
06_handmade_08.txt AC 37 ms 4668 KiB
06_handmade_09.txt AC 553 ms 4664 KiB
06_handmade_10.txt AC 158 ms 4076 KiB