제출 #918620

#제출 시각아이디문제언어결과실행 시간메모리
918620Boycl07수열 (APIO14_sequence)C++17
0 / 100
28 ms131072 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i = 1; i <= n; ++i) #define forn(i, l, r) for(int i = l; i <= r; ++i) #define ford(i, r, l) for(int i = r; i >= l; --i) #define FOR(i, n) for(int i = 0; i < n; ++i) #define fi first #define se second #define pii pair<int, int> #define pll pair<ll, ll> #define pb push_back #define endl "\n" #define task "split" #define sz(a) int(a.size()) #define C(x, y) make_pair(x, y) #define all(a) (a).begin(), (a).end() #define bit(i, mask) (mask >> i & 1) 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 (res > val){ res = val; return true; }; return false; } inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;} inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;} inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;} const int N = 1e5 + 4; const int M = 3e5 + 3; const int INF = 1e9 + 3; const ll LINF = 1e18; const int A = 26 + 2; const int K = 200 + 3; int n, k; int a[N]; int sum[N]; ll dp[N][K]; int opt[N][K]; ll cost(int i, int j) { return 1ll * (sum[i - 1]) * (sum[j] - sum[i - 1]); } int j = 0; void dnc(int l, int r, int optl, int optr) { if(l > r) return; int mid = l + r >> 1; opt[mid][j] = optl; forn(k, optl, min(optr, mid)) if(maximize(dp[mid][j], dp[k - 1][j - 1] + cost(k, mid))) opt[mid][j] = k; dnc(l, mid - 1, optl, opt[mid][j]); dnc(mid + 1, r, opt[mid][j], optr); } void solve() { cin >> n >> k; rep(i, n) cin >> a[i], sum[i] = sum[i - 1] + a[i]; dp[0][0] = 0; rep(i, n) dp[i][0] = -LINF; rep(_, k + 1) { ++j; forn(i, 0, n) dp[i][j] = -LINF; dnc(1, n, 1, n); } cout << dp[n][k + 1] << endl; int x = n; ford(i, k, 1) { x = opt[x][i + 1]; cout << x - 1 << " "; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int TC = 1; if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } while(TC--) { solve(); cout << endl; } return 0; }

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

sequence.cpp: In function 'void dnc(int, int, int, int)':
sequence.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = l + r >> 1;
      |               ~~^~~
sequence.cpp: In function 'int main()':
sequence.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         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...