oj.uz

Submission #736640

# Submission time Handle Problem Language Result Execution time Memory
736640 2023-05-06T04:01:31 Z Olympia Zoltan (COCI16_zoltan) C++17
7 / 140
 549 ms 7176 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 << cnt << " " << mx << '\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
7.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 518 ms 292 KB Output isn't correct
2 Incorrect 529 ms 292 KB Output isn't correct
3 Incorrect 549 ms 296 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 349 ms 304 KB Output isn't correct
6 Incorrect 266 ms 296 KB Output isn't correct
7 Runtime error 137 ms 444 KB Execution killed with signal 11
8 Runtime error 131 ms 460 KB Execution killed with signal 11
9 Runtime error 133 ms 460 KB Execution killed with signal 11
10 Runtime error 135 ms 444 KB Execution killed with signal 11
11 Runtime error 25 ms 5804 KB Execution killed with signal 11
12 Runtime error 21 ms 5064 KB Execution killed with signal 11
13 Runtime error 20 ms 4836 KB Execution killed with signal 11
14 Runtime error 24 ms 5080 KB Execution killed with signal 11
15 Runtime error 27 ms 6216 KB Execution killed with signal 11
16 Runtime error 30 ms 7068 KB Execution killed with signal 11
17 Runtime error 26 ms 7120 KB Execution killed with signal 11
18 Runtime error 28 ms 7176 KB Execution killed with signal 11
19 Runtime error 27 ms 7112 KB Execution killed with signal 11
20 Runtime error 26 ms 7120 KB Execution killed with signal 11