oj.uz

Submission #590003

# Submission time Handle Problem Language Result Execution time Memory
590003 2022-07-05T12:59:48 Z Sam_a17 Shortcut (IOI16_shortcut) C++14
23 / 100
 2000 ms 4436 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include "shortcut_c.h"
#include <cstdio>
using namespace std;
#define ll long long

const int N = 2e3 + 10;
long long dist[N][N];
const ll inf = 1e16;
long long maxLeft[N], maxRight[N], kox[N];
long long maxLeftDiam[N], maxRightDiam[N];
multiset<pair<ll, long long>> adj[N];
vector<long long> pat[N];
int ni;

pair<long long, long long> djik(int node) {
  vector<bool> used(ni + 1);
  vector<long long> dist(ni + 1, inf);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>> > q;
  dist[node] = 0;
  q.push({0, node});
 
  while(!q.empty()) {
    auto u = q.top();
    q.pop();

    if(used[u.second]) {
      continue;
    }
    used[u.second] = true;

    for(auto i: adj[u.second]) {
      if(dist[i.first] > dist[u.second] + i.second) {
        dist[i.first] = dist[u.second] + i.second;
        q.push({dist[i.first], i.first});
      }
    }
  }

  pair<ll, ll> answ = {-1, -1};

  for(int i = 0; i < ni; i++) {
    if(dist[i] == inf) {
      assert(false);
    }

    if(dist[i] > answ.first) {
      answ = {dist[i], i};
    }
  }

  return answ;
}

void djik2(int node) {
  vector<bool> used(ni + 1);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>> > q;
  for(int i = 0; i < ni; i++) {
    dist[node][i] = inf;
  }
  dist[node][node] = 0;
  q.push({0, node});
 
  while(!q.empty()) {
    auto u = q.top();
    q.pop();

    if(used[u.second]) {
      continue;
    }
    used[u.second] = true;

    for(auto i: adj[u.second]) {
      if(dist[node][i.first] > dist[node][u.second] + i.second) {
        dist[node][i.first] = dist[node][u.second] + i.second;
        q.push({dist[node][i.first], i.first});
      }
    }
  }

  long long maxi = 0;
  for(int i = 0; i < ni; i++) {
    assert(dist[node][i] != inf);
    maxi = max(maxi, dist[node][i]);
  }

  for(int i = 0; i < ni; i++) {
    if(dist[node][i] == maxi) {
      pat[node].push_back(i);
    }
  }
}

void djik3(int node, vector<ll>& dist) {
  vector<bool> used(ni + 1);
  // vector<long long> dist(ni + 1, inf);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>> > q;
  dist[node] = 0;
  q.push({0, node});
 
  while(!q.empty()) {
    auto u = q.top();
    q.pop();

    if(used[u.second]) {
      continue;
    }
    used[u.second] = true;

    for(auto i: adj[u.second]) {
      if(dist[i.first] > dist[u.second] + i.second) {
        dist[i.first] = dist[u.second] + i.second;
        q.push({dist[i.first], i.first});
      }
    }
  }
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
  maxLeft[0] = d[0];
  for(int i = 1; i < n; i++) {
    maxLeft[i] = max(maxLeft[i - 1] + (long long)l[i - 1], (long long)d[i]); 
  }

  maxRight[n - 1] = d[n - 1];
  for(int i = n - 2; i >= 0; i--) {
    maxRight[i] = max(maxRight[i + 1] + (long long)l[i], (long long)d[i]);
  }

  maxLeftDiam[0] = maxLeft[0];
  for(int i = 1; i < n; i++) {
    maxLeftDiam[i] = max(maxLeftDiam[i - 1], maxLeft[i - 1] + (long long)l[i - 1] + (long long)d[i]);
  }

  maxRightDiam[n - 1] = maxRight[n - 1];
  for(int i = n - 2; i >= 0; i--) {
    maxRightDiam[i] = max(maxRightDiam[i + 1], maxRight[i + 1] + (long long)l[i] + (long long)d[i]);
  }

  ni = n;

  if(d[0]) {
    kox[0] = ni;
    adj[0].insert({ni, d[0]});
    adj[ni++].insert({0, d[0]});
  }

  for(int i = 1; i < n; i++) {

    adj[i - 1].insert({i, l[i - 1]});
    adj[i].insert({i - 1, l[i - 1]});

    if(d[i]) {
      kox[i] = ni;
      adj[i].insert({ni, d[i]});
      adj[ni++].insert({i, d[i]});
    }
  }

  for(int i = 0; i < ni; i++) {
    djik2(i);
  }

  long long minDiametr = djik(djik(0).second).first;

  for(int i = 0; i < n; i++) {
    long long s = 0;
    for(int j = i + 1; j < n; j++) {
      s += l[j - 1];

      if(s <= c) {
        continue;
      }

      adj[i].insert({j, (long long)c});
      adj[j].insert({i, (long long)c});

      vector<long long> d1(ni + 1, inf), d2(ni + 1, inf);

      djik3(i, d1);
      djik3(j, d2);
      
      long long maxi = max({maxLeftDiam[i], maxRightDiam[j], maxLeft[i] + maxRight[j] + c});
      
      for(int k = i; k <= j; k++) {
        if(kox[k]) {
          for(int g = 0; g < ni; g++) {
            if(min(d1[kox[k]] + d1[g], d2[kox[k]] + d2[g]) < dist[kox[k]][g]) {
              maxi = max(maxi, min(d1[kox[k]] + d1[g], d2[kox[k]] + d2[g]));
            } else {
              maxi = max(maxi, dist[kox[k]][g]);
            }
          }
        } else {
           for(int g = 0; g < ni; g++) {
            if(min(d1[k] + d1[g], d1[k] + d1[g]) < dist[k][g]) {
              maxi = max(maxi, min(d1[k] + d1[g], d1[k] + d1[g]));
            } else {
              maxi = max(maxi, dist[k][g]);
            }
          }
        }
      }
      minDiametr = min(maxi, minDiametr);

      adj[i].erase(adj[i].find(make_pair(j, (ll)c)));
      adj[j].erase(adj[j].find(make_pair(i, (ll)c)));
    }
  }

  return minDiametr;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer
39 Correct 1 ms 468 KB n = 2, 62 is a correct answer
40 Correct 0 ms 444 KB n = 2, 3 is a correct answer
41 Correct 1 ms 468 KB n = 3, 29 is a correct answer
42 Correct 1 ms 468 KB n = 2, 3 is a correct answer
43 Correct 1 ms 468 KB n = 2, 3 is a correct answer
44 Correct 1 ms 468 KB n = 2, 2000000001 is a correct answer
45 Correct 1 ms 444 KB n = 2, 3000000000 is a correct answer
46 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
47 Correct 1 ms 436 KB n = 3, 3000000000 is a correct answer
48 Correct 1 ms 448 KB n = 4, 3000000001 is a correct answer
49 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
50 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
51 Correct 1 ms 468 KB n = 10, 1000000343 is a correct answer
52 Correct 1 ms 452 KB n = 10, 3189 is a correct answer
53 Correct 1 ms 452 KB n = 10, 7000000000 is a correct answer
54 Correct 1 ms 448 KB n = 5, 12 is a correct answer
55 Correct 0 ms 468 KB n = 5, 25 is a correct answer
56 Correct 1 ms 468 KB n = 2, 122 is a correct answer
57 Correct 1 ms 448 KB n = 10, 117 is a correct answer
58 Correct 1 ms 452 KB n = 10, 336 is a correct answer
59 Correct 1 ms 468 KB n = 10, 438 is a correct answer
60 Correct 1 ms 468 KB n = 10, 206 is a correct answer
61 Correct 1 ms 468 KB n = 10, 636 is a correct answer
62 Correct 1 ms 468 KB n = 4, 2399 is a correct answer
63 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
64 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
65 Correct 131 ms 1604 KB n = 100, 51000000001 is a correct answer
66 Correct 20 ms 852 KB n = 50, 197881272 is a correct answer
67 Correct 192 ms 1608 KB n = 100, 20969 is a correct answer
68 Correct 202 ms 1600 KB n = 100, 20969 is a correct answer
69 Correct 109 ms 1592 KB n = 100, 52000000000 is a correct answer
70 Correct 195 ms 1524 KB n = 100, 285 is a correct answer
71 Correct 200 ms 1596 KB n = 100, 21272 is a correct answer
72 Correct 79 ms 1596 KB n = 100, 12161 is a correct answer

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer
39 Correct 1 ms 468 KB n = 2, 62 is a correct answer
40 Correct 0 ms 444 KB n = 2, 3 is a correct answer
41 Correct 1 ms 468 KB n = 3, 29 is a correct answer
42 Correct 1 ms 468 KB n = 2, 3 is a correct answer
43 Correct 1 ms 468 KB n = 2, 3 is a correct answer
44 Correct 1 ms 468 KB n = 2, 2000000001 is a correct answer
45 Correct 1 ms 444 KB n = 2, 3000000000 is a correct answer
46 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
47 Correct 1 ms 436 KB n = 3, 3000000000 is a correct answer
48 Correct 1 ms 448 KB n = 4, 3000000001 is a correct answer
49 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
50 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
51 Correct 1 ms 468 KB n = 10, 1000000343 is a correct answer
52 Correct 1 ms 452 KB n = 10, 3189 is a correct answer
53 Correct 1 ms 452 KB n = 10, 7000000000 is a correct answer
54 Correct 1 ms 448 KB n = 5, 12 is a correct answer
55 Correct 0 ms 468 KB n = 5, 25 is a correct answer
56 Correct 1 ms 468 KB n = 2, 122 is a correct answer
57 Correct 1 ms 448 KB n = 10, 117 is a correct answer
58 Correct 1 ms 452 KB n = 10, 336 is a correct answer
59 Correct 1 ms 468 KB n = 10, 438 is a correct answer
60 Correct 1 ms 468 KB n = 10, 206 is a correct answer
61 Correct 1 ms 468 KB n = 10, 636 is a correct answer
62 Correct 1 ms 468 KB n = 4, 2399 is a correct answer
63 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
64 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
65 Correct 131 ms 1604 KB n = 100, 51000000001 is a correct answer
66 Correct 20 ms 852 KB n = 50, 197881272 is a correct answer
67 Correct 192 ms 1608 KB n = 100, 20969 is a correct answer
68 Correct 202 ms 1600 KB n = 100, 20969 is a correct answer
69 Correct 109 ms 1592 KB n = 100, 52000000000 is a correct answer
70 Correct 195 ms 1524 KB n = 100, 285 is a correct answer
71 Correct 200 ms 1596 KB n = 100, 21272 is a correct answer
72 Correct 79 ms 1596 KB n = 100, 12161 is a correct answer
73 Execution timed out 2069 ms 4436 KB Time limit exceeded
74 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer
39 Correct 1 ms 468 KB n = 2, 62 is a correct answer
40 Correct 0 ms 444 KB n = 2, 3 is a correct answer
41 Correct 1 ms 468 KB n = 3, 29 is a correct answer
42 Correct 1 ms 468 KB n = 2, 3 is a correct answer
43 Correct 1 ms 468 KB n = 2, 3 is a correct answer
44 Correct 1 ms 468 KB n = 2, 2000000001 is a correct answer
45 Correct 1 ms 444 KB n = 2, 3000000000 is a correct answer
46 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
47 Correct 1 ms 436 KB n = 3, 3000000000 is a correct answer
48 Correct 1 ms 448 KB n = 4, 3000000001 is a correct answer
49 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
50 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
51 Correct 1 ms 468 KB n = 10, 1000000343 is a correct answer
52 Correct 1 ms 452 KB n = 10, 3189 is a correct answer
53 Correct 1 ms 452 KB n = 10, 7000000000 is a correct answer
54 Correct 1 ms 448 KB n = 5, 12 is a correct answer
55 Correct 0 ms 468 KB n = 5, 25 is a correct answer
56 Correct 1 ms 468 KB n = 2, 122 is a correct answer
57 Correct 1 ms 448 KB n = 10, 117 is a correct answer
58 Correct 1 ms 452 KB n = 10, 336 is a correct answer
59 Correct 1 ms 468 KB n = 10, 438 is a correct answer
60 Correct 1 ms 468 KB n = 10, 206 is a correct answer
61 Correct 1 ms 468 KB n = 10, 636 is a correct answer
62 Correct 1 ms 468 KB n = 4, 2399 is a correct answer
63 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
64 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
65 Correct 131 ms 1604 KB n = 100, 51000000001 is a correct answer
66 Correct 20 ms 852 KB n = 50, 197881272 is a correct answer
67 Correct 192 ms 1608 KB n = 100, 20969 is a correct answer
68 Correct 202 ms 1600 KB n = 100, 20969 is a correct answer
69 Correct 109 ms 1592 KB n = 100, 52000000000 is a correct answer
70 Correct 195 ms 1524 KB n = 100, 285 is a correct answer
71 Correct 200 ms 1596 KB n = 100, 21272 is a correct answer
72 Correct 79 ms 1596 KB n = 100, 12161 is a correct answer
73 Execution timed out 2069 ms 4436 KB Time limit exceeded
74 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer
39 Correct 1 ms 468 KB n = 2, 62 is a correct answer
40 Correct 0 ms 444 KB n = 2, 3 is a correct answer
41 Correct 1 ms 468 KB n = 3, 29 is a correct answer
42 Correct 1 ms 468 KB n = 2, 3 is a correct answer
43 Correct 1 ms 468 KB n = 2, 3 is a correct answer
44 Correct 1 ms 468 KB n = 2, 2000000001 is a correct answer
45 Correct 1 ms 444 KB n = 2, 3000000000 is a correct answer
46 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
47 Correct 1 ms 436 KB n = 3, 3000000000 is a correct answer
48 Correct 1 ms 448 KB n = 4, 3000000001 is a correct answer
49 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
50 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
51 Correct 1 ms 468 KB n = 10, 1000000343 is a correct answer
52 Correct 1 ms 452 KB n = 10, 3189 is a correct answer
53 Correct 1 ms 452 KB n = 10, 7000000000 is a correct answer
54 Correct 1 ms 448 KB n = 5, 12 is a correct answer
55 Correct 0 ms 468 KB n = 5, 25 is a correct answer
56 Correct 1 ms 468 KB n = 2, 122 is a correct answer
57 Correct 1 ms 448 KB n = 10, 117 is a correct answer
58 Correct 1 ms 452 KB n = 10, 336 is a correct answer
59 Correct 1 ms 468 KB n = 10, 438 is a correct answer
60 Correct 1 ms 468 KB n = 10, 206 is a correct answer
61 Correct 1 ms 468 KB n = 10, 636 is a correct answer
62 Correct 1 ms 468 KB n = 4, 2399 is a correct answer
63 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
64 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
65 Correct 131 ms 1604 KB n = 100, 51000000001 is a correct answer
66 Correct 20 ms 852 KB n = 50, 197881272 is a correct answer
67 Correct 192 ms 1608 KB n = 100, 20969 is a correct answer
68 Correct 202 ms 1600 KB n = 100, 20969 is a correct answer
69 Correct 109 ms 1592 KB n = 100, 52000000000 is a correct answer
70 Correct 195 ms 1524 KB n = 100, 285 is a correct answer
71 Correct 200 ms 1596 KB n = 100, 21272 is a correct answer
72 Correct 79 ms 1596 KB n = 100, 12161 is a correct answer
73 Execution timed out 2069 ms 4436 KB Time limit exceeded
74 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer
39 Correct 1 ms 468 KB n = 2, 62 is a correct answer
40 Correct 0 ms 444 KB n = 2, 3 is a correct answer
41 Correct 1 ms 468 KB n = 3, 29 is a correct answer
42 Correct 1 ms 468 KB n = 2, 3 is a correct answer
43 Correct 1 ms 468 KB n = 2, 3 is a correct answer
44 Correct 1 ms 468 KB n = 2, 2000000001 is a correct answer
45 Correct 1 ms 444 KB n = 2, 3000000000 is a correct answer
46 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
47 Correct 1 ms 436 KB n = 3, 3000000000 is a correct answer
48 Correct 1 ms 448 KB n = 4, 3000000001 is a correct answer
49 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
50 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
51 Correct 1 ms 468 KB n = 10, 1000000343 is a correct answer
52 Correct 1 ms 452 KB n = 10, 3189 is a correct answer
53 Correct 1 ms 452 KB n = 10, 7000000000 is a correct answer
54 Correct 1 ms 448 KB n = 5, 12 is a correct answer
55 Correct 0 ms 468 KB n = 5, 25 is a correct answer
56 Correct 1 ms 468 KB n = 2, 122 is a correct answer
57 Correct 1 ms 448 KB n = 10, 117 is a correct answer
58 Correct 1 ms 452 KB n = 10, 336 is a correct answer
59 Correct 1 ms 468 KB n = 10, 438 is a correct answer
60 Correct 1 ms 468 KB n = 10, 206 is a correct answer
61 Correct 1 ms 468 KB n = 10, 636 is a correct answer
62 Correct 1 ms 468 KB n = 4, 2399 is a correct answer
63 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
64 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
65 Correct 131 ms 1604 KB n = 100, 51000000001 is a correct answer
66 Correct 20 ms 852 KB n = 50, 197881272 is a correct answer
67 Correct 192 ms 1608 KB n = 100, 20969 is a correct answer
68 Correct 202 ms 1600 KB n = 100, 20969 is a correct answer
69 Correct 109 ms 1592 KB n = 100, 52000000000 is a correct answer
70 Correct 195 ms 1524 KB n = 100, 285 is a correct answer
71 Correct 200 ms 1596 KB n = 100, 21272 is a correct answer
72 Correct 79 ms 1596 KB n = 100, 12161 is a correct answer
73 Execution timed out 2069 ms 4436 KB Time limit exceeded
74 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer
39 Correct 1 ms 468 KB n = 2, 62 is a correct answer
40 Correct 0 ms 444 KB n = 2, 3 is a correct answer
41 Correct 1 ms 468 KB n = 3, 29 is a correct answer
42 Correct 1 ms 468 KB n = 2, 3 is a correct answer
43 Correct 1 ms 468 KB n = 2, 3 is a correct answer
44 Correct 1 ms 468 KB n = 2, 2000000001 is a correct answer
45 Correct 1 ms 444 KB n = 2, 3000000000 is a correct answer
46 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
47 Correct 1 ms 436 KB n = 3, 3000000000 is a correct answer
48 Correct 1 ms 448 KB n = 4, 3000000001 is a correct answer
49 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
50 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
51 Correct 1 ms 468 KB n = 10, 1000000343 is a correct answer
52 Correct 1 ms 452 KB n = 10, 3189 is a correct answer
53 Correct 1 ms 452 KB n = 10, 7000000000 is a correct answer
54 Correct 1 ms 448 KB n = 5, 12 is a correct answer
55 Correct 0 ms 468 KB n = 5, 25 is a correct answer
56 Correct 1 ms 468 KB n = 2, 122 is a correct answer
57 Correct 1 ms 448 KB n = 10, 117 is a correct answer
58 Correct 1 ms 452 KB n = 10, 336 is a correct answer
59 Correct 1 ms 468 KB n = 10, 438 is a correct answer
60 Correct 1 ms 468 KB n = 10, 206 is a correct answer
61 Correct 1 ms 468 KB n = 10, 636 is a correct answer
62 Correct 1 ms 468 KB n = 4, 2399 is a correct answer
63 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
64 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
65 Correct 131 ms 1604 KB n = 100, 51000000001 is a correct answer
66 Correct 20 ms 852 KB n = 50, 197881272 is a correct answer
67 Correct 192 ms 1608 KB n = 100, 20969 is a correct answer
68 Correct 202 ms 1600 KB n = 100, 20969 is a correct answer
69 Correct 109 ms 1592 KB n = 100, 52000000000 is a correct answer
70 Correct 195 ms 1524 KB n = 100, 285 is a correct answer
71 Correct 200 ms 1596 KB n = 100, 21272 is a correct answer
72 Correct 79 ms 1596 KB n = 100, 12161 is a correct answer
73 Execution timed out 2069 ms 4436 KB Time limit exceeded
74 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 4, 80 is a correct answer
2 Correct 1 ms 468 KB n = 9, 110 is a correct answer
3 Correct 1 ms 468 KB n = 4, 21 is a correct answer
4 Correct 0 ms 468 KB n = 3, 4 is a correct answer
5 Correct 1 ms 468 KB n = 2, 62 is a correct answer
6 Correct 1 ms 468 KB n = 2, 3 is a correct answer
7 Correct 0 ms 468 KB n = 3, 29 is a correct answer
8 Correct 1 ms 468 KB n = 2, 3 is a correct answer
9 Correct 1 ms 468 KB n = 2, 3 is a correct answer
10 Correct 0 ms 468 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 468 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 468 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 468 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 468 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 468 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 468 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 424 KB n = 5, 12 is a correct answer
21 Correct 0 ms 468 KB n = 5, 25 is a correct answer
22 Correct 0 ms 468 KB n = 2, 122 is a correct answer
23 Correct 1 ms 468 KB n = 10, 117 is a correct answer
24 Correct 1 ms 468 KB n = 10, 336 is a correct answer
25 Correct 1 ms 468 KB n = 10, 438 is a correct answer
26 Correct 1 ms 444 KB n = 10, 206 is a correct answer
27 Correct 1 ms 468 KB n = 10, 636 is a correct answer
28 Correct 1 ms 452 KB n = 4, 2399 is a correct answer
29 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
30 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
31 Correct 117 ms 1600 KB n = 100, 51000000001 is a correct answer
32 Correct 20 ms 960 KB n = 50, 197881272 is a correct answer
33 Correct 192 ms 1596 KB n = 100, 20969 is a correct answer
34 Correct 195 ms 1600 KB n = 100, 20969 is a correct answer
35 Correct 109 ms 1600 KB n = 100, 52000000000 is a correct answer
36 Correct 137 ms 1532 KB n = 100, 285 is a correct answer
37 Correct 194 ms 1600 KB n = 100, 21272 is a correct answer
38 Correct 74 ms 1600 KB n = 100, 12161 is a correct answer
39 Correct 1 ms 468 KB n = 2, 62 is a correct answer
40 Correct 0 ms 444 KB n = 2, 3 is a correct answer
41 Correct 1 ms 468 KB n = 3, 29 is a correct answer
42 Correct 1 ms 468 KB n = 2, 3 is a correct answer
43 Correct 1 ms 468 KB n = 2, 3 is a correct answer
44 Correct 1 ms 468 KB n = 2, 2000000001 is a correct answer
45 Correct 1 ms 444 KB n = 2, 3000000000 is a correct answer
46 Correct 1 ms 468 KB n = 3, 3000000000 is a correct answer
47 Correct 1 ms 436 KB n = 3, 3000000000 is a correct answer
48 Correct 1 ms 448 KB n = 4, 3000000001 is a correct answer
49 Correct 1 ms 468 KB n = 4, 4000000000 is a correct answer
50 Correct 1 ms 468 KB n = 5, 4000000000 is a correct answer
51 Correct 1 ms 468 KB n = 10, 1000000343 is a correct answer
52 Correct 1 ms 452 KB n = 10, 3189 is a correct answer
53 Correct 1 ms 452 KB n = 10, 7000000000 is a correct answer
54 Correct 1 ms 448 KB n = 5, 12 is a correct answer
55 Correct 0 ms 468 KB n = 5, 25 is a correct answer
56 Correct 1 ms 468 KB n = 2, 122 is a correct answer
57 Correct 1 ms 448 KB n = 10, 117 is a correct answer
58 Correct 1 ms 452 KB n = 10, 336 is a correct answer
59 Correct 1 ms 468 KB n = 10, 438 is a correct answer
60 Correct 1 ms 468 KB n = 10, 206 is a correct answer
61 Correct 1 ms 468 KB n = 10, 636 is a correct answer
62 Correct 1 ms 468 KB n = 4, 2399 is a correct answer
63 Correct 1 ms 468 KB n = 10, 10992 is a correct answer
64 Correct 1 ms 468 KB n = 10, 3112 is a correct answer
65 Correct 131 ms 1604 KB n = 100, 51000000001 is a correct answer
66 Correct 20 ms 852 KB n = 50, 197881272 is a correct answer
67 Correct 192 ms 1608 KB n = 100, 20969 is a correct answer
68 Correct 202 ms 1600 KB n = 100, 20969 is a correct answer
69 Correct 109 ms 1592 KB n = 100, 52000000000 is a correct answer
70 Correct 195 ms 1524 KB n = 100, 285 is a correct answer
71 Correct 200 ms 1596 KB n = 100, 21272 is a correct answer
72 Correct 79 ms 1596 KB n = 100, 12161 is a correct answer
73 Execution timed out 2069 ms 4436 KB Time limit exceeded
74 Halted 0 ms 0 KB -