제출 #1083218

#제출 시각아이디문제언어결과실행 시간메모리
1083218kiethm07수열 (APIO14_sequence)C++11
33 / 100
56 ms131072 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define iii pair<int,pii> #define fi first #define se second #define vi vector<int> #define vii vector<pii> #define pb(i) push_back(i) #define all(x) x.begin(),x.end() #define TEXT "a" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int inf = 1e9 + 7; const ld eps = 1e-8; const double pi = acos(-1); const int N = 1e5 + 5; const int K = 205; int n,k; ll p[N]; ll dp[N][K]; int pre[N][K]; struct line{ ll a,b; int id; line(ll _a, ll _b, int _id){ a = _a; b = _b; id = _id; } ll eval(ll x){ return a * x + b; } double isect(const line& F) const{ return 1.0 * (F.b - b) / (a - F.a); } }; struct CHT{ deque<line> dq; void add(line F){ int n = dq.size(); while(n >= 2 && dq[n - 2].isect(dq[n - 1]) >= F.isect(dq[n - 1])){ n--; dq.pop_back(); } dq.push_back(F); } pair<ll,ll> query(ll x){ int n = dq.size(); while(n >= 2 && dq[0].eval(x) <= dq[1].eval(x)){ n--; dq.pop_front(); } return make_pair(dq[0].eval(x),dq[0].id); } }; int main(){ cin.tie(0) -> sync_with_stdio(0); if (fopen(TEXT".inp","r")){ freopen(TEXT".inp","r",stdin); freopen(TEXT".out","w",stdout); } cin >> n >> k; for (int i = 1; i <= n; i++){ cin >> p[i]; p[i] += p[i - 1]; } for (int used = 1; used <= k; used++){ CHT c; c.add(line(0,0,0)); for (int i = 1; i < n; i++){ // for (int j = 0; j < i; j++){ // dp[i][used] = max(dp[i][used], dp[j][used - 1] + (p[i] - p[j]) * (p[n] - p[i])); // if (dp[i][used] == dp[j][used - 1] + (p[i] - p[j]) * (p[n] - p[i])) pre[i][used] = j; // } auto tmp = c.query(-(p[n] - p[i])); dp[i][used] = p[i] * (p[n] - p[i]) + tmp.fi; pre[i][used] = tmp.se; c.add(line(p[i], dp[i][used - 1], i)); } } int best = 0; for (int i = 1; i < n; i++){ if (dp[i][k] >= dp[best][k]) best = i; } cout << dp[best][k] << "\n"; vector<int> v; for (int used = k; used >= 1; used--){ v.push_back(best); best = pre[best][used]; } reverse(all(v)); for (int i : v){ if (i == 0) cout << "LMAO\n"; cout << i << " "; } return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(TEXT".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...