oj.uz

Submission #736636

# Submission time Handle Problem Language Result Execution time Memory
736636 2023-05-06T03:56:09 Z Olympia Zoltan (COCI16_zoltan) C++17
7 / 140
 549 ms 7124 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;
int lis_length[MX];
int lis_number[MX];
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];
                }
            }
        }
    }
    int 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];
    }
    int 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;
        } else if (p.first > mx) {
            mx = p.first, cnt = p.second;
        }
    }
    cout << cnt << " " << mx << '\n';
}

Compilation message

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

Subtask #1
7.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 524 ms 292 KB Output isn't correct
2 Incorrect 514 ms 292 KB Output isn't correct
3 Incorrect 549 ms 308 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 313 ms 296 KB Output isn't correct
6 Incorrect 239 ms 296 KB Output isn't correct
7 Runtime error 145 ms 460 KB Execution killed with signal 11
8 Runtime error 148 ms 444 KB Execution killed with signal 11
9 Runtime error 142 ms 456 KB Execution killed with signal 11
10 Runtime error 146 ms 448 KB Execution killed with signal 11
11 Runtime error 49 ms 5784 KB Execution killed with signal 11
12 Runtime error 48 ms 5052 KB Execution killed with signal 11
13 Runtime error 45 ms 4808 KB Execution killed with signal 11
14 Runtime error 46 ms 5076 KB Execution killed with signal 11
15 Runtime error 51 ms 6248 KB Execution killed with signal 11
16 Runtime error 53 ms 7052 KB Execution killed with signal 11
17 Runtime error 34 ms 7124 KB Execution killed with signal 11
18 Runtime error 36 ms 7096 KB Execution killed with signal 11
19 Runtime error 35 ms 7088 KB Execution killed with signal 11
20 Runtime error 33 ms 7088 KB Execution killed with signal 11