제출 #498478

#제출 시각아이디문제언어결과실행 시간메모리
498478Nalrimet수열 (APIO14_sequence)C++17
0 / 100
65 ms131076 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define ll long long #define ld long double #define pb push_back #define S second #define F first //const int inf = 1e18; const int N = 100005; const ll inf = 1e18; int n, y, k, par[N][205], k1, ind; ll a[N], b[N], pref[N], suma, dp[N][205], sz[N][205]; bool cut[N][205], used[N]; vector<int> ans; ll f(int i, int j, int m){ // if(dp[m][j - 1] == -inf) return -inf; // cout << i << ' ' << j << ' ' << m << '\n'; // cout << dp[m][j - 1] << ' ' << (pref[i] - pref[m]) << ' ' << (pref[n] - pref[i]) << '\n'; return dp[m][j - 1] + (pref[i] - pref[m]) * (pref[n] - pref[i]); // // (a - b) * (c - a) // ac-a^2-bc+ab // -(a * a) + (ab) // a(b-a) // pref[n] * // -pref[i] * // // pref[m] * // (pref[i]*pref[n])-(pref[i] * pref[i]) + pref[m] * pref[i] - pref[m]*pref[n] // dp[m][j - 1] + } main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; k1 = k; k++; dp[0][k] = -1; for(int i = 1; i <= n; ++i){ cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } for(int j = 2; j <= k; ++j){ for(int i = 1; i <= n; ++i){ dp[i][j] = -1; if(f(i, j, i - 1) > dp[i][j]){ dp[i][j] = max(dp[i][j], f(i, j, i - 1)); par[i][j] = i - 1; sz[i][j] = sz[i - 1][j - 1] + 1; } if(f(i, j, par[i - 1][j]) > dp[i][j]){ dp[i][j] = max(dp[i][j], f(i, j, par[i - 1][j])); par[i][j] = par[i - 1][j]; sz[i][j] = sz[i - 1][j]; } // cout << i << ' ' << j << ' ' << dp[i][j] << '\n'; } } for(int i = n - 1; i >= 1; --i){ if(sz[i][k] == k - 1 && dp[i][k] > dp[ind][k]){ ind = i; } } cout << dp[ind][k] << '\n'; while(ind != 0){ ans.pb(ind); ind = par[ind][k]; k--; } reverse(ans.begin(), ans.end()); for(auto to : ans){ cout << to << ' '; } }

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

sequence.cpp:37:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 |  main(){
      |  ^~~~
#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...