QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311954#4254. Marketing networkhos_lyric#60 956ms4696kbC++146.8kb2024-01-23 01:11:172024-07-04 03:21:21

Judging History

This is the latest submission verdict.

  • [2024-07-04 03:21:21]
  • Judged
  • Verdict: 60
  • Time: 956ms
  • Memory: 4696kb
Show
  • [2024-01-23 01:11:17]
  • Submitted

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


vector<int> uf;
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


constexpr int INF = 1001001001;
using INT = __int128;

int N, M, S, K;
vector<int> X;
vector<int> A, B, C;


vector<int> brute() {
  vector<int> ans;
  for (int p = 0; p < 1 << M; ++p) {
    int cost = 0;
    bool ok = true;
    uf.assign(N, -1);
    for (int i = 0; i < M; ++i) if (p >> i & 1) {
      cost += C[i];
      if (!connect(A[i], B[i])) ok = false;
    }
    for (int s = 0; s < S; ++s) {
      ok = ok && (root(X[0]) == root(X[s]));
    }
    if (ok) {
// if(cost==13){for(int i=0;i<M;++i)if(p>>i&1)cerr<<i<<" ";cerr<<endl;}
      ans.push_back(cost);
    }
  }
  sort(ans.begin(), ans.end());
  ans.resize(K, -1);
  return ans;
}


int counter;
pair<int, INT> steiner(INT ban) {
++counter;if(!(counter&(counter-1)))cerr<<"counter = "<<counter<<" ..."<<endl;
  vector<vector<int>> G(N);
  for (int i = 0; i < M; ++i) if (!(ban >> i & 1)) {
    G[A[i]].push_back(i);
    G[B[i]].push_back(i);
  }
  vector<vector<int>> dp(1 << S, vector<int>(N, INF));
  vector<vector<int>> prv(1 << S, vector<int>(N, 0));
  for (int p = 1; p < 1 << S; ++p) {
    if (p & (p - 1)) {
      for (int q = p; --q &= p; ) {
        for (int u = 0; u < N; ++u) {
          if (chmin(dp[p][u], dp[q][u] + dp[p - q][u])) {
            prv[p][u] = q;
          }
        }
      }
    } else {
      const int s = __builtin_ctz(p);
      dp[p][X[s]] = 0;
    }
    using Entry = pair<int, int>;
    priority_queue<Entry, vector<Entry>, greater<Entry>> que;
    for (int u = 0; u < N; ++u) if (dp[p][u] < INF) {
      que.emplace(dp[p][u], u);
    }
    for (; !que.empty(); ) {
      const int c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (dp[p][u] != c) continue;
      for (const int i : G[u]) {
        const int cc = c + C[i];
        const int v = A[i] ^ B[i] ^ u;
        if (chmin(dp[p][v], cc)) {
          prv[p][v] = ~i;
          que.emplace(cc, v);
        }
      }
    }
  }
  const int all = (1 << S) - 1;
  int um = 0;
  for (int u = 0; u < N; ++u) if (dp[all][um] > dp[all][u]) um = u;
  INT used = 0;
  if (dp[all][um] < INF) {
    vector<pair<int, int>> stack;
    stack.emplace_back(all, um);
    for (; stack.size(); ) {
      const int p = stack.back().first;
      const int u = stack.back().second;
      stack.pop_back();
// cerr<<"recover "<<p<<" "<<u<<" "<<prv[p][u]<<endl;
      if (prv[p][u] > 0) {
        const int q = prv[p][u];
        stack.emplace_back(q, u);
        stack.emplace_back(p - q, u);
      } else if (prv[p][u] < 0) {
        const int i = ~prv[p][u];
        used |= (INT)1 << i;
        stack.emplace_back(p, A[i] ^ B[i] ^ u);
      }
    }
  }
/*
cerr<<"[steiner] ";
for(int i=0;i<M;++i)if(ban>>i&1)cerr<<i<<" ";
cerr<<": "<<dp[all][um]<<"; ";
for(int i=0;i<M;++i)if(used>>i&1)cerr<<i<<" ";
cerr<<endl;
*/
  return make_pair(dp[all][um], used);
}

vector<int> run() {
counter=0;
  vector<int> ans;
  vector<INT> sols;
  // ((cost, used), ban)
  using Entry = pair<pair<int, INT>, INT>;
  priority_queue<Entry, vector<Entry>, greater<Entry>> que;
  set<INT> bans{0}, vis;
  {
    const auto res = steiner(0);
    if (res.first < INF) {
      que.emplace(res, 0);
    }
  }
  for (; que.size(); ) {
    const int cost = que.top().first.first;
    const INT used = que.top().first.second;
    const INT ban = que.top().second;
    que.pop();
/*
cerr<<cost<<": ";
for(int i=0;i<M;++i)if(used>>i&1)cerr<<i<<" ";
cerr<<";  ";
for(int i=0;i<M;++i)if(ban>>i&1)cerr<<i<<" ";
cerr<<endl;
*/
    if (vis.insert(used).second) {
      ans.push_back(cost);
      sols.push_back(used);
      if ((int)ans.size() == K) break;
      // unnecessary edge
      uf.assign(N, -1);
      for (int i = 0; i < M; ++i) if (used & (INT)1 << i) {
        assert(connect(A[i], B[i]));
      }
      for (int i = 0; i < M; ++i) if (root(A[i]) != root(B[i])) {
        if (!vis.count(used | (INT)1 << i)) {
          que.emplace(make_pair(cost + C[i], used | (INT)1 << i), -1);
        }
      }
    }
    if (~ban) {
      // ban more
      for (int i = 0; i < M; ++i) if (used & (INT)1 << i) {
        const INT bb = ban | (INT)1 << i;
        if (bans.insert(bb).second) {
          for (int k = 0; k < (int)ans.size(); ++k) {
            if (!(sols[k] & bb)) {
              que.emplace(make_pair(ans[k], sols[k]), bb);
              goto done;
            }
          }
          {
            const auto res = steiner(bb);
            if (res.first < INF) {
              que.emplace(res, bb);
            }
          }
         done:{}
        }
      }
    }
  }
  ans.resize(K, -1);
cerr<<"counter = "<<counter<<endl;
  return ans;
}


int main() {
  for (; ~scanf("%d%d%d%d", &N, &M, &S, &K); ) {
    X.resize(S);
    for (int s = 0; s < S; ++s) {
      scanf("%d", &X[s]);
      --X[s];
    }
    A.resize(M);
    B.resize(M);
    C.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d", &A[i], &B[i], &C[i]);
      --A[i];
      --B[i];
    }
    
    const auto ans = run();
#ifdef LOCAL
if(M<=20){
 const auto brt=brute();
 if(brt!=ans){
  cerr<<"brt = "<<brt<<endl;
  cerr<<"ans = "<<ans<<endl;
 }
 assert(brt==ans);
}
#endif
    for (int k = 0; k < K; ++k) {
      printf("%d\n", ans[k]);
    }
  }
  return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 2
Accepted
time: 1ms
memory: 3832kb

input:

10 20 4 10
4 9 1 6
6 3 22
9 7 89
9 5 60
4 5 10
8 5 90
4 9 38
9 3 62
1 2 50
8 9 48
4 5 82
5 3 22
2 3 73
2 6 74
9 8 39
8 2 54
4 5 29
8 6 84
5 10 92
2 5 20
3 2 22

output:

162
162
164
181
181
183
184
184
186
186

result:

ok 10 numbers

Test #2:

score: 2
Accepted
time: 1ms
memory: 3864kb

input:

10 20 4 10
4 3 8 9
3 2 68
2 9 22
8 6 35
6 3 6
10 6 88
4 2 76
8 2 100
9 7 86
2 7 24
1 5 89
5 9 67
4 2 22
2 6 12
7 1 42
10 1 64
3 4 50
7 10 1
5 3 60
2 3 7
7 8 75

output:

92
93
97
98
98
99
116
117
120
121

result:

ok 10 numbers

Test #3:

score: 2
Accepted
time: 1ms
memory: 4120kb

input:

10 20 4 10
7 9 5 3
10 3 79
4 2 44
10 5 41
7 1 51
6 9 29
4 10 76
7 3 52
5 2 67
3 1 90
5 3 97
5 7 56
7 2 73
8 4 60
7 9 64
4 6 37
4 5 100
1 6 82
7 6 52
4 2 68
3 5 9

output:

125
129
142
146
154
158
162
166
166
169

result:

ok 10 numbers

Test #4:

score: 2
Accepted
time: 0ms
memory: 4124kb

input:

10 20 4 10
10 5 2 3
10 9 1
3 6 26
8 4 14
2 9 36
4 1 63
6 4 40
4 9 56
3 6 11
1 2 49
5 1 3
2 3 25
1 3 14
9 7 22
5 3 89
6 10 27
5 6 42
7 9 7
3 9 29
10 1 36
5 3 94

output:

72
78
79
79
79
80
81
83
83
85

result:

ok 10 numbers

Test #5:

score: 2
Accepted
time: 1ms
memory: 3868kb

input:

10 20 4 10
9 10 4 2
9 4 81
7 4 28
5 4 61
8 6 17
2 3 58
6 8 26
10 1 7
9 10 59
5 9 69
8 1 100
8 6 36
4 6 37
10 4 59
10 8 26
7 10 18
4 2 41
2 6 91
8 2 70
8 9 19
1 10 88

output:

132
139
140
145
146
147
149
149
152
153

result:

ok 10 numbers

Test #6:

score: 2
Accepted
time: 6ms
memory: 4280kb

input:

50 100 10 1
47 18 20 27 3 22 42 23 21 30
19 23 51
2 25 60
2 14 87
7 28 45
23 5 26
27 23 58
31 16 6
37 15 5
50 45 54
13 17 42
1 35 30
44 21 98
18 49 51
6 3 62
32 10 15
20 5 67
42 47 41
35 32 82
40 17 21
10 18 49
13 33 20
22 40 12
9 43 24
7 38 44
32 40 15
23 34 38
35 24 83
17 8 88
10 44 5
16 17 78
14 ...

output:

616

result:

ok 1 number(s): "616"

Test #7:

score: 2
Accepted
time: 8ms
memory: 4588kb

input:

50 100 10 1
14 24 37 22 39 38 36 7 49 41
39 13 79
41 30 78
24 50 38
48 47 83
25 17 98
44 18 5
45 13 11
35 30 33
11 34 20
22 3 16
26 23 100
3 15 41
25 16 64
36 2 18
6 25 32
33 44 5
27 9 71
25 39 87
38 2 25
12 19 18
40 48 9
19 10 31
50 41 15
23 44 47
5 21 36
34 18 75
12 9 46
20 27 92
25 24 15
10 42 99...

output:

428

result:

ok 1 number(s): "428"

Test #8:

score: 2
Accepted
time: 8ms
memory: 4588kb

input:

50 100 10 1
40 26 28 20 1 18 36 32 7 42
34 27 38
44 14 54
18 22 30
24 18 65
23 1 13
35 2 65
29 25 2
16 11 98
36 33 50
16 3 71
36 26 10
33 21 85
10 22 45
29 35 12
9 1 12
26 3 65
38 39 16
15 32 54
37 26 5
37 50 19
19 23 100
5 36 72
3 27 63
21 30 35
34 25 100
22 42 9
36 34 65
5 6 20
5 11 98
17 27 1
21 ...

output:

363

result:

ok 1 number(s): "363"

Test #9:

score: 2
Accepted
time: 8ms
memory: 4356kb

input:

50 100 10 1
3 33 31 20 10 40 18 27 38 8
16 18 86
26 3 61
14 19 68
40 12 60
3 15 62
32 3 68
49 39 6
8 17 79
36 18 84
5 34 73
33 11 3
22 9 32
28 36 83
11 29 1
42 49 31
2 5 64
50 17 26
28 36 48
14 19 81
34 16 80
32 35 60
40 44 55
1 40 93
34 27 93
5 20 42
35 34 38
45 28 52
24 44 78
18 45 47
7 12 54
15 2...

output:

734

result:

ok 1 number(s): "734"

Test #10:

score: 2
Accepted
time: 9ms
memory: 4364kb

input:

50 100 10 1
16 9 2 19 33 47 18 36 48 34
24 44 37
26 35 77
31 16 91
35 6 16
44 5 38
31 1 35
3 26 42
19 5 51
7 43 100
13 15 55
2 42 1
37 28 40
27 37 16
11 21 19
45 25 34
26 38 57
48 9 52
7 44 41
29 14 95
2 41 65
20 10 51
37 19 93
31 46 33
9 29 87
21 34 65
33 7 83
44 22 51
23 39 85
39 26 50
30 15 8
22 ...

output:

517

result:

ok 1 number(s): "517"

Test #11:

score: 2
Accepted
time: 8ms
memory: 4292kb

input:

50 100 10 1
27 13 16 43 46 32 22 24 25 34
31 39 47
34 18 42
43 38 86
18 49 69
15 32 39
3 46 61
45 13 62
37 46 27
50 16 25
8 32 71
23 43 81
2 10 46
27 13 64
43 34 61
27 11 92
17 36 2
17 7 6
22 16 82
43 1 62
15 18 55
12 27 43
32 50 60
45 44 15
5 37 81
44 39 14
29 23 69
8 34 64
23 38 30
6 42 24
40 38 5...

output:

598

result:

ok 1 number(s): "598"

Test #12:

score: 2
Accepted
time: 9ms
memory: 4592kb

input:

50 100 10 1
36 40 47 22 12 9 10 49 13 19
50 24 14
10 50 80
24 46 74
45 40 23
47 43 87
22 14 65
36 12 49
32 27 84
1 27 13
33 3 43
4 18 18
34 13 50
38 12 54
25 46 8
4 1 83
9 26 78
20 8 85
26 13 97
6 46 96
33 19 30
38 15 74
20 22 61
33 23 82
8 44 2
27 16 78
24 41 15
33 24 84
11 37 89
26 19 71
42 22 74
...

output:

492

result:

ok 1 number(s): "492"

Test #13:

score: 2
Accepted
time: 7ms
memory: 4580kb

input:

50 100 10 1
40 41 42 11 24 21 38 35 23 36
49 35 31
29 43 77
9 34 6
4 37 36
4 47 21
22 11 47
38 40 13
41 13 93
13 42 21
27 18 19
10 1 33
17 44 43
24 7 73
46 31 100
38 34 46
8 31 62
41 45 83
40 46 5
25 42 67
16 49 63
45 40 39
16 12 18
48 50 34
8 45 79
12 25 3
44 35 54
7 4 93
12 21 14
10 44 79
1 20 97
...

output:

454

result:

ok 1 number(s): "454"

Test #14:

score: 2
Accepted
time: 8ms
memory: 4344kb

input:

50 100 10 1
10 45 23 1 25 14 13 39 15 12
50 42 3
24 2 77
32 40 62
44 18 39
49 3 39
41 47 59
29 50 40
45 17 71
45 5 28
24 13 34
43 14 44
38 27 34
29 48 94
37 9 34
39 8 68
18 6 6
31 26 18
18 44 13
32 22 55
11 19 33
3 45 6
41 16 99
4 35 27
13 38 66
41 47 53
42 14 67
37 24 51
23 6 8
38 41 73
46 44 87
21...

output:

553

result:

ok 1 number(s): "553"

Test #15:

score: 2
Accepted
time: 7ms
memory: 4584kb

input:

50 100 10 1
38 19 30 18 50 34 16 9 27 37
32 44 96
25 12 8
43 14 74
22 18 59
11 32 50
37 6 95
13 5 3
2 28 93
46 49 31
7 1 24
34 28 97
36 12 72
32 28 26
36 22 23
7 12 69
44 31 68
4 38 28
35 32 33
33 24 99
4 38 43
40 24 56
50 3 57
40 22 61
18 49 18
24 31 51
8 18 76
34 39 45
37 42 59
23 28 72
25 42 89
2...

output:

536

result:

ok 1 number(s): "536"

Test #16:

score: 2
Accepted
time: 3ms
memory: 4272kb

input:

50 100 5 20
27 21 46 15 49
30 41 55
50 27 61
48 6 32
7 31 94
49 39 53
12 36 40
46 26 80
39 42 61
41 2 38
35 33 37
12 15 61
13 9 12
36 35 77
6 40 74
9 15 47
43 15 95
48 9 62
45 30 25
41 35 1
42 16 41
45 43 58
22 23 14
24 31 10
46 17 97
14 41 52
44 39 28
19 11 35
44 37 12
45 9 30
10 2 5
13 15 30
26 33...

output:

379
382
384
384
385
385
387
387
387
388
388
388
388
389
389
390
390
390
390
390

result:

ok 20 numbers

Test #17:

score: 2
Accepted
time: 0ms
memory: 4256kb

input:

50 100 5 20
43 27 13 9 36
14 3 86
22 5 89
19 46 59
46 35 12
21 43 5
3 37 10
1 5 38
28 16 58
12 6 50
4 7 83
40 44 31
40 26 65
46 34 75
24 43 21
31 15 25
30 33 7
1 22 12
18 9 42
13 27 30
32 3 77
22 11 80
38 37 80
45 31 70
49 50 6
46 26 70
21 40 83
38 5 23
6 37 97
47 15 6
35 19 40
39 2 50
48 20 97
27 4...

output:

184
186
187
189
189
190
190
191
191
191
192
192
192
192
193
193
193
193
194
194

result:

ok 20 numbers

Test #18:

score: 2
Accepted
time: 3ms
memory: 3964kb

input:

50 100 5 20
6 3 33 9 26
3 35 77
33 13 98
45 48 9
29 33 12
36 48 99
47 25 1
42 31 5
8 33 62
48 10 61
42 29 67
43 49 88
6 16 48
40 33 95
15 48 40
17 26 69
17 43 36
22 18 85
15 21 30
4 49 61
30 12 25
26 42 60
17 41 8
43 23 41
24 32 74
30 32 83
27 6 76
5 35 73
5 50 59
21 25 54
31 18 6
9 32 58
40 43 48
3...

output:

413
414
416
417
418
418
419
419
419
419
419
420
420
420
421
421
421
422
422
422

result:

ok 20 numbers

Test #19:

score: 2
Accepted
time: 41ms
memory: 3976kb

input:

50 100 5 20
23 27 50 21 13
36 47 9
37 40 58
15 38 4
17 38 30
8 1 19
39 43 71
47 10 63
47 8 90
20 47 41
12 2 82
21 28 90
34 15 1
50 15 93
33 34 19
39 44 48
5 44 49
25 31 35
38 32 47
26 40 23
8 10 9
32 13 95
12 39 16
15 22 6
10 22 33
9 43 39
7 26 65
3 13 77
18 2 61
31 27 47
46 11 81
26 17 13
6 30 81
2...

output:

397
398
400
400
401
401
401
401
402
402
403
403
403
404
404
404
404
404
404
404

result:

ok 20 numbers

Test #20:

score: 2
Accepted
time: 9ms
memory: 3972kb

input:

50 100 5 20
46 43 21 23 4
3 5 11
12 15 69
4 36 49
7 29 22
39 19 83
19 40 87
8 12 16
35 20 15
20 23 100
50 13 6
9 21 42
41 26 72
29 43 13
43 48 71
13 23 77
3 28 45
18 13 99
14 41 18
48 30 11
22 40 80
18 8 57
12 42 69
41 6 61
48 26 47
43 15 4
46 20 58
22 36 16
38 22 16
40 36 67
9 25 68
11 16 23
29 24 ...

output:

336
337
339
340
341
342
342
343
343
343
344
344
344
344
345
345
345
346
346
346

result:

ok 20 numbers

Test #21:

score: 2
Accepted
time: 282ms
memory: 4016kb

input:

50 100 7 50
20 17 35 6 7 5 19
44 23 70
12 3 86
36 18 39
23 39 31
11 24 81
7 28 97
5 25 100
23 40 4
31 13 22
39 2 71
16 9 2
29 16 19
15 30 71
46 3 85
11 34 72
8 11 85
24 1 6
23 43 49
49 41 36
26 3 84
1 11 74
29 25 60
41 42 58
1 7 96
26 13 33
20 6 45
45 20 38
16 10 82
31 7 22
39 12 38
49 17 9
34 43 15...

output:

378
380
380
380
381
382
382
382
382
382
383
383
383
383
383
384
384
384
384
384
384
384
384
384
385
385
385
385
385
385
385
385
385
386
386
386
386
386
386
386
386
386
386
386
386
386
386
386
386
387

result:

ok 50 numbers

Test #22:

score: 2
Accepted
time: 36ms
memory: 4080kb

input:

50 100 7 50
46 50 26 5 20 44 21
29 5 89
35 48 71
9 1 8
50 12 56
21 26 49
21 4 33
44 35 7
17 8 6
17 44 73
32 44 56
49 36 63
32 15 11
40 31 8
11 34 34
45 36 26
13 48 42
12 25 72
36 23 80
14 12 86
50 15 4
30 50 74
21 20 44
41 32 12
48 37 72
4 44 20
45 23 70
34 21 24
20 30 1
22 18 83
18 34 69
29 37 56
2...

output:

342
343
343
344
344
345
345
345
345
346
346
346
346
346
346
346
347
347
347
347
347
347
347
347
347
347
347
348
348
348
348
348
348
348
348
348
348
348
348
348
348
348
348
348
348
349
349
349
349
349

result:

ok 50 numbers

Test #23:

score: 2
Accepted
time: 26ms
memory: 4020kb

input:

50 100 7 50
13 6 43 49 25 16 45
8 16 49
39 26 79
12 5 58
27 23 62
1 4 25
41 31 28
47 25 75
9 1 48
47 27 90
4 34 96
14 50 81
47 33 48
35 31 85
12 15 8
10 46 61
47 37 58
36 17 91
15 14 35
4 32 84
7 36 34
47 31 29
6 26 79
47 10 61
29 22 20
39 24 86
26 20 82
48 14 98
25 48 87
15 38 13
5 18 8
22 49 5
17 ...

output:

382
383
384
384
385
385
386
386
386
387
387
387
388
388
388
388
389
389
389
389
389
390
390
390
390
390
391
391
391
391
391
391
391
392
392
392
392
392
392
392
392
393
393
393
393
393
393
393
393
393

result:

ok 50 numbers

Test #24:

score: 2
Accepted
time: 323ms
memory: 4320kb

input:

50 100 7 50
29 30 10 12 11 50 7
21 20 8
50 46 2
8 11 44
27 45 16
21 45 25
30 36 7
5 13 50
6 23 53
27 46 14
19 12 7
34 45 49
19 43 79
33 48 20
42 37 76
6 33 61
9 41 3
37 41 52
33 19 76
34 10 83
41 24 87
31 26 9
14 16 78
11 46 1
39 32 99
13 4 5
33 37 59
2 27 69
45 8 7
26 34 57
30 35 43
9 47 59
1 50 72...

output:

344
344
345
345
345
345
346
346
348
349
349
349
349
350
350
350
350
350
351
351
351
351
351
352
352
352
352
352
352
352
352
352
352
352
353
353
353
353
353
353
353
353
353
353
353
353
353
353
353
353

result:

ok 50 numbers

Test #25:

score: 2
Accepted
time: 16ms
memory: 4004kb

input:

50 100 7 50
2 33 37 15 27 19 26
48 47 8
14 4 2
10 17 7
13 17 63
3 18 88
29 3 24
13 1 76
21 46 92
12 9 8
7 9 97
48 30 2
13 50 78
7 37 52
49 26 25
6 39 10
3 30 14
7 21 11
28 36 20
11 34 66
13 6 35
9 20 53
41 27 86
25 48 44
22 26 28
17 34 53
2 47 14
19 45 64
30 43 61
47 32 6
31 15 33
18 33 30
10 13 22
...

output:

336
337
337
337
338
338
338
338
338
338
339
339
339
339
339
339
339
339
339
339
340
340
340
340
340
340
340
340
340
340
340
340
341
341
341
341
341
341
341
341
341
341
341
341
342
342
342
342
342
342

result:

ok 50 numbers

Test #26:

score: 0
Time Limit Exceeded

input:

50 100 9 50
21 23 42 49 11 28 22 10 4
40 15 75
33 48 66
6 3 43
39 28 59
6 27 61
20 5 90
28 32 26
30 31 70
47 38 78
29 50 7
50 2 3
49 35 4
17 5 36
44 26 46
43 40 4
24 5 84
22 37 61
39 37 55
30 9 78
31 37 76
42 25 35
8 25 83
37 12 62
15 40 82
27 15 86
37 2 44
14 15 2
45 46 99
35 12 28
19 5 94
1 24 23
...

output:



result:




Test #27: 
score: 2
Accepted
time: 340ms
memory: 4236kb


input:
50 100 9 50
8 47 44 13 25 48 30 18 33
20 27 9
10 16 100
8 10 59
2 38 82
40 13 5
35 45 14
7 37 49
22 35 41
28 5 55
18 16 80
41 13 53
30 7 61
16 45 97
22 16 12
7 4 90
15 42 25
45 22 56
42 40 76
24 18 6
10 23 67
49 13 16
40 15 64
18 31 97
30 24 76
29 46 6
7 13 85
11 33 41
7 41 80
29 43 81
49 8 2
49 21 ...



output:
267
268
273
273
274
274
274
275
276
276
277
277
279
279
279
279
280
280
280
280
280
280
281
281
281
282
282
282
282
282
283
283
283
283
283
284
284
285
285
285
285
285
285
285
285
286
286
286
286
286




result:
ok 50 numbers






Test #28: 
score: 2
Accepted
time: 168ms
memory: 4160kb


input:
50 100 9 50
47 24 34 41 30 7 10 22 31
44 21 42
18 23 31
31 2 68
30 33 59
3 5 37
29 45 99
38 47 68
21 29 74
8 39 2
16 6 43
30 41 40
32 24 32
46 22 25
10 6 18
15 23 15
50 34 99
12 9 4
32 36 3
5 34 7
7 39 38
45 44 70
27 26 58
39 2 24
8 37 95
5 48 25
6 35 38
46 12 63
46 26 30
41 18 26
31 9 57
15 35 14
3...



output:
391
393
393
394
395
395
396
396
397
397
397
398
398
399
399
399
400
400
400
400
401
401
401
402
402
402
402
402
403
403
403
403
403
403
404
404
404
404
404
404
404
405
405
405
405
405
405
405
405
406




result:
ok 50 numbers






Test #29: 
score: 0
Time Limit Exceeded


input:
50 100 9 50
11 32 36 40 2 14 9 13 41
1 30 19
20 23 95
47 20 32
3 27 53
41 47 27
5 44 97
5 33 4
25 22 63
30 23 4
39 13 59
20 24 34
31 43 6
1 40 28
22 32 55
25 2 85
14 24 46
25 47 94
4 17 18
11 6 87
35 17 22
19 37 15
33 21 52
26 14 99
19 22 90
41 36 35
38 9 57
18 6 92
38 35 21
15 22 28
46 41 35
26 3 8...



output:
534
535
536
537
537
538
538
538
538
538
539
539
539
539
539
540
540
540
540
540
540
540
541
541
541
541
541
541
541
541
541
541
542
542
542
542
542
542
542
542
542
542
542
542
542
543
543
543
543
543




result:




Test #30: 
score: 2
Accepted
time: 680ms
memory: 4472kb


input:
50 100 9 50
20 9 11 44 28 26 47 31 40
25 36 51
50 26 36
26 20 40
45 15 31
16 5 71
46 2 86
14 44 24
10 15 88
2 27 31
7 20 28
33 36 96
13 16 71
27 11 64
9 6 74
45 16 4
11 36 30
22 4 71
26 32 4
15 8 81
33 14 65
44 50 76
40 42 98
45 11 3
31 49 87
17 49 41
49 30 7
14 11 100
38 11 39
31 19 96
37 47 43
23 ...



output:
329
331
333
333
334
334
334
335
335
336
336
336
336
337
338
338
338
338
338
338
338
339
339
339
339
340
340
340
340
340
340
340
340
340
341
341
341
341
341
341
341
341
341
342
342
342
342
342
342
343




result:
ok 50 numbers






Test #31: 
score: 0
Time Limit Exceeded


input:
50 100 10 50
27 48 35 40 33 34 26 5 21 10
44 45 75
34 17 97
29 7 71
13 35 50
23 1 99
18 21 22
13 3 21
24 12 32
39 46 65
5 6 23
42 4 35
3 12 41
42 30 81
38 41 26
2 20 8
9 28 27
45 25 66
16 41 85
9 29 89
9 24 65
50 4 8
17 49 10
50 43 22
31 12 47
14 47 10
39 47 63
32 13 50
8 20 63
26 43 29
46 3 21
28 2...



output:
587
590
591
594
595
596
597
597
597
598
598
599
599
600
600
600
600
601
601
601
601
602
602
602
603
603
604
604
604
604
605
605
605
605
605
605
605
605
606
606
606
606
606
606
607
607
607
607
607
607




result:




Test #32: 
score: 0
Time Limit Exceeded


input:
50 100 10 50
23 16 2 22 32 8 48 26 6 41
5 41 68
3 49 90
42 50 10
10 14 20
25 38 18
47 50 25
15 11 18
41 47 33
15 34 88
33 10 92
20 40 34
26 6 4
6 31 44
41 9 60
44 28 83
48 20 72
24 3 83
20 8 69
39 42 63
36 20 8
24 40 22
6 28 81
39 27 12
13 50 80
47 31 87
19 43 33
50 37 26
17 46 69
10 32 8
41 46 85
1...



output:


result:




Test #33: 
score: 2
Accepted
time: 828ms
memory: 4696kb


input:
50 100 10 50
39 40 19 16 42 10 15 11 41 49
6 45 60
22 14 61
5 39 63
43 47 5
38 18 12
32 5 71
16 7 12
12 17 3
37 42 41
49 15 24
23 7 54
35 44 40
31 41 21
14 7 10
25 9 88
44 15 14
11 19 92
25 10 27
8 15 78
48 23 36
40 46 55
9 50 83
25 1 90
47 25 35
31 40 95
43 20 30
22 10 21
36 46 36
24 45 79
25 23 73...



output:
349
349
350
350
350
351
351
351
351
351
351
352
352
352
352
352
352
352
352
352
353
353
353
353
353
353
353
353
353
353
353
354
354
354
354
354
354
354
354
354
354
354
354
354
354
354
354
355
355
355




result:
ok 50 numbers






Test #34: 
score: 2
Accepted
time: 956ms
memory: 4340kb


input:
50 100 10 50
49 17 43 20 44 4 30 8 27 25
21 44 71
2 46 23
10 12 56
49 34 64
22 19 38
13 28 59
22 19 58
45 23 78
16 38 34
29 24 73
3 29 65
47 20 15
24 38 99
14 18 11
35 33 54
40 9 56
28 3 36
46 47 88
36 45 37
3 39 93
7 5 26
32 22 20
47 36 84
1 43 96
17 46 56
30 18 95
50 44 2
49 41 6
19 49 42
38 21 60...



output:
552
553
554
555
557
558
559
560
562
563
563
563
564
564
564
565
565
565
565
566
566
566
566
567
567
567
567
567
567
568
568
568
568
568
568
568
568
569
569
569
569
569
569
569
569
570
570
570
570
570




result:
ok 50 numbers






Test #35: 
score: 0
Time Limit Exceeded


input:
50 100 10 50
4 49 21 34 3 29 15 26 25 5
26 46 16
24 31 100
33 9 84
10 33 60
47 22 71
15 47 5
30 4 92
25 1 39
33 44 74
42 19 86
39 32 85
6 18 73
9 50 85
33 12 11
2 43 80
39 34 85
3 26 70
9 30 9
32 17 59
18 16 82
1 46 74
49 18 13
29 37 38
28 11 76
13 30 38
9 39 4
20 43 65
13 24 9
37 6 25
35 42 72
20 1...



output:


result:




Test #36: 
score: 0
Time Limit Exceeded


input:
50 100 11 50
29 39 18 8 37 48 41 40 36 30 10
39 43 6
24 9 1
43 9 83
35 26 35
25 43 55
26 46 57
33 37 36
35 30 27
1 27 91
49 15 55
14 15 16
7 14 9
5 10 83
11 10 83
23 42 83
50 11 22
41 11 86
20 26 76
1 40 80
11 48 6
43 1 99
25 28 20
28 4 98
16 19 21
47 44 97
4 46 79
12 42 36
26 15 6
50 30 50
29 24 7
...



output:


result:




Test #37: 
score: 0
Time Limit Exceeded


input:
50 100 11 50
42 46 39 7 27 15 48 32 1 13 44
7 12 88
7 23 42
24 6 88
3 21 58
17 11 74
41 22 80
50 11 44
43 40 19
32 50 40
43 31 32
10 37 66
39 21 25
18 3 49
47 43 8
12 29 14
21 28 19
20 44 4
9 45 51
30 25 32
18 1 71
28 16 14
26 31 44
13 27 90
28 15 90
18 50 96
26 42 17
1 39 10
50 31 47
5 47 69
18 43 ...



output:


result:




Test #38: 
score: 0
Time Limit Exceeded


input:
50 100 11 50
49 43 16 39 18 23 46 6 17 48 45
21 13 56
31 42 56
18 19 66
15 20 96
49 42 72
5 16 52
45 32 37
10 12 84
43 34 1
17 23 57
36 41 10
49 34 86
33 3 16
23 38 97
45 34 10
9 47 65
46 20 33
25 9 66
50 22 83
3 50 11
12 33 80
47 44 14
21 29 72
39 2 36
15 5 1
7 14 78
10 34 13
28 23 41
18 22 5
15 28...



output:


result:




Test #39: 
score: 0
Time Limit Exceeded


input:
50 100 11 50
5 22 10 6 18 4 47 41 11 21 3
33 13 37
22 39 10
38 29 82
29 9 82
25 37 42
22 38 84
36 47 87
31 13 4
35 5 29
41 21 14
4 36 17
30 27 43
22 14 26
34 3 37
32 43 54
17 41 7
10 16 67
24 4 99
2 24 12
47 5 30
27 26 85
2 13 44
15 34 35
34 13 82
35 11 46
25 4 80
6 31 25
8 26 100
45 38 6
25 37 96
3...



output:


result:




Test #40: 
score: 0
Time Limit Exceeded


input:
50 100 11 50
12 1 20 15 29 7 4 37 16 43 21
23 12 88
47 10 21
41 14 60
3 43 86
43 41 71
22 2 88
48 43 25
33 46 86
16 41 49
7 6 52
36 11 51
4 34 90
27 30 85
33 36 68
41 24 57
22 35 56
36 33 48
34 39 70
49 21 11
7 28 42
22 4 55
29 12 17
28 41 96
5 44 35
26 5 50
2 27 34
2 49 70
23 44 81
9 41 44
41 45 23...



output:
435
439
442
443
446
446
447
447
447
448
449
449
450
450
451
451
452
452
453
453
453
453
453
454
454
454
454
455
455
455
455
456
456
456
456
456
456
457
457
457
457
457
457
458
458
458
458
458
459
459




result:




Test #41: 
score: 0
Time Limit Exceeded


input:
50 100 13 50
13 38 50 3 22 2 7 34 4 1 35 24 11
33 11 65
25 29 6
3 10 100
30 15 60
7 6 36
6 15 44
18 17 78
5 8 32
24 18 35
50 39 78
16 9 92
1 16 98
20 23 44
49 46 84
11 35 43
1 46 67
31 40 8
28 21 91
24 39 54
21 22 21
40 1 96
39 9 19
12 49 85
41 7 37
7 26 91
45 35 43
37 14 31
7 10 12
12 16 29
18 43 5...



output:


result:




Test #42: 
score: 0
Time Limit Exceeded


input:
50 100 13 50
33 6 12 26 49 19 29 43 4 8 9 40 2
9 47 74
39 11 93
49 10 15
45 5 96
19 24 30
46 34 57
48 37 37
26 46 65
42 38 13
4 32 30
37 18 51
31 28 42
38 11 49
35 9 26
43 38 72
48 8 20
10 48 80
7 13 30
8 7 69
45 4 11
50 12 38
29 20 23
33 31 84
46 2 12
26 42 53
44 17 37
39 7 86
10 23 26
45 9 42
27 5...



output:


result:




Test #43: 
score: 0
Time Limit Exceeded


input:
50 100 13 50
35 41 27 42 19 32 29 34 37 12 33 24 1
16 12 8
33 18 3
27 16 88
3 36 22
11 43 74
28 38 24
14 50 20
43 35 68
25 15 74
28 41 5
48 41 1
22 47 64
43 5 1
27 25 89
3 37 28
47 45 5
32 35 3
31 41 30
44 17 5
11 27 100
13 19 52
2 31 63
15 28 1
25 41 24
42 30 11
18 35 54
46 25 53
17 34 43
42 49 55
...



output:


result:




Test #44: 
score: 0
Time Limit Exceeded


input:
50 100 13 50
45 18 1 27 3 20 47 33 40 43 14 8 19
2 1 74
4 46 12
25 30 52
39 46 42
27 32 98
28 48 3
9 29 41
17 45 30
48 30 55
15 46 25
16 44 34
28 25 9
17 27 80
2 31 61
22 46 79
8 42 33
47 49 3
13 47 43
19 41 1
20 50 75
1 9 90
36 20 52
27 41 65
9 14 63
46 29 25
29 31 19
31 3 77
40 4 64
48 26 93
5 4 3...



output:


result:




Test #45: 
score: 0
Time Limit Exceeded


input:
50 100 13 50
8 44 22 27 35 10 1 38 43 15 2 21 16
8 34 69
19 39 27
41 6 31
3 11 65
13 22 44
36 34 82
9 41 63
13 43 90
34 28 38
13 49 64
48 16 72
12 38 22
1 28 27
25 32 66
21 40 67
34 20 98
23 49 56
47 7 62
28 40 22
18 31 12
21 1 33
10 24 43
14 26 43
15 31 38
14 12 59
41 30 71
28 27 26
5 17 81
41 2 42...



output:


result:




Test #46: 
score: 0
Time Limit Exceeded


input:
50 100 15 50
34 27 46 43 48 6 1 38 14 49 18 23 37 31 5
50 5 30
26 7 49
41 35 29
1 27 44
25 21 13
35 8 63
48 18 30
42 18 96
39 45 69
31 33 80
46 27 72
2 48 1
22 26 52
15 42 9
19 43 49
13 23 26
33 9 7
47 48 87
28 32 62
1 47 78
12 38 89
6 26 99
47 29 13
44 17 98
40 23 59
42 15 79
47 14 47
47 11 42
36 4...



output:


result:




Test #47: 
score: 0
Time Limit Exceeded


input:
50 100 15 50
1 33 12 38 3 22 45 36 26 29 43 9 34 20 23
22 9 49
17 7 88
46 14 87
40 2 73
46 26 24
5 32 78
26 47 100
19 36 50
48 26 35
49 18 60
50 45 50
39 16 14
26 39 2
6 3 26
41 16 78
40 22 10
21 12 73
42 27 95
50 31 27
19 37 38
40 17 45
36 46 88
46 7 17
6 37 1
18 44 52
39 8 54
14 50 2
14 47 76
23 3...



output:


result:




Test #48: 
score: 0
Time Limit Exceeded


input:
50 100 15 50
35 47 41 42 23 43 22 30 31 29 48 32 16 50 5
38 34 53
9 18 19
28 47 91
23 31 10
10 30 5
46 24 1
2 50 93
23 36 23
15 44 66
25 36 11
23 25 28
17 31 15
11 9 71
5 41 58
20 41 72
32 35 71
31 6 23
41 16 24
42 37 36
11 30 44
25 46 28
26 28 9
27 45 61
14 3 67
47 31 16
9 25 12
23 35 39
5 40 86
40...



output:


result:




Test #49: 
score: 0
Time Limit Exceeded


input:
50 100 15 50
27 34 4 36 16 17 1 7 28 46 30 32 21 41 2
4 39 55
1 34 77
16 22 68
35 31 37
16 28 99
27 28 99
43 27 33
48 15 88
24 7 82
29 46 57
50 20 13
37 40 48
49 14 32
28 2 73
29 22 54
40 7 98
10 2 17
3 31 79
33 18 69
50 7 27
12 20 16
29 4 12
6 45 26
29 28 15
4 47 27
44 32 8
9 34 74
14 13 42
45 28 7...



output:


result:




Test #50: 
score: 0
Time Limit Exceeded


input:
50 100 15 50
29 33 17 27 13 4 20 45 40 41 48 28 15 42 12
1 40 30
37 38 16
22 17 70
37 9 78
16 29 72
44 36 36
25 50 38
8 43 6
15 11 7
16 25 31
17 46 24
35 12 87
16 35 3
7 2 92
11 15 19
39 13 95
26 27 84
17 50 63
8 14 48
28 15 42
9 34 18
23 49 98
43 27 4
32 4 15
32 36 13
12 18 34
3 38 31
50 48 89
15 2...



output:


result:




					

	




			

						

				

					
					

						English
						繁體中文
						简体中文
					

				

				
				
				
Server Time: 2025-03-06 13:51:07 | OpenSource Project