oj.uz

Submission #737105

# Submission time Handle Problem Language Result Execution time Memory
737105 2023-05-06T15:51:31 Z Olympia Zoltan (COCI16_zoltan) C++17
42 / 140
 576 ms 7240 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<int,int> lis (vector<int> v) {
    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 = 0;
    for (int i = 0; i < v.size(); i++) {
        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);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int64_t mx = 0, cnt = 0;
    for (int i = 0; i < (1 << n); i += 2) {
        deque<int> d;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                d.push_back(v[j]);
            } else {
                d.push_front(v[j]);
            }
        }
        vector<int> vec;
        for (int i: d) {
            vec.push_back(i);
        }
        auto p = lis(vec);
        if (p.first == mx) {
            cnt += p.second;
            cnt %= MOD;
        } else if (p.first > mx) {
            mx = p.first, cnt = p.second;
        }
    }
    cout << mx << " " << cnt << '\n';
}

Compilation message

zoltan.cpp: In function 'std::pair<int, int> lis(std::vector<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 546 ms 296 KB Output is correct
2 Correct 539 ms 292 KB Output is correct
3 Correct 576 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 406 ms 296 KB Output is correct
6 Correct 251 ms 292 KB Output is correct
7 Runtime error 142 ms 448 KB Execution killed with signal 11
8 Runtime error 141 ms 452 KB Execution killed with signal 11
9 Runtime error 141 ms 464 KB Execution killed with signal 11
10 Runtime error 132 ms 448 KB Execution killed with signal 11
11 Runtime error 24 ms 5808 KB Execution killed with signal 11
12 Runtime error 26 ms 5072 KB Execution killed with signal 11
13 Runtime error 20 ms 4816 KB Execution killed with signal 11
14 Runtime error 28 ms 5072 KB Execution killed with signal 11
15 Runtime error 28 ms 6256 KB Execution killed with signal 11
16 Runtime error 31 ms 7064 KB Execution killed with signal 11
17 Runtime error 26 ms 7240 KB Execution killed with signal 11
18 Runtime error 27 ms 7128 KB Execution killed with signal 11
19 Runtime error 27 ms 7120 KB Execution killed with signal 11
20 Runtime error 25 ms 7136 KB Execution killed with signal 11