oj.uz

Submission #736641

# Submission time Handle Problem Language Result Execution time Memory
736641 2023-05-06T04:02:50 Z Olympia Zoltan (COCI16_zoltan) C++17
42 / 140
 580 ms 7132 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 580 ms 296 KB Output is correct
2 Correct 527 ms 292 KB Output is correct
3 Correct 554 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 347 ms 296 KB Output is correct
6 Correct 267 ms 292 KB Output is correct
7 Runtime error 134 ms 448 KB Execution killed with signal 11
8 Runtime error 133 ms 460 KB Execution killed with signal 11
9 Runtime error 141 ms 448 KB Execution killed with signal 11
10 Runtime error 136 ms 456 KB Execution killed with signal 11
11 Runtime error 31 ms 5836 KB Execution killed with signal 11
12 Runtime error 27 ms 5068 KB Execution killed with signal 11
13 Runtime error 21 ms 4912 KB Execution killed with signal 11
14 Runtime error 23 ms 5084 KB Execution killed with signal 11
15 Runtime error 27 ms 6264 KB Execution killed with signal 11
16 Runtime error 29 ms 7108 KB Execution killed with signal 11
17 Runtime error 27 ms 7128 KB Execution killed with signal 11
18 Runtime error 28 ms 7132 KB Execution killed with signal 11
19 Runtime error 29 ms 7088 KB Execution killed with signal 11
20 Runtime error 37 ms 7112 KB Execution killed with signal 11