oj.uz

Submission #736635

# Submission time Handle Problem Language Result Execution time Memory
736635 2023-05-06T03:55:04 Z Olympia Zoltan (COCI16_zoltan) C++14
7 / 140
 1000 ms 5200 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 599 ms 296 KB Output isn't correct
2 Incorrect 554 ms 300 KB Output isn't correct
3 Incorrect 589 ms 292 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 364 ms 300 KB Output isn't correct
6 Incorrect 285 ms 212 KB Output isn't correct
7 Incorrect 191 ms 340 KB Output isn't correct
8 Incorrect 164 ms 340 KB Output isn't correct
9 Incorrect 169 ms 340 KB Output isn't correct
10 Incorrect 204 ms 340 KB Output isn't correct
11 Execution timed out 1078 ms 4172 KB Time limit exceeded
12 Execution timed out 1080 ms 3672 KB Time limit exceeded
13 Execution timed out 1082 ms 3528 KB Time limit exceeded
14 Execution timed out 1071 ms 3680 KB Time limit exceeded
15 Execution timed out 1051 ms 4424 KB Time limit exceeded
16 Execution timed out 1090 ms 5068 KB Time limit exceeded
17 Execution timed out 1086 ms 5200 KB Time limit exceeded
18 Execution timed out 1074 ms 5200 KB Time limit exceeded
19 Execution timed out 1085 ms 5192 KB Time limit exceeded
20 Execution timed out 1056 ms 5200 KB Time limit exceeded