# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
648884 | 2022-10-08T16:11:20 Z | messiuuuuu | Teams (CEOI11_tea) | C++14 | 457 ms | 32544 KB |
/// #include<bits/stdc++.h> #define task "C" #define ll long long #define ld long double #define fi first #define se second #define pb push_back using namespace std; const int MAXN = 1e6 + 5; const ll INF = 1e9 + 5; int n, a[MAXN]; void Input() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; } int cs[MAXN]; int dp[MAXN], last[MAXN], tsz[MAXN]; int Cal(int lim) { dp[n] = 0; for (int i = 1; i <= n; i++) { int x = a[cs[i]]; if (i < x || (dp[last[i - x]] + 1 < dp[last[i - 1]] && i < n)) { last[i] = last[i - 1]; } else { int sz = i - last[i - x]; int newdp = dp[last[i - x]] + 1; if (sz <= lim && (i == n || newdp >= dp[last[i - 1]])) { last[i] = i; dp[i] = newdp; tsz[i] = sz; } else { last[i] = last[i - 1]; } } } return dp[n]; } void Solve() { iota(cs + 1, cs + n + 1, 1); sort(cs + 1, cs + n + 1, [](int i, int j) { return a[i] < a[j]; }); int t = Cal(n); int l = 1, r = n; while (l <= r) { int mid = (l + r) >> 1; if (Cal(mid) == t) { r = mid - 1; } else { l = mid + 1; } } Cal(l); cout << dp[n] << '\n'; int p = n; while (p > 0) { int sz = tsz[p]; cout << sz << ' '; for (int i = 0; i < sz; i++, p--) { cout << cs[p] << ' '; } cout << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(task".INP","r")) { freopen(task".INP","r",stdin); //freopen(task".OUT","w",stdout); } Input(); Solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 352 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 464 KB | Output is correct |
2 | Correct | 2 ms | 468 KB | Output is correct |
3 | Correct | 2 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 468 KB | Output is correct |
2 | Correct | 2 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 2684 KB | Output is correct |
2 | Correct | 22 ms | 2496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 3020 KB | Output is correct |
2 | Correct | 19 ms | 2424 KB | Output is correct |
3 | Correct | 26 ms | 3072 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 251 ms | 23800 KB | Output is correct |
2 | Correct | 222 ms | 22400 KB | Output is correct |
3 | Correct | 252 ms | 24092 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 341 ms | 32076 KB | Output is correct |
2 | Correct | 320 ms | 31724 KB | Output is correct |
3 | Correct | 331 ms | 29776 KB | Output is correct |
4 | Correct | 387 ms | 28368 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 388 ms | 30460 KB | Output is correct |
2 | Correct | 268 ms | 26692 KB | Output is correct |
3 | Correct | 335 ms | 30676 KB | Output is correct |
4 | Correct | 457 ms | 32544 KB | Output is correct |