Submission #970075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
970075	2024-04-26T07:29:49 Z	Requiem	Financial Report (JOI21_financial)	C++17	100 / 100	1040 ms	23308 KB

Main

#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e9
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "financialreport"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
int a[MAXN], n, d;

namespace subtask1{
    bool checkSubtask1(){
         return n <= 20;
    }

    void solveSubtask1(){
         int res = 0;
         for(int msk = 0; msk < (1 << (n - 1)); msk++){
             int prv = -1, mx = -INF, valid = 1, cur = 0;
             for(int j = 0; j < n; j++){
                 if ((msk & (1 << j)) or j == n - 1) {

                     if (prv != -1 and j - prv > d) valid = 0;
                     if (maximize(mx, a[j + 1])){
                         cur++;
                     }
                     prv = j;
                 }
             }

             if (valid) maximize(res, cur);
         }
         cout << res << endl;
    }
}

namespace subtask2{
    bool checkSubtask2(){
         return n <= 400;
    }

    int dp[406][406];
    vector<int> listval;
    void computeDp1(){
         memset(dp, -0x3f, sizeof(dp));
         for(int i = 1; i <= n; i++){
             dp[i][i] = 1;
         }
         a[0] = -INF;
         for(int i = 0; i <= n; i++){ //regard i
             for(int j = 0; j <= n; j++){
                 if (dp[i][j] > -INF){
//                     cout << i << ' ' << j << ' ' << dp[i][j] << endl;
                     for(int k = i + 1; k <= min(i + d, n); k++){
                         int mxId = (a[j] >= a[k]) ? j : k;
                         if (mxId == k) maximize(dp[k][mxId], dp[i][j] + 1);
                         else maximize(dp[k][mxId], dp[i][j]);
                     }
                 }
             }
         }
         int res = 0;
         for(int i = 0; i <= n; i++){
             maximize(res, dp[n][i]);
         }
         cout << res << endl;
    }

    void computeDp2(){
         for(int i = 1; i <= n; i++){
             listval.pb(a[i]);
         }
         sort(listval.begin(), listval.end());
         listval.erase(unique(listval.begin(), listval.end()), listval.end());

    }
    void solveSubtask2(){
         computeDp1();
    }
}

namespace subtask3{
    int Valid[7003][7003];
    bool checkSubtask3(){
         return n <= 7000;
    }
    int dp[MAXN];

    void solveSubtask3(){
         memset(Valid, 0x3f, sizeof(Valid));
         deque<int> opt;

         for(int i = 1; i <= n; i++){
             Valid[i][i] = a[i];
             for(int j = i; j <= n; j++){
                 if (j - i <= d) Valid[i][j] = max(a[i], a[j]);
                 else minimize(Valid[i][j], max(Valid[i][opt.front()], a[j]) );

                 while(!opt.empty() and Valid[i][j] <= Valid[i][opt.back()]) opt.pop_back();
                 opt.push_back(j);
                 while(!opt.empty() and opt.front() + d <= j) {
                       opt.pop_front();
                 }
//                 cout << Valid[i][j] << ' ';
             }
             opt.clear();
//             cout << endl;
         }
         int res = 0;
         for(int i = 1; i <= n; i++){
             dp[i] = 1;
             for(int j = i - 1; j >= 1; j--){
                 if (Valid[j][i] <= a[i] and a[i] > a[j]) maximize(dp[i], dp[j] + 1);
             }
             maximize(res, dp[i]);
//             cout << dp[i] << ' ';
         }
//         cout << endl;
         cout << res << endl;
    }
}
namespace subtask4{
    bool checkSubtask4(){
         return d == 1;
    }

    void solveSubtask4(){
        stack<int> st;
        int res = 1;
        st.push(n);
        for(int i = n - 1; i >= 1; i--){
            while(!st.empty() and a[i] >= a[st.top()]) st.pop();
            st.push(i);
            maximize(res, (int) st.size());
        }
        cout << res << endl;
    }
}

namespace subtask5{
    bool checkSubtask5(){
        return d == n;
    }

    int dp[MAXN];

    void solveSubtask5(){
        multiset<int> st;
        int res = 0;
        for(int i = 1; i <= n; i++){
            auto it = st.lower_bound(a[i]);
//            cout << st.size() << ' ' << i << endl;
            if (it == st.end()) st.insert(a[i]);
            else {
                st.erase(it);
                st.insert(a[i]);
            }
        }

        cout << (int) st.size() << endl;
    }
}

struct DSU{
    int par[MAXN], ranking[MAXN], ending[MAXN];
    multiset<int> component;

    void reset(){
         for(int i = 1; i <= n; i++){
             ending[i] = i;
             ranking[i] = 1;
             par[i] = i;
         }
    }
    int root(int u){
        if (par[u] == u) return u;
        else return par[u] = root(par[u]);
    }
    void unite(int u,int v){
        u = root(u);
        v = root(v);
        if (u != v){
            if (ranking[u] >= d) component.erase(ending[u]);
            if (ranking[v] >= d) component.erase(ending[v]);
            if (ranking[u] < ranking[v]) swap(u, v);
            par[v] = u;
            ranking[u] += ranking[v];
            maximize(ending[u], ending[v]);
            if (ranking[u] >= d) component.insert(ending[u]);
        }
    }
};

struct IT{
    int st[MAXN << 2];

    void reset(){
        memset(st, -0x3f, sizeof(st));
    }
    void update(int node, int l, int r, int pos,int x){

         if (l == r){
             st[node] = x;
             return;
         }
         int mid = (l + r) >> 1;
         if (pos <= mid) update(node << 1, l, mid, pos, x);
         else update(node << 1 | 1, mid + 1, r, pos, x);
         st[node] = max(st[node << 1], st[node << 1 | 1]);
//         cout << "UPD: " << node << ' ' << l << ' ' <<r << ' ' << pos << ' ' << x << ' ' << st[node] << endl;
    }

    int get(int node, int l,int r, int u, int v){
         if (l >= u and r <= v){
             return st[node];
         }

         if (l > v or r < u) return -INF;
         int mid = (l + r) >> 1;
         return max(get(node << 1, l, mid, u, v),
                    get(node << 1 | 1, mid + 1, r, u, v));
    }

    int get(int u, int v){
        return get(1, 1, n, u, v);
    }

    void update(int pos, int x){
        update(1, 1, n, pos, x);
    }
};
namespace subtask6{
    int dp[MAXN], R[MAXN], revive[MAXN];
    ii b[MAXN];
    bool checkSubtask6(){
         return true;
    }
    DSU DSU;

    bool check(int i, int mid){
         auto it = DSU.component.lower_bound(mid);
         int numzero = 0;
         if (it == DSU.component.end()) numzero = 0;
         else{
             int e = *it;
             int sz = DSU.ranking[DSU.root(e)];
             int s = e - sz + 1;
             maximize(numzero, min(e, i) - max(s, mid) + 1);
             it++;
             if (it != DSU.component.end()){
                 int e = *it;
                 int sz = DSU.ranking[DSU.root(e)];
                 int s = e - sz + 1;
                 maximize(numzero, min(e, i) - max(s, mid) + 1);
             }
         }
         return numzero < d;
    }

    void solveSubtask6(){
        for(int i = 1; i <= n; i++){
            b[i] = {a[i], i};
        }
        IT IT;
        DSU.reset();
        IT.reset();
        memset(revive, 0, sizeof(revive));
        sort(b + 1, b + 1 + n);
        for(int i = n, last; i >= 1; i = last){
            last = i;
            while(last >= 1 and b[last].fi == b[i].fi){
                  int l = 0, r = b[last].se, res = 0;
                  while(l <= r){
                     int mid = (l + r) >> 1;

                     if (check(b[last].se, mid)){
                         res = mid;
                         r = mid - 1;
                     }
                     else{
                         l = mid + 1;
                     }
                  }
//                  if (b[last].se == 6){
//                      if (check(6, 2)){
//                          cout << "YES" << endl;
//                      }
//                      else cout << "NO" << endl;
//                  }
                  R[b[last].se] = res;
//                  cout << res << ' ' << b[last].se << endl;
                  last--;
            }

            for(int j = i; j > last; j--){
                if (1 >= d) DSU.component.insert(b[j].se);
                revive[b[j].se] = 1;
                if (b[j].se > 1 and revive[b[j].se - 1]) DSU.unite(b[j].se - 1, b[j].se);
                if (b[j].se < n and revive[b[j].se + 1]) DSU.unite(b[j].se, b[j].se + 1);
            }
        }
        for(int i = 1; i <= n; i++){
            a[b[i].se] = i;
        }
//        for(int i = 1; i <= n; i++){
//            cout << a[i] << ' ';
//        }
//        cout << endl;


//        for(int i = 1; i <= n; i++){
//            cout << R[i] << ' ';
//        }
//        cout << endl;
        int res = 0;
        for(int i = 1, last = 0; i <= n; i = last){
            last = i;
            while(last <= n and b[last].fi == b[i].fi){
                  dp[b[last].se] = max(1, IT.get(R[b[last].se], b[last].se) + 1);
//                  cout << R[b[last].se] + 1<< ' '
//                       << b[last].se << ' '
//                       << dp[b[last].se] << ' '
//                       << endl;
                  maximize(res, dp[b[last].se]);
                  last++;
            }

            for(int j = i; j < last; j++){
                IT.update(b[j].se, dp[b[j].se]);
            }
        }
//        for(int i = 1; i <= n; i++){
//            cout <<dp[i] << ' ' ;
//        }
//        cout << endl;

        cout << res << endl;

    }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> d;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

//    if (subtask1::checkSubtask1()) return subtask1::solveSubtask1(), 0;
//    if (subtask2::checkSubtask2()) return subtask2::solveSubtask2(), 0;
//    if (subtask3::checkSubtask3()) return subtask3::solveSubtask3(), 0;
//    if (subtask4::checkSubtask4()) return subtask4::solveSubtask4(), 0;
//    if (subtask5::checkSubtask5()) return subtask5::solveSubtask5(), 0;
    if (subtask6::checkSubtask6()) return subtask6::solveSubtask6(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message

Main.cpp: In function 'void subtask5::solveSubtask5()':
Main.cpp:162:13: warning: unused variable 'res' [-Wunused-variable]
  162 |         int res = 0;
      |             ^~~
Main.cpp: At global scope:
Main.cpp:354:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  354 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:358:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  358 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:359:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  359 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15196 KB	Output is correct
2	Correct	4 ms	15196 KB	Output is correct
3	Correct	4 ms	15196 KB	Output is correct
4	Correct	4 ms	15196 KB	Output is correct
5	Correct	4 ms	15324 KB	Output is correct
6	Correct	4 ms	15196 KB	Output is correct
7	Correct	4 ms	15196 KB	Output is correct
8	Correct	4 ms	15408 KB	Output is correct
9	Correct	4 ms	15196 KB	Output is correct
10	Correct	4 ms	15196 KB	Output is correct
11	Correct	4 ms	15280 KB	Output is correct
12	Correct	4 ms	15196 KB	Output is correct
13	Correct	4 ms	15284 KB	Output is correct
14	Correct	4 ms	15196 KB	Output is correct
15	Correct	4 ms	15196 KB	Output is correct
16	Correct	4 ms	15196 KB	Output is correct
17	Correct	4 ms	15196 KB	Output is correct
18	Correct	4 ms	15192 KB	Output is correct
19	Correct	4 ms	15196 KB	Output is correct
20	Correct	5 ms	15196 KB	Output is correct
21	Correct	4 ms	15196 KB	Output is correct
22	Correct	4 ms	15196 KB	Output is correct
23	Correct	4 ms	15192 KB	Output is correct
24	Correct	4 ms	15196 KB	Output is correct
25	Correct	4 ms	15196 KB	Output is correct
26	Correct	4 ms	15196 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15196 KB	Output is correct
2	Correct	4 ms	15196 KB	Output is correct
3	Correct	4 ms	15196 KB	Output is correct
4	Correct	4 ms	15196 KB	Output is correct
5	Correct	4 ms	15324 KB	Output is correct
6	Correct	4 ms	15196 KB	Output is correct
7	Correct	4 ms	15196 KB	Output is correct
8	Correct	4 ms	15408 KB	Output is correct
9	Correct	4 ms	15196 KB	Output is correct
10	Correct	4 ms	15196 KB	Output is correct
11	Correct	4 ms	15280 KB	Output is correct
12	Correct	4 ms	15196 KB	Output is correct
13	Correct	4 ms	15284 KB	Output is correct
14	Correct	4 ms	15196 KB	Output is correct
15	Correct	4 ms	15196 KB	Output is correct
16	Correct	4 ms	15196 KB	Output is correct
17	Correct	4 ms	15196 KB	Output is correct
18	Correct	4 ms	15192 KB	Output is correct
19	Correct	4 ms	15196 KB	Output is correct
20	Correct	5 ms	15196 KB	Output is correct
21	Correct	4 ms	15196 KB	Output is correct
22	Correct	4 ms	15196 KB	Output is correct
23	Correct	4 ms	15192 KB	Output is correct
24	Correct	4 ms	15196 KB	Output is correct
25	Correct	4 ms	15196 KB	Output is correct
26	Correct	4 ms	15196 KB	Output is correct
27	Correct	5 ms	15196 KB	Output is correct
28	Correct	4 ms	15192 KB	Output is correct
29	Correct	4 ms	15196 KB	Output is correct
30	Correct	4 ms	15196 KB	Output is correct
31	Correct	4 ms	15196 KB	Output is correct
32	Correct	4 ms	15192 KB	Output is correct
33	Correct	4 ms	15196 KB	Output is correct
34	Correct	4 ms	15196 KB	Output is correct
35	Correct	4 ms	15192 KB	Output is correct
36	Correct	4 ms	15196 KB	Output is correct
37	Correct	4 ms	15196 KB	Output is correct
38	Correct	4 ms	15196 KB	Output is correct
39	Correct	4 ms	15288 KB	Output is correct
40	Correct	5 ms	15192 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15196 KB	Output is correct
2	Correct	4 ms	15196 KB	Output is correct
3	Correct	4 ms	15196 KB	Output is correct
4	Correct	4 ms	15196 KB	Output is correct
5	Correct	4 ms	15324 KB	Output is correct
6	Correct	4 ms	15196 KB	Output is correct
7	Correct	4 ms	15196 KB	Output is correct
8	Correct	4 ms	15408 KB	Output is correct
9	Correct	4 ms	15196 KB	Output is correct
10	Correct	4 ms	15196 KB	Output is correct
11	Correct	4 ms	15280 KB	Output is correct
12	Correct	4 ms	15196 KB	Output is correct
13	Correct	4 ms	15284 KB	Output is correct
14	Correct	4 ms	15196 KB	Output is correct
15	Correct	4 ms	15196 KB	Output is correct
16	Correct	4 ms	15196 KB	Output is correct
17	Correct	4 ms	15196 KB	Output is correct
18	Correct	4 ms	15192 KB	Output is correct
19	Correct	4 ms	15196 KB	Output is correct
20	Correct	5 ms	15196 KB	Output is correct
21	Correct	4 ms	15196 KB	Output is correct
22	Correct	4 ms	15196 KB	Output is correct
23	Correct	4 ms	15192 KB	Output is correct
24	Correct	4 ms	15196 KB	Output is correct
25	Correct	4 ms	15196 KB	Output is correct
26	Correct	4 ms	15196 KB	Output is correct
27	Correct	5 ms	15196 KB	Output is correct
28	Correct	4 ms	15192 KB	Output is correct
29	Correct	4 ms	15196 KB	Output is correct
30	Correct	4 ms	15196 KB	Output is correct
31	Correct	4 ms	15196 KB	Output is correct
32	Correct	4 ms	15192 KB	Output is correct
33	Correct	4 ms	15196 KB	Output is correct
34	Correct	4 ms	15196 KB	Output is correct
35	Correct	4 ms	15192 KB	Output is correct
36	Correct	4 ms	15196 KB	Output is correct
37	Correct	4 ms	15196 KB	Output is correct
38	Correct	4 ms	15196 KB	Output is correct
39	Correct	4 ms	15288 KB	Output is correct
40	Correct	5 ms	15192 KB	Output is correct
41	Correct	15 ms	15392 KB	Output is correct
42	Correct	14 ms	15448 KB	Output is correct
43	Correct	8 ms	15448 KB	Output is correct
44	Correct	8 ms	15452 KB	Output is correct
45	Correct	7 ms	15452 KB	Output is correct
46	Correct	7 ms	15452 KB	Output is correct
47	Correct	9 ms	15448 KB	Output is correct
48	Correct	10 ms	15704 KB	Output is correct
49	Correct	8 ms	15392 KB	Output is correct
50	Correct	9 ms	15452 KB	Output is correct
51	Correct	11 ms	15448 KB	Output is correct
52	Correct	12 ms	15452 KB	Output is correct
53	Correct	7 ms	15452 KB	Output is correct
54	Correct	7 ms	15340 KB	Output is correct
55	Correct	7 ms	15452 KB	Output is correct
56	Correct	7 ms	15452 KB	Output is correct
57	Correct	7 ms	15448 KB	Output is correct
58	Correct	7 ms	15452 KB	Output is correct
59	Correct	6 ms	15500 KB	Output is correct
60	Correct	7 ms	15376 KB	Output is correct
61	Correct	7 ms	15452 KB	Output is correct

Subtask #4

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	19324 KB	Output is correct
2	Correct	466 ms	22864 KB	Output is correct
3	Correct	689 ms	22992 KB	Output is correct
4	Correct	1040 ms	23308 KB	Output is correct
5	Correct	722 ms	22140 KB	Output is correct
6	Correct	1018 ms	23064 KB	Output is correct
7	Correct	151 ms	19528 KB	Output is correct
8	Correct	189 ms	19460 KB	Output is correct
9	Correct	175 ms	19416 KB	Output is correct
10	Correct	187 ms	19356 KB	Output is correct
11	Correct	618 ms	19704 KB	Output is correct
12	Correct	739 ms	20052 KB	Output is correct
13	Correct	470 ms	19548 KB	Output is correct
14	Correct	695 ms	19792 KB	Output is correct

Subtask #5

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	19632 KB	Output is correct
2	Correct	152 ms	19744 KB	Output is correct
3	Correct	155 ms	19408 KB	Output is correct
4	Correct	173 ms	19536 KB	Output is correct
5	Correct	168 ms	19792 KB	Output is correct
6	Correct	218 ms	19780 KB	Output is correct
7	Correct	115 ms	19540 KB	Output is correct
8	Correct	113 ms	19536 KB	Output is correct
9	Correct	123 ms	19528 KB	Output is correct
10	Correct	160 ms	19540 KB	Output is correct
11	Correct	166 ms	19472 KB	Output is correct
12	Correct	190 ms	19544 KB	Output is correct

Subtask #6

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15196 KB	Output is correct
2	Correct	4 ms	15196 KB	Output is correct
3	Correct	4 ms	15196 KB	Output is correct
4	Correct	4 ms	15196 KB	Output is correct
5	Correct	4 ms	15324 KB	Output is correct
6	Correct	4 ms	15196 KB	Output is correct
7	Correct	4 ms	15196 KB	Output is correct
8	Correct	4 ms	15408 KB	Output is correct
9	Correct	4 ms	15196 KB	Output is correct
10	Correct	4 ms	15196 KB	Output is correct
11	Correct	4 ms	15280 KB	Output is correct
12	Correct	4 ms	15196 KB	Output is correct
13	Correct	4 ms	15284 KB	Output is correct
14	Correct	4 ms	15196 KB	Output is correct
15	Correct	4 ms	15196 KB	Output is correct
16	Correct	4 ms	15196 KB	Output is correct
17	Correct	4 ms	15196 KB	Output is correct
18	Correct	4 ms	15192 KB	Output is correct
19	Correct	4 ms	15196 KB	Output is correct
20	Correct	5 ms	15196 KB	Output is correct
21	Correct	4 ms	15196 KB	Output is correct
22	Correct	4 ms	15196 KB	Output is correct
23	Correct	4 ms	15192 KB	Output is correct
24	Correct	4 ms	15196 KB	Output is correct
25	Correct	4 ms	15196 KB	Output is correct
26	Correct	4 ms	15196 KB	Output is correct
27	Correct	5 ms	15196 KB	Output is correct
28	Correct	4 ms	15192 KB	Output is correct
29	Correct	4 ms	15196 KB	Output is correct
30	Correct	4 ms	15196 KB	Output is correct
31	Correct	4 ms	15196 KB	Output is correct
32	Correct	4 ms	15192 KB	Output is correct
33	Correct	4 ms	15196 KB	Output is correct
34	Correct	4 ms	15196 KB	Output is correct
35	Correct	4 ms	15192 KB	Output is correct
36	Correct	4 ms	15196 KB	Output is correct
37	Correct	4 ms	15196 KB	Output is correct
38	Correct	4 ms	15196 KB	Output is correct
39	Correct	4 ms	15288 KB	Output is correct
40	Correct	5 ms	15192 KB	Output is correct
41	Correct	15 ms	15392 KB	Output is correct
42	Correct	14 ms	15448 KB	Output is correct
43	Correct	8 ms	15448 KB	Output is correct
44	Correct	8 ms	15452 KB	Output is correct
45	Correct	7 ms	15452 KB	Output is correct
46	Correct	7 ms	15452 KB	Output is correct
47	Correct	9 ms	15448 KB	Output is correct
48	Correct	10 ms	15704 KB	Output is correct
49	Correct	8 ms	15392 KB	Output is correct
50	Correct	9 ms	15452 KB	Output is correct
51	Correct	11 ms	15448 KB	Output is correct
52	Correct	12 ms	15452 KB	Output is correct
53	Correct	7 ms	15452 KB	Output is correct
54	Correct	7 ms	15340 KB	Output is correct
55	Correct	7 ms	15452 KB	Output is correct
56	Correct	7 ms	15452 KB	Output is correct
57	Correct	7 ms	15448 KB	Output is correct
58	Correct	7 ms	15452 KB	Output is correct
59	Correct	6 ms	15500 KB	Output is correct
60	Correct	7 ms	15376 KB	Output is correct
61	Correct	7 ms	15452 KB	Output is correct
62	Correct	116 ms	19324 KB	Output is correct
63	Correct	466 ms	22864 KB	Output is correct
64	Correct	689 ms	22992 KB	Output is correct
65	Correct	1040 ms	23308 KB	Output is correct
66	Correct	722 ms	22140 KB	Output is correct
67	Correct	1018 ms	23064 KB	Output is correct
68	Correct	151 ms	19528 KB	Output is correct
69	Correct	189 ms	19460 KB	Output is correct
70	Correct	175 ms	19416 KB	Output is correct
71	Correct	187 ms	19356 KB	Output is correct
72	Correct	618 ms	19704 KB	Output is correct
73	Correct	739 ms	20052 KB	Output is correct
74	Correct	470 ms	19548 KB	Output is correct
75	Correct	695 ms	19792 KB	Output is correct
76	Correct	92 ms	19632 KB	Output is correct
77	Correct	152 ms	19744 KB	Output is correct
78	Correct	155 ms	19408 KB	Output is correct
79	Correct	173 ms	19536 KB	Output is correct
80	Correct	168 ms	19792 KB	Output is correct
81	Correct	218 ms	19780 KB	Output is correct
82	Correct	115 ms	19540 KB	Output is correct
83	Correct	113 ms	19536 KB	Output is correct
84	Correct	123 ms	19528 KB	Output is correct
85	Correct	160 ms	19540 KB	Output is correct
86	Correct	166 ms	19472 KB	Output is correct
87	Correct	190 ms	19544 KB	Output is correct
88	Correct	777 ms	22616 KB	Output is correct
89	Correct	711 ms	21928 KB	Output is correct
90	Correct	416 ms	21176 KB	Output is correct
91	Correct	204 ms	20564 KB	Output is correct
92	Correct	139 ms	20644 KB	Output is correct
93	Correct	153 ms	20644 KB	Output is correct
94	Correct	171 ms	20640 KB	Output is correct
95	Correct	650 ms	22316 KB	Output is correct
96	Correct	442 ms	21508 KB	Output is correct
97	Correct	277 ms	20780 KB	Output is correct
98	Correct	215 ms	20720 KB	Output is correct
99	Correct	199 ms	20652 KB	Output is correct
100	Correct	194 ms	20656 KB	Output is correct
101	Correct	168 ms	20644 KB	Output is correct
102	Correct	156 ms	20648 KB	Output is correct
103	Correct	156 ms	20560 KB	Output is correct
104	Correct	168 ms	20656 KB	Output is correct
105	Correct	191 ms	20648 KB	Output is correct
106	Correct	229 ms	20408 KB	Output is correct
107	Correct	255 ms	20656 KB	Output is correct
108	Correct	204 ms	20820 KB	Output is correct
109	Correct	344 ms	20528 KB	Output is correct
110	Correct	297 ms	21072 KB	Output is correct
111	Correct	210 ms	20564 KB	Output is correct
112	Correct	180 ms	20560 KB	Output is correct
113	Correct	176 ms	20676 KB	Output is correct
114	Correct	182 ms	20648 KB	Output is correct
115	Correct	123 ms	20660 KB	Output is correct
116	Correct	109 ms	20564 KB	Output is correct
117	Correct	133 ms	20560 KB	Output is correct
118	Correct	140 ms	20648 KB	Output is correct
119	Correct	163 ms	20528 KB	Output is correct
120	Correct	164 ms	20648 KB	Output is correct