oj.uz

Submission #737104

# Submission time Handle Problem Language Result Execution time Memory
737104 2023-05-06T15:51:07 Z Olympia Zoltan (COCI16_zoltan) C++17
14 / 140
 596 ms 8996 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;
        }
    }
    sort(v.begin(), v.end());
    cout << v.back() << " " << cnt << '\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
14.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 596 ms 300 KB Output isn't correct
2 Incorrect 535 ms 296 KB Output isn't correct
3 Incorrect 545 ms 304 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 346 ms 300 KB Output is correct
6 Correct 302 ms 304 KB Output is correct
7 Runtime error 154 ms 460 KB Execution killed with signal 11
8 Runtime error 152 ms 472 KB Execution killed with signal 11
9 Runtime error 155 ms 456 KB Execution killed with signal 11
10 Runtime error 165 ms 476 KB Execution killed with signal 11
11 Runtime error 27 ms 6980 KB Execution killed with signal 11
12 Runtime error 23 ms 6080 KB Execution killed with signal 11
13 Runtime error 27 ms 5804 KB Execution killed with signal 11
14 Runtime error 24 ms 6412 KB Execution killed with signal 11
15 Runtime error 31 ms 7884 KB Execution killed with signal 11
16 Runtime error 34 ms 8996 KB Execution killed with signal 11
17 Runtime error 28 ms 8352 KB Execution killed with signal 11
18 Runtime error 30 ms 8400 KB Execution killed with signal 11
19 Runtime error 30 ms 8376 KB Execution killed with signal 11
20 Runtime error 29 ms 8384 KB Execution killed with signal 11