oj.uz

Submission #736633

# Submission time Handle Problem Language Result Execution time Memory
736633 2023-05-06T03:53:57 Z Olympia Zoltan (COCI16_zoltan) C++17
7 / 140
 1000 ms 6960 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;
pair<int,int> lis (vector<int> v) {
    vector<int> lis_length(v.size()); //lis_length[i] is the length of the longest increasing subsequence ending at index i.
    vector<int> lis_number(v.size()); //lis_number[i] is the number of longest increasing subsequences ending at index i.
    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:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 568 ms 324 KB Output isn't correct
2 Incorrect 541 ms 300 KB Output isn't correct
3 Incorrect 547 ms 332 KB Output isn't correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 354 ms 212 KB Output isn't correct
6 Incorrect 272 ms 296 KB Output isn't correct
7 Incorrect 204 ms 340 KB Output isn't correct
8 Incorrect 168 ms 340 KB Output isn't correct
9 Incorrect 173 ms 340 KB Output isn't correct
10 Incorrect 176 ms 328 KB Output isn't correct
11 Execution timed out 1084 ms 5392 KB Time limit exceeded
12 Execution timed out 1075 ms 4672 KB Time limit exceeded
13 Execution timed out 1082 ms 4424 KB Time limit exceeded
14 Execution timed out 1067 ms 4936 KB Time limit exceeded
15 Execution timed out 1072 ms 6092 KB Time limit exceeded
16 Execution timed out 1057 ms 6960 KB Time limit exceeded
17 Execution timed out 1074 ms 6336 KB Time limit exceeded
18 Execution timed out 1074 ms 6344 KB Time limit exceeded
19 Execution timed out 1058 ms 6344 KB Time limit exceeded
20 Execution timed out 1081 ms 6336 KB Time limit exceeded