제출 #41983

#제출 시각아이디문제언어결과실행 시간메모리
41983fest수열 (APIO14_sequence)C++14
0 / 100
2 ms300 KiB
// fest #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define y1 dasdasfasfas #define x1 wqdadfasfasfas #define All(c) c.begin(), c.end() #define SZ(A) (int((A).size())) #define umap unordered_map #define FILENAME "" #define __ fflush(stdout) typedef long long ll; typedef long double ld; using namespace std; void FREOPEN() { #ifdef COMP freopen(".in", "r", stdin); freopen("1.out", "w", stdout); #endif } inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } const int N = 100001, M = 111, inf = 1e9 * 2, MOD = (int)1e9 + 7; char CH[N]; const double eps = 1e-14; const ll INF = 1e18; const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1}; const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1}; int pref[N], a[N], pr[N][M]; ll dp[N][M]; vector<pair<int, pair<ll, int> > > lines; double meet(int a1, ll b1, int a2, ll b2) { return (double)(b2 - b1) / (double)(a1 - a2); } void calc(int real, int n, int k) { for (int i = 0; i <= n; i++) dp[i][0] = -INF, pr[i][0] = -1; dp[0][0] = 0; for (int bl = 1; bl <= k; bl++) { for (int i = 0; i <= n; i++) dp[i][bl % M] = -INF, pr[i][bl % M] = - 1; lines.clear(); lines.pb({-pref[bl - 1], {dp[bl - 1][(bl - 1) % M], bl - 1}}); int lef = 0; for (int i = bl; i <= n; i++) { int x = pref[real] - pref[i]; while (lef + 1 < SZ(lines) && x * 1ll * lines[lef].F + lines[lef].S.F < x * 1ll * lines[lef + 1].F + lines[lef + 1].S.F) lef++; dp[i][bl % M] = x * 1ll * pref[i] + x * 1ll * lines[lef].F + lines[lef].S.F; pr[i][bl % M] = lines[lef].S.S; while (SZ(lines) >= 2 && meet(lines.back().F, lines.back().S.F, -pref[i], dp[i][(bl - 1) % M]) > meet(lines[SZ(lines) - 2].F, lines[SZ(lines) - 2].S.F, -pref[i], dp[i][(bl - 1) % M]) - eps) lines.pop_back(); while (!lines.empty() && lines.back().F == -pref[i] && lines.back().S.F == dp[i][(bl - 1) % M]) lines.pop_back(); lines.pb({-pref[i], {dp[i][(bl - 1) % M], i}}); if (lef >= SZ(lines)) lef = SZ(lines) - 1; } } } int main() { FREOPEN(); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) scanf("%d ", a + i); for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i]; calc(n, n, k); int pos = 0; ll ans = -INF; for (int i = 1; i <= n; i++) { if (ans < dp[i][k % M]) { ans = dp[i][k % M]; pos = i; } } vector<int> out; cout << ans << endl; int bl = k; while (true) { int last = bl % M; bool ok = 0; for (int i = last; bl > 0; i = (i - 1 + M) % M, bl--) { if (ok && i == last) break; out.pb(pos); pos = pr[pos][i]; ok = 1; } if (!bl) break; calc(n, pos, bl); } sort(All(out)); for (auto i : out) printf("%d ", i); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:76:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d ", a + i);
                                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...