제출 #416037

#제출 시각아이디문제언어결과실행 시간메모리
416037ti20_ntsonK개의 묶음 (IZhO14_blocks)C++17
0 / 100
21 ms41412 KiB
/// Author :Nguyễn Thái Sơn -Ti20 -THPT chuyên Lương Thế Vinh #include<bits/stdc++.h> #define TASK "test" #define ll long long #define ull unsigned long long #define fi first #define se second #define ti20_ntson int main() #define all(x) (x).begin(),(x).end() #define vi vector<int> #define vii pair<int,int> #define forup(i,l,r) for (int i=l; i<=r; i++) #define fordown(i,l,r) for (int i=l; i>=r; i--) #define getbit(x, i) (((x) >> (i)) & 1) #define vvi vector< vector <int >> using namespace std; const int mod = 1e9+7; const int oo = 1e8; const int maxN = 1e5+5; int n,a[maxN]; int dp[105][maxN],k; void nhap() { cin >> n >> k; for (int i=1; i<=n; i++) cin >> a[i]; } void solve() { memset(dp, 0x3f, sizeof dp); dp[1][0] = 0; for (int i =1; i<=n; i++) dp[1][i] = max (dp[1][i-1],a[i]); for (int i=2; i<=k; i++) { stack < vii > S; for (int j=i; j <= n; j++) { int res = dp[i-1][j-1]; while (!S.empty() && a[S.top().second] <= a[j]) { res = min(res, S.top().first); S.pop(); } dp[i][j] = min(dp[i][S.empty() ? 0 : S.top().second], res + a[j]); // cout << i << " " << j << " " << dp[i][j] << endl; cout << res << endl; S.push({res,j}); } } cout << dp[k][n]; } ti20_ntson { // freopen(TASK".INP","r",stdin); // freopen(TASK".OUT","w",stdout); ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0); int T =1; // cin >> T; while (T--) { nhap(); solve(); } } /* input 4 5 2 3 4 5 56 outpt 4455 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...