oj.uz

Submission #737173

# Submission time Handle Problem Language Result Execution time Memory
737173 2023-05-06T17:50:35 Z Olympia Zoltan (COCI16_zoltan) C++17
42 / 140
 676 ms 27904 KB 
#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <map>
#include <deque>
using namespace std;
const int MX = 20;
int64_t lis_length[MX];
int64_t lis_number[MX];
const int MOD = 1e9 + 7;
pair<int64_t,int64_t> lis (vector<int> v, int x) {
    lis_length[0] = 1, lis_number[0] = 1;
    for (int i = 1; i < v.size(); i++) {
        lis_length[i] = 1, lis_number[i] = 1;
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i]) {
                if (lis_length[j] + 1 > lis_length[i]) {
                    lis_length[i] = lis_length[j] + 1;
                    lis_number[i] = lis_number[j];
                } else if (lis_length[j] + 1 == lis_length[i]) {
                    lis_number[i] += lis_number[j];
                    lis_number[i] %= MOD;
                }
            }
        }
    }
    int64_t mx = 0, cnt = 1;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == x or x == -1) {
            if (lis_length[i] > mx) {
                mx = lis_length[i];
                cnt = lis_number[i];
            } else if (lis_length[i] == mx) {
                cnt += lis_number[i];
            }
        }
    }
    return make_pair(mx, cnt);
}
void print (vector<int> v) {
    cout << "{";
    for (int i: v) {
        cout << i << ' ';
    }
    cout << "}\n";
}
pair<int64_t,int64_t> split (vector<int> v, int x) {
    vector<int> v1, v2;
    for (int i: v) {
        if (i > x) {
            v2.push_back(i);
        } else {
            v1.push_back(i);
        }
    }
    reverse(v1.begin(), v1.end());
    auto p1 = lis(v1, x);
    auto p2 = lis(v2, -1);
    //print(v1), print(v2);
    //cout << x << " " << p1.first << " " << p1.second << " " << p2.first << " " << p2.second << '\n';
    return make_pair(p1.first + p2.first, p1.second * p2.second);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> v(n);
    set<int> s;
    s.insert(0);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        s.insert(v[i]);
    }
    int64_t mx = 0, cnt = 0;
    for (int i: s) {
        auto p = split(v, i);
        if (p.first > mx) {
            mx = p.first, cnt = p.second;
        } else if (p.first == mx) {
            cnt += p.second, cnt %= MOD;
        }
    }
    if (cnt % 2 == 0) cnt /= 2;
    else cnt = (cnt + MOD - 1)/2 % MOD;   
    for (int i = 0; i < n - mx; i++) {
        cnt *= 2; cnt %= MOD;
    }
    cout << mx << " " << cnt << '\n';
}

Compilation message

zoltan.cpp: In function 'std::pair<long int, long int> lis(std::vector<int>, int)':
zoltan.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Runtime error 663 ms 660 KB Execution killed with signal 11
8 Runtime error 656 ms 612 KB Execution killed with signal 11
9 Runtime error 676 ms 544 KB Execution killed with signal 11
10 Runtime error 664 ms 616 KB Execution killed with signal 11
11 Runtime error 79 ms 22012 KB Execution killed with signal 11
12 Runtime error 71 ms 19092 KB Execution killed with signal 11
13 Runtime error 72 ms 18052 KB Execution killed with signal 11
14 Runtime error 66 ms 19564 KB Execution killed with signal 11
15 Runtime error 87 ms 24128 KB Execution killed with signal 11
16 Runtime error 100 ms 27904 KB Execution killed with signal 11
17 Runtime error 72 ms 24256 KB Execution killed with signal 11
18 Runtime error 70 ms 24256 KB Execution killed with signal 11
19 Runtime error 66 ms 24188 KB Execution killed with signal 11
20 Runtime error 70 ms 24196 KB Execution killed with signal 11