oj.uz

Submission #1041045

# Submission time Handle Problem Language Result Execution time Memory
1041045 2024-08-01T14:14:03 Z RecursiveCo Closing Time (IOI23_closing) C++17
52 / 100
 71 ms 31068 KB 
// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long int

template <typename T, typename I>
struct segtree {
    int n;
    vector<T> tree;
    vector<I> initial;
    T id;

    segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) {
        tree.resize(4 * n);
    }

    T conquer(T left, T right) {
        // write your conquer function
    }

    T value(I inp) {
        // write your value function
    }

    void build(int v, int l, int r) {
        if (l == r) tree[v] = value(initial[l]);
        else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int v, int l, int r, int i, I x) {
        if (l == r) tree[v] = value(x);
        else {
            int middle = (l + r) / 2;
            if (middle >= i) upd(2 * v, l, middle, i, x);
            else upd(2 * v + 1, middle + 1, r, i, x);
            tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
        }
    }

    T query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        else if (r < ql || qr < l) return id;
        int middle = (l + r) / 2;
        T left = query(2 * v, l, middle, ql, qr);
        T right = query(2 * v + 1, middle + 1, r, ql, qr);
        return conquer(left, right);
    }
};

// vector<int>

vector<vector<pair<int, int>>> adjList;
vector<long long> fromX;
vector<long long> fromY;

vector<vector<long long>> arrays;

void dfs(int v, int p, long long d, int which) {
    if (which) fromY[v] = d;
    else fromX[v] = d;
    for (auto pa: adjList[v]) {
        int con = pa.first;
        long long w = pa.second;
        if (con == p) continue;
        dfs(con, v, d + w, which);
    }
}

void comp(int v, int p1, int p2, long long d, long long add) {
    arrays.back().push_back(add + d);
    for (auto pa: adjList[v]) {
        int con = pa.first;
        long long w = pa.second;
        if (con == p1 || con == p2) continue;
        comp(con, v, -1, d + w, add);
    }
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    adjList.clear();
    adjList.resize(N);
    fromX.clear();
    fromX.resize(N);
    fromY.clear();
    fromY.resize(N);
    forto(N - 1, i) {
        int a = U[i];
        int b = V[i];
        int w = W[i];
        adjList[a].push_back({b, w});
        adjList[b].push_back({a, w});
    }
    bool path = true;
    forto(N - 1, i) if (V[i] - U[i] != 1) path = false;
    dfs(X, -1, 0ll, 0);
    dfs(Y, -1, 0ll, 1);
    int ans = 0;
    if (fromY[X] > 2 * K) {
        vector<long long> paths;
        forto(N, i) {
            paths.push_back(min(fromX[i], fromY[i]));
        }
        sortl(paths);
        long long sum = 0;
        forto(N, i) {
            if (sum + paths[i] > K) break;
            sum += paths[i];
            ans++;
        }
    } else if (path) {
        long long C = fromX[Y]; // = fromY[X]
        // CASE 1: Stuff gets taken twice on both sides.
        // Everything in the middle gets taken twice.
        // Greedy/bruteforce on the sides.
        int ans1 = 0;
        long long sum1 = 0;
        int middle1 = 0;
        vector<long long> sides1;
        forto(N, i) {
            long long val = max(fromX[i], fromY[i]);
            if (val < C) sum1 += val, middle1++;
            else sides1.push_back(min(fromX[i], fromY[i]));
        }
        sortl(sides1);
        int s1 = sides1.size();
        if (sum1 <= K) ans1 = max(ans1, 2 * middle1);
        forto(s1, i) {
            if (sum1 + sides1[i] > K) break;
            sum1 += sides1[i];
            long long extral = (K - sum1) / C;
            int extra;
            if (extral > (long long) i + 1) extra = i + 1;
            else extra = (int) extral;
            ans1 = max(ans1, 2 * middle1 + (i + 1) + extra);
        }

        // CASE 2: Stuff gets taken twice on one of the two sides.
        // Everything in the middle gets taken once.
        // Suppose wlog the twice-taken stuff occurs on Y's side, then some suffix spanning to at least the halfway point of the middle must get taken twice.
        // CASE 2.1: On Y's side.
        int ans21 = 0;
        long long sum21 = 0;
        int middle21 = 0;
        vector<long long> delta21;
        vector<long long> side21;
        forto(N, i) {
            long long val = min(fromX[i], fromY[i]);
            if (max(fromX[i], fromY[i]) < C) sum21 += val, middle21++;
            if (max(fromX[i], fromY[i]) < C) {
                if (2 * fromY[i] <= C) sum21 += max(fromX[i], fromY[i]) - val, middle21++;
                else delta21.push_back(fromY[i] - fromX[i]);
            } else if (fromX[i] <= fromY[i]) {
                delta21.push_back(fromX[i]);
            } else {
                side21.push_back(fromY[i]);
            }
        }
        sortl(delta21);
        sortl(side21);
        if (sum21 <= K) ans21 = max(ans21, middle21);
        int ds21 = delta21.size();
        int s21 = side21.size();
        forto(ds21, i) {
            if (sum21 + delta21[i] > K) break;
            ans21 = max(ans21, middle21 + (i + 1));
            sum21 += delta21[i];
            long long here = sum21;
            forto(s21, j) {
                if (here + side21[j] > K) break;
                here += side21[j];
                long long extral = (K - here) / C;
                int extra;
                if (extral > (long long) j + 1) extra = j + 1;
                else extra = (int) extral;
                ans21 = max(ans21, middle21 + (i + 1) + (j + 1) + extra);
            }
        }

        // CASE 2.2: On X's side.
        int ans22 = 0;
        long long sum22 = 0;
        int middle22 = 0;
        vector<long long> delta22;
        vector<long long> side22;
        forto(N, i) {
            long long val = min(fromX[i], fromY[i]);
            if (max(fromX[i], fromY[i]) < C) sum22 += val, middle22++;
            if (max(fromX[i], fromY[i]) < C) {
                if (2 * fromX[i] <= C) sum22 += max(fromX[i], fromY[i]) - val, middle22++;
                else delta22.push_back(fromX[i] - fromY[i]);
            } else if (fromY[i] <= fromX[i]) {
                delta22.push_back(fromY[i]);
            } else {
                side22.push_back(fromX[i]);
            }
        }
        sortl(delta22);
        sortl(side22);
        if (sum22 <= K) ans22 = max(ans22, middle22);
        int ds22 = delta22.size();
        int s22 = side22.size();
        forto(ds22, i) {
            if (sum22 + delta22[i] > K) break;
            ans22 = max(ans22, middle22 + (i + 1));
            sum22 += delta22[i];
            long long here = sum22;
            forto(s22, j) {
                if (here + side22[j] > K) break;
                here += side22[j];
                long long extral = (K - here) / C;
                int extra;
                if (extral > (long long) j + 1) extra = j + 1;
                else extra = (int) extral;
                ans22 = max(ans22, middle22 + (i + 1) + (j + 1) + extra);
            }
        }

        // CASE 3: Nothing on the sides gets taken twice.
        // Then we greedy on the sides while solving the problem in the middle.
        // Yeah O(n^2log(n)) passes. Pretty sure.
        int ans3 = 0;
        vector<long long> sides3;
        vector<long long> midsmall3;
        vector<long long> middelta3;
        long long midsum3 = 0;
        forto(N, i) {
            long long val = max(fromX[i], fromY[i]);
            if (val < C) {
                midsmall3.push_back(min(fromX[i], fromY[i]));
                middelta3.push_back(val - min(fromX[i], fromY[i]));
                midsum3 += min(fromX[i], fromY[i]);
            } else {
                sides3.push_back(min(fromX[i], fromY[i]));
            }
        }
        sortl(sides3);
        sortl(midsmall3);
        sortl(middelta3);
        int s3 = sides3.size();
        int ms3 = midsmall3.size();
        int md3 = middelta3.size();
        long long sum3 = 0;
        forto(s3, i) {
            if (sum3 + sides3[i] > K) break;
            sum3 += sides3[i];
            ans3 = max(ans3, i + 1);
            long long tot = sum3;
            forto(ms3, j) {
                if (tot + midsmall3[j] > K) break;
                tot += midsmall3[j];
                ans3 = max(ans3, (i + 1) + (j + 1));
            }
            if (sum3 + midsum3 <= K) {
                ans3 = max(ans3, (i + 1) + ms3);
                long long higher = sum3 + midsum3;
                forto(md3, j) {
                    if (higher + middelta3[j] > K) break;
                    higher += middelta3[j];
                    ans3 = max(ans3, (i + 1) + ms3 + (j + 1));
                }
            }
        }

        ans = max({ans1, ans21, ans22, ans3});
    } else {
        long long C = fromX[Y]; // = fromY[X]
        vector<pair<long long, int>> mainpath;
        forto(N, i) {
            if (fromX[i] + fromY[i] == C) mainpath.push_back({fromX[i], i});
        }
        sortl(mainpath);
        int l = mainpath.size();
        forto(l, i) {
            vector<long long> here;
            arrays.push_back(here);
            int v = mainpath[i].second;
            comp(v, i? mainpath[i - 1].second: -1, i < l - 1? mainpath[i + 1].second: -1, 0ll, min(fromX[v], fromY[v]));
            sortl(arrays.back());
        }

        // CASE 1: All ones.
        // In this case, a simple greedy algorithm suffices.
        int ans1 = 0;
        vector<long long> ones1;
        forto(N, i) ones1.push_back(min(fromX[i], fromY[i]));
        sortl(ones1);
        long long sum1 = 0ll;
        forto(N, i) {
            if (sum1 + ones1[i] > K) break;
            sum1 += ones1[i];
            ans1++;
        }

        // CASE 2: Not all ones.
        // In this case, we can run a DP.
        vector<vector<long long>> dp(3, vector<long long>(2 * N + 1, 1e18 + 5));
        vector<vector<long long>> newdp(3, vector<long long>(2 * N + 1, 1e18 + 5));
        dp[0][0] = 0;
        forto(l, i) {
            forto(3, j) forto(2 * N + 1, k) newdp[j][k] = 1e18 + 5;
            int v = mainpath[i].second;
            long long mini = min(fromX[v], fromY[v]);
            long long maxi = max(fromX[v], fromY[v]);
            long long delta = maxi - mini;
            int sz = arrays[i].size();
            vector<long long> min1(2 * sz + 1, 1e18 + 5);
            vector<long long> min2(2 * sz + 1, 1e18 + 5);
            long long sum = 0ll;
            forto(sz, j) {
                sum += arrays[i][j];
                min1[j + 1] = sum;
                long long for2 = sum;
                forto(j + 1, k) {
                    for2 += delta;
                    min2[(j + 1) + (k + 1)] = min(min2[(j + 1) + (k + 1)], for2);
                }
            }
            forto(2 * N + 1, j) {
                if (j < i) continue;
                forto(2 * sz + 1, k) {
                    if (k == 0) continue;
                    if (j + k > 2 * N) break;
                    newdp[0][j + k] = min(newdp[0][j + k], dp[0][j] + min1[k]);
                    newdp[1][j + k] = min(newdp[1][j + k], min(dp[0][j], dp[1][j]) + min2[k]);
                    newdp[2][j + k] = min(newdp[2][j + k], min(dp[1][j], dp[2][j]) + min1[k]);
                }
            }

            swap(dp, newdp);
        }
        int ans2 = 0;
        forto(2 * N + 1, i) {
            long long mincost = min({dp[0][i], dp[1][i], dp[2][i]});
            if (mincost <= K) ans2 = i;
        }

        ans = max({ans1, ans2});
    }
    return ans;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:105:5: note: in expansion of macro 'forto'
  105 |     forto(N - 1, i) {
      |     ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:113:5: note: in expansion of macro 'forto'
  113 |     forto(N - 1, i) if (V[i] - U[i] != 1) path = false;
      |     ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:119:9: note: in expansion of macro 'forto'
  119 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:124:9: note: in expansion of macro 'forto'
  124 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:138:9: note: in expansion of macro 'forto'
  138 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:146:9: note: in expansion of macro 'forto'
  146 |         forto(s1, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:165:9: note: in expansion of macro 'forto'
  165 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:182:9: note: in expansion of macro 'forto'
  182 |         forto(ds21, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:187:13: note: in expansion of macro 'forto'
  187 |             forto(s21, j) {
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:204:9: note: in expansion of macro 'forto'
  204 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:221:9: note: in expansion of macro 'forto'
  221 |         forto(ds22, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:226:13: note: in expansion of macro 'forto'
  226 |             forto(s22, j) {
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:245:9: note: in expansion of macro 'forto'
  245 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:262:9: note: in expansion of macro 'forto'
  262 |         forto(s3, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:267:13: note: in expansion of macro 'forto'
  267 |             forto(ms3, j) {
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:275:17: note: in expansion of macro 'forto'
  275 |                 forto(md3, j) {
      |                 ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:287:9: note: in expansion of macro 'forto'
  287 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:292:9: note: in expansion of macro 'forto'
  292 |         forto(l, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:304:9: note: in expansion of macro 'forto'
  304 |         forto(N, i) ones1.push_back(min(fromX[i], fromY[i]));
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:307:9: note: in expansion of macro 'forto'
  307 |         forto(N, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:318:9: note: in expansion of macro 'forto'
  318 |         forto(l, i) {
      |         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:319:13: note: in expansion of macro 'forto'
  319 |             forto(3, j) forto(2 * N + 1, k) newdp[j][k] = 1e18 + 5;
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:319:25: note: in expansion of macro 'forto'
  319 |             forto(3, j) forto(2 * N + 1, k) newdp[j][k] = 1e18 + 5;
      |                         ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:328:13: note: in expansion of macro 'forto'
  328 |             forto(sz, j) {
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:332:17: note: in expansion of macro 'forto'
  332 |                 forto(j + 1, k) {
      |                 ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:337:13: note: in expansion of macro 'forto'
  337 |             forto(2 * N + 1, j) {
      |             ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:339:17: note: in expansion of macro 'forto'
  339 |                 forto(2 * sz + 1, k) {
      |                 ^~~~~
closing.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
closing.cpp:351:9: note: in expansion of macro 'forto'
  351 |         forto(2 * N + 1, i) {
      |         ^~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 26748 KB Output is correct
2 Correct 71 ms 31068 KB Output is correct
3 Correct 42 ms 2908 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 8 ms 924 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 7 ms 860 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 932 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 504 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 504 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Incorrect 1 ms 344 KB 2nd lines differ - on the 1st token, expected: '19', found: '17'
38 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 504 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Incorrect 1 ms 344 KB 2nd lines differ - on the 1st token, expected: '19', found: '17'
45 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 8 ms 924 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 7 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 1 ms 932 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 504 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Incorrect 1 ms 344 KB 2nd lines differ - on the 1st token, expected: '19', found: '17'
53 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 8 ms 924 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 7 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 1 ms 932 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 344 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 504 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Incorrect 1 ms 344 KB 2nd lines differ - on the 1st token, expected: '19', found: '17'
53 Halted 0 ms 0 KB -