답안 #737174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737174	2023-05-06T17:51:17 Z	Olympia	Zoltan (COCI16_zoltan)	C++17	63 / 140	1000 ms	13324 KB

zoltan

#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 = 2e5;
int64_t lis_length[MX];
int64_t lis_number[MX];
const int MOD = 1e9 + 7;
pair<int64_t,int64_t> lis (vector<int> v, int x) {
    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 = 1;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == x or x == -1) {
            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);
}
pair<int64_t,int64_t> split (vector<int> v, int x) {
    vector<int> v1, v2;
    for (int i: v) {
        if (i > x) {
            v2.push_back(i);
        } else {
            v1.push_back(i);
        }
    }
    reverse(v1.begin(), v1.end());
    auto p1 = lis(v1, x);
    auto p2 = lis(v2, -1);
    return make_pair(p1.first + p2.first, p1.second * p2.second);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> v(n);
    set<int> s;
    s.insert(0);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        s.insert(v[i]);
    }
    int64_t mx = 0, cnt = 0;
    for (int i: s) {
        auto p = split(v, i);
        if (p.first > mx) {
            mx = p.first, cnt = p.second;
        } else if (p.first == mx) {
            cnt += p.second, cnt %= MOD;
        }
    }
    if (cnt % 2 == 0) cnt /= 2;
    else cnt = (cnt + MOD - 1)/2 % MOD;   
    for (int i = 0; i < n - mx; i++) {
        cnt *= 2; cnt %= MOD;
    }
    cout << mx << " " << cnt << '\n';
}

Compilation message

zoltan.cpp: In function 'std::pair<long int, long int> lis(std::vector<int>, 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

63.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	819 ms	536 KB	Output is correct
8	Correct	847 ms	532 KB	Output is correct
9	Incorrect	850 ms	528 KB	Output isn't correct
10	Correct	862 ms	532 KB	Output is correct
11	Execution timed out	1073 ms	11072 KB	Time limit exceeded
12	Execution timed out	1075 ms	9724 KB	Time limit exceeded
13	Execution timed out	1063 ms	9208 KB	Time limit exceeded
14	Execution timed out	1077 ms	9408 KB	Time limit exceeded
15	Execution timed out	1065 ms	11600 KB	Time limit exceeded
16	Execution timed out	1063 ms	13324 KB	Time limit exceeded
17	Execution timed out	1068 ms	12008 KB	Time limit exceeded
18	Execution timed out	1070 ms	12060 KB	Time limit exceeded
19	Execution timed out	1070 ms	11964 KB	Time limit exceeded
20	Execution timed out	1068 ms	12056 KB	Time limit exceeded