oj.uz

Submission #736639

# Submission time Handle Problem Language Result Execution time Memory
736639 2023-05-06T04:01:06 Z Olympia Zoltan (COCI16_zoltan) C++17
7 / 140
 644 ms 7128 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];
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];
                }
            }
        }
    }
    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;
        } 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 636 ms 296 KB Output isn't correct
2 Incorrect 644 ms 292 KB Output isn't correct
3 Incorrect 608 ms 212 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 454 ms 300 KB Output isn't correct
6 Incorrect 320 ms 292 KB Output isn't correct
7 Runtime error 176 ms 464 KB Execution killed with signal 11
8 Runtime error 184 ms 444 KB Execution killed with signal 11
9 Runtime error 174 ms 456 KB Execution killed with signal 11
10 Runtime error 166 ms 444 KB Execution killed with signal 11
11 Runtime error 26 ms 5804 KB Execution killed with signal 11
12 Runtime error 24 ms 5080 KB Execution killed with signal 11
13 Runtime error 29 ms 4884 KB Execution killed with signal 11
14 Runtime error 23 ms 5080 KB Execution killed with signal 11
15 Runtime error 28 ms 6256 KB Execution killed with signal 11
16 Runtime error 31 ms 7068 KB Execution killed with signal 11
17 Runtime error 24 ms 7128 KB Execution killed with signal 11
18 Runtime error 25 ms 7128 KB Execution killed with signal 11
19 Runtime error 28 ms 7120 KB Execution killed with signal 11
20 Runtime error 24 ms 7128 KB Execution killed with signal 11