提出 #48012160

ソースコード 拡げる

#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
#define int long long
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;
}
bool chkmin(int &a, int b) {return (b < a ? a = b, true : false);}
const int N = 10;
const int INF = 1e18;
int n, S, T, A, w = 40;
int val[N], c[N], sum[1 << 8], tr[1 << 8], f[50][2][2][1 << 8];
int vis[1 << 8], tmp[1 << 8];
signed main() {
  n = read(); S = read(); T = read(); A = read();
  for(int i = 0; i < n; i++)val[i] = read(), c[i] = read();
  for(int i = 0; i < (1 << n); i++) {
    for(int j = 0; j < n; j++) {
      if(i >> j & 1)sum[i] += c[j];
    }
  }
  for(int msk = 0; msk < (1 << n); msk++) {
    for(int i = 0; i < n; i++) {
      if(msk >> i & 1)tr[msk] ^= val[i];
    }
  }
  for(int i = 0; i < (1 << n); i++) {
    for(int x = 0; x < 2; x++) {
      for(int msk = 0; msk < (1 << n); msk++) {
        f[0][x][0][msk] = sum[msk];
        f[0][x][1][msk] = sum[msk] + A;
      }
    }
  }
  for(int i = 0; i < w; i++) {
    for(int x = 0; x < 2; x++) {
      for(int y = 0; y < 2; y++) {
        for(int msk = 0; msk < (1 << n); msk++) {
          f[i + 1][x][y][msk] = INF;
          // printf("f:%d %d %d %d %d\n", i, x, y, msk, f[i][x][y][msk]); 
        }
      }
    }
    for(int x = 0; x < 2; x++) {
      for(int y = 0; y < 2; y++) {
        int st = x ? 0 : (S >> i & 1);
        int ed = y ? 1 : (T >> i & 1);
        for(int msk = 0; msk < (1 << n); msk++) {
          if((tr[msk] >> i & 1) == (st ^ ed)) {
            chkmin(f[i + 1][x][y][msk], f[i][x][y][msk]);
          }
        }
      }
    }
    for(int x = 0; x < 2; x++) {
      int st = x ? 0 : (S >> i & 1);
      // cout << "st:" << st << endl;
      for(int msk = 0; msk < (1 << n); msk++) {
        tmp[msk] = INF; vis[msk] = false;
        if((tr[msk] >> i & 1) == st)tmp[msk] = f[i][x][1][msk];
      }
      while(true) {
        int mn = INF, pos = -1;
        for(int msk = 0; msk < (1 << n); msk++)
          if(!vis[msk] && chkmin(mn, tmp[msk]))pos = msk;
        if(!~pos)break;
        vis[pos] = true;
        for(int msk = 0; msk < (1 << n); msk++) {
          if((tr[msk] >> i & 1) == 1)
            chkmin(tmp[pos ^ msk], tmp[pos] + f[i][1][1][msk]);
          for(int y = 0; y < 2; y++) {
            int ed = y ? 1 : (T >> i & 1);
            if((tr[msk] >> i & 1) == (ed ^ 1)) {
              // cout << x << ' ' << y << ' ' << tmp[pos] << ' ' << (pos ^ msk) << ' ' << tmp[pos] + f[i][1][y][msk] << endl;
              chkmin(f[i + 1][x][y][pos ^ msk], tmp[pos] + f[i][1][y][msk]);
            }
          }
        }
      }
      // cout << "ans:" << f[w][0][0][1] << endl;
    }
  }
  int ans = INF;
  for(int msk = 0; msk < (1 << n); msk++) {
    chkmin(ans, f[w][0][0][msk]);
    // cout << "msk:" << msk << ' ' << f[w][0][0][msk] << endl;
  }
  printf("%lld\n", (ans == INF ? -1 : ans));
  return 0;
}

提出情報

提出日時
問題 E - Increment or XOR
ユーザ thebighead
言語 C++ 20 (gcc 12.2)
得点 1400
コード長 3280 Byte
結果 AC
実行時間 16 ms
メモリ 4196 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1400 / 1400
結果
AC × 4
AC × 57
セット名 テストケース
Sample 01.txt, 02.txt, 03.txt, 04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt
ケース名 結果 実行時間 メモリ
01.txt AC 1 ms 3992 KiB
02.txt AC 1 ms 4120 KiB
03.txt AC 1 ms 4052 KiB
04.txt AC 15 ms 4108 KiB
05.txt AC 1 ms 3996 KiB
06.txt AC 1 ms 4116 KiB
07.txt AC 1 ms 3996 KiB
08.txt AC 1 ms 3956 KiB
09.txt AC 12 ms 3960 KiB
10.txt AC 2 ms 4124 KiB
11.txt AC 14 ms 4112 KiB
12.txt AC 12 ms 3964 KiB
13.txt AC 14 ms 3920 KiB
14.txt AC 15 ms 4000 KiB
15.txt AC 16 ms 3984 KiB
16.txt AC 16 ms 3960 KiB
17.txt AC 16 ms 3960 KiB
18.txt AC 16 ms 4196 KiB
19.txt AC 16 ms 4104 KiB
20.txt AC 15 ms 4140 KiB
21.txt AC 15 ms 3920 KiB
22.txt AC 14 ms 3996 KiB
23.txt AC 15 ms 3932 KiB
24.txt AC 16 ms 3996 KiB
25.txt AC 16 ms 4112 KiB
26.txt AC 15 ms 4000 KiB
27.txt AC 16 ms 3916 KiB
28.txt AC 16 ms 3968 KiB
29.txt AC 15 ms 4132 KiB
30.txt AC 15 ms 3868 KiB
31.txt AC 15 ms 3988 KiB
32.txt AC 15 ms 4192 KiB
33.txt AC 15 ms 4128 KiB
34.txt AC 15 ms 4000 KiB
35.txt AC 16 ms 3936 KiB
36.txt AC 14 ms 4192 KiB
37.txt AC 16 ms 4064 KiB
38.txt AC 15 ms 4128 KiB
39.txt AC 15 ms 4144 KiB
40.txt AC 15 ms 3964 KiB
41.txt AC 15 ms 4060 KiB
42.txt AC 15 ms 4008 KiB
43.txt AC 16 ms 4124 KiB
44.txt AC 15 ms 4108 KiB
45.txt AC 15 ms 4188 KiB
46.txt AC 16 ms 4096 KiB
47.txt AC 15 ms 3988 KiB
48.txt AC 15 ms 4108 KiB
49.txt AC 16 ms 4056 KiB
50.txt AC 15 ms 4004 KiB
51.txt AC 15 ms 4056 KiB
52.txt AC 15 ms 4108 KiB
53.txt AC 16 ms 3912 KiB
54.txt AC 15 ms 3940 KiB
55.txt AC 1 ms 3984 KiB
56.txt AC 1 ms 3912 KiB
57.txt AC 1 ms 4060 KiB