제출 #1304789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304789		maithedung	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	162 ms	80964 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define exit return 0
#define cap pair<int,int>
#define fi first
#define se second
#define pb push_back
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define fill(f,x) memset(f,x,sizeof(f))
#define lcm(a,b) (a/__gcd(a,b)*b)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
int F[105][100005]; 
int A[1000005]; 
signed main()
{
    fast;
    int n,k; 
    cin>>n>>k; 
    FOR(i,0,n) FOR(j,0,k) F[j][i]=1e18; 
    F[0][0]=0; 
    FOR(i,1,n) cin>>A[i]; 
   //  for (int i = 1; i <= n; ++i) F[1][i] = max(F[1][i - 1], A[i]);
    FOR(i,1,k)
    {
        deque<cap> q; 
        FOR(j,1,n)
        {
            int minf=F[i-1][j-1]; 
            while(q.size() && A[q.back().second]<=A[j])
            {
                minf=min(minf,q.back().first); 
                q.pop_back(); 
            }
            if(q.size()) F[i][j]=min(F[i][q.back().second],minf+A[j]);
            else F[i][j]=minf+A[j]; 
            q.push_back({minf,j}); 
        }
    }
    cout<<F[k][n]; 
    exit;
}
/*
░▒▓███████▓▒░░▒▓█▓▒░░▒▓█▓▒░▒▓███████▓▒░ ░▒▓██████▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒▒▓███▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓███████▓▒░ ░▒▓██████▓▒░░▒▓█▓▒░░▒▓█▓▒░░▒▓██████▓▒░
*/

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47