oj.uz

답안 #498307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498307 2021-12-25T03:32:34 Z kingline 수열 (APIO14_sequence) C++17
11 / 100
 2000 ms 1996 KB 
/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
//#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
//#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
#define pii pair < int, int >
#define pll pair < long long, long long >

using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
const int M = 305;
const int mod = 1e9 + 7;

int n, k, a[N], res, use;

vector < int > dv;
void rec(int l, int r, int last) {
    if(l >= r) return;
    last++;
    while(last < dv.size() && dv[last] < l) last++;
    if(last == dv.size() || r <= dv[last]) return;
    int lef = 0, righ = 0;
    for(int i = l; i <= dv[last]; i++) {
        lef += a[i];
    }
    for(int i = dv[last] + 1; i <= r; i++) {
        righ += a[i];
    }
    res += lef * righ;
    ++use;
    rec(l, dv[last], last);
    rec(dv[last] + 1, r, last);
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //file("pieaters");
    cin >> n >> k;
    vector < int > br;
    for(int i = 1; i <= n; i++) {
        br.pb(i);
        cin >> a[i];
    }
    int ans = 0;
    vector < int > path;
    do {
        for(int i = 0; i < k; i++) dv.pb(br[i]);
        res = 0;
        rec(1, n, -1);
        if(res >= ans && use == k) {
            path = dv;
            ans = res;
        }
        use = 0;
        dv.clear();
    } while(next_permutation(all(br)));
    reverse(all(path));
    cout << ans << endl;
    for(int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
}

Compilation message

sequence.cpp: In function 'void rec(long long int, long long int, long long int)':
sequence.cpp:33:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while(last < dv.size() && dv[last] < l) last++;
      |           ~~~~~^~~~~~~~~~~
sequence.cpp:34:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if(last == dv.size() || r <= dv[last]) return;
      |        ~~~~~^~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:74:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < path.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 312 KB contestant found the optimal answer: 108 == 108
2 Correct 138 ms 204 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 204 KB contestant found the optimal answer: 0 == 0
4 Correct 274 ms 296 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 279 ms 312 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 105 ms 204 KB contestant found the optimal answer: 1 == 1
7 Correct 106 ms 300 KB contestant found the optimal answer: 1 == 1
8 Correct 118 ms 300 KB contestant found the optimal answer: 1 == 1
9 Correct 173 ms 204 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 185 ms 300 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 196 ms 296 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 196 ms 300 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 23 ms 316 KB contestant found the optimal answer: 140072 == 140072
14 Correct 1 ms 312 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 210 ms 300 KB contestant found the optimal answer: 805 == 805
16 Correct 175 ms 316 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 199 ms 300 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2045 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2043 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2059 ms 588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2078 ms 1996 KB Time limit exceeded
2 Halted 0 ms 0 KB -