제출 #918241

#제출 시각아이디문제언어결과실행 시간메모리
918241wii수열 (APIO14_sequence)C++17
0 / 100
32 ms131072 KiB
#include <bits/stdc++.h> using namespace std; typedef double db; typedef long long ll; typedef long double ld; #define int ll typedef pair<int, int> pii; #define lx (id << 1) #define rx (lx 1) #define gcd __gcd #define pb push_back #define all(x) (x).begin(), (x).end() #define bit(i, mask) ((mask) >> (i) & 1) #define reset(x, val) memset(x, val, sizeof(x)) #define foru(i,a,b) for(int i = (a); i <= (b); ++i) #define ford(i,a,b) for(int i = (a); i >= (b); --i) #define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; } template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; } const ll Linf = 0x3f3f3f3f3f3f3f3f; const int Inf = 0x3f3f3f3f; const ll Mod = 1e9 + 7; const ll Mod2 = ll(1e9) + 9; const int Lim = 1e6 + 5; const int inv6 = 166666668; // #define Sieve #ifdef Sieve vector<int> pr; vector<int> lpf; void Linear_sieve(int n = Lim) { pr.assign(1, 2); lpf.assign(n + 1, 2); for (int x = 3; x <= n; x += 2) { if (lpf[x] == 2) pr.push_back(lpf[x] = x); for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i) lpf[pr[i] * x] = pr[i]; } } #endif /// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*==== const int base = 3; const int N = 1e5 + 5; const int K = 200 + 1; const int dx[] = {+1, -1, 0, 0}; const int dy[] = {0, 0, +1, -1}; const int block_size = sqrt(2e9) + 2; struct Line { mutable int a, b; Line() = default; Line(int a, int b): a(a), b(b) {} bool operator< (const Line &x) const { return a < x.a; }; int operator() (int x) const { return a * x + b; } }; struct LineContainer { vector<Line> st; int div(int a, int b) { return a / b - ((a ^ b) < 0 && a % b); } ld isect(const Line &x, const Line &y) { return ld(y.b - x.b) / (x.a - y.a); } int bad(const Line &a, const Line &b, const Line &c) { if (b.a == c.a) return true; return isect(a, b) < isect(b, c); } void add(int k, int m) { int top = st.size(); Line l = Line(k, m); while (top >= 2 && bad(st[top - 2], st[top - 1], l)) st.pop_back(), --top; st.push_back(l); } int query(int x) { int l = 0, r = st.size() - 1; while (l < r) { int mid = (l + r) >> 1; if (isect(st[mid], st[mid + 1]) > x) l = mid + 1; else r = mid; } return st[l](x); } }; int n, k; int a[N], pref[N]; int dp[K][N]; LineContainer cht; int f(int l, int r) { return pref[r] - pref[l - 1]; } /** 7 3 4 1 3 4 0 2 3 **/ void solve() { cin >> n >> k; foru(i, 1, n) cin >> a[i]; foru(i, 1, n) pref[i] = pref[i - 1] + a[i]; foru(i, 0, n) foru(z, 0, k) dp[i][z] = -Linf; dp[0][0] = 0; foru(z, 1, k) { cht.st.clear(); foru(i, 1, n - 1) { int j = i - 1; cht.add(-pref[j], dp[z - 1][j]); dp[z][i] = cht.query(f(i + 1, n)) + f(i + 1, n) * pref[i]; } } int ans = -Linf; foru(i, 1, n - 1) maximize(ans, dp[i][k]); cout << ans << "\n"; for (int cur = n - 1, z = k; cur > 0 && z > 0; --cur) { if (dp[z][cur] == ans) { for (int j = 0; j < cur; ++j) if (dp[z - 1][j] + f(j + 1, cur) * f(cur + 1, n) == ans) { cout << cur << " "; cur = j + 1; --z; ans = dp[z][j]; break; } } } } signed main() { FastIO; #define task "" if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } #define task "Test" if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } else if (0) { ofstream fout(task".inp"); fout.close(); freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } #ifdef Sieve Linear_sieve(); #endif int ntest = 1; // cin >> ntest; while (ntest--) { //cout << "Case " << q << ": " << "\n"; solve(); cout << "\n"; } return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/

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

sequence.cpp:167: warning: "task" redefined
  167 |     #define task "Test"
      | 
sequence.cpp:161: note: this is the location of the previous definition
  161 |     #define task ""
      | 
sequence.cpp: In function 'int main()':
sequence.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...