# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
615949 | 2022-07-31T16:05:40 Z | KazamaHoang | 수열 (APIO14_sequence) | C++14 | 2000 ms | 131072 KB |
#include <bits/stdc++.h> using namespace std; int n, k, a[100005]; int what_subtask_is_the_input() { if (n <= 10) return 1; } template <typename T> void println(vector<T>& a) { for (auto x : a) cout << x << " "; cout << "\n"; } namespace sub1 { bool used[15]; long long res = -1; vector<int> ans; void back_track(long long cur = 0, vector<int> order = {}) { vector<int> vt = {1}; for (int i = 2; i <= n; ++ i) { if (used[i]) { vt.push_back(i); } } if (vt.size() == k + 1) { if (res < cur) { res = cur; ans = order; } return; } vt.push_back(n + 1); for (int i = 0; i + 1 < vt.size(); ++ i) { int s = 0; for (int j = vt[i]; j < vt[i + 1]; ++ j) { s += a[j]; } int pref = a[vt[i]]; for (int j = vt[i] + 1; j < vt[i + 1]; ++ j) { used[j] = 1; order.push_back(j - 1); back_track(cur + 1ll * pref * (s - pref), order); order.pop_back(); used[j] = 0; pref += a[j]; } } } void solve() { back_track(); cout << res << "\n"; println(ans); } } int main() { cin.tie(0)->sync_with_stdio(0); #ifdef LOCAL freopen("main.inp", "r", stdin); freopen("main.out", "w", stdout); #endif // LOCAL cin >> n >> k; for (int i = 1; i <= n; ++ i) { cin >> a[i]; } int sub = what_subtask_is_the_input(); if (sub == 1) sub1::solve(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 0 ms | 212 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 0 ms | 212 KB | contestant found the optimal answer: 0 == 0 |
4 | Correct | 4 ms | 324 KB | contestant found the optimal answer: 1542524 == 1542524 |
5 | Correct | 234 ms | 312 KB | contestant found the optimal answer: 4500000000 == 4500000000 |
6 | Correct | 0 ms | 212 KB | contestant found the optimal answer: 1 == 1 |
7 | Correct | 1 ms | 212 KB | contestant found the optimal answer: 1 == 1 |
8 | Correct | 0 ms | 212 KB | contestant found the optimal answer: 1 == 1 |
9 | Correct | 1 ms | 328 KB | contestant found the optimal answer: 100400096 == 100400096 |
10 | Correct | 1 ms | 324 KB | contestant found the optimal answer: 900320000 == 900320000 |
11 | Correct | 1 ms | 212 KB | contestant found the optimal answer: 3698080248 == 3698080248 |
12 | Correct | 2 ms | 212 KB | contestant found the optimal answer: 3200320000 == 3200320000 |
13 | Correct | 1 ms | 212 KB | contestant found the optimal answer: 140072 == 140072 |
14 | Correct | 1 ms | 212 KB | contestant found the optimal answer: 376041456 == 376041456 |
15 | Correct | 2 ms | 212 KB | contestant found the optimal answer: 805 == 805 |
16 | Correct | 1 ms | 212 KB | contestant found the optimal answer: 900189994 == 900189994 |
17 | Correct | 1 ms | 212 KB | contestant found the optimal answer: 999919994 == 999919994 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2070 ms | 564 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2053 ms | 5844 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 227 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 518 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |