제출 #88510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88510		ABCD	K개의 묶음 (IZhO14_blocks)	C++14	0 / 100	4 ms	696 KiB

blocks

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int N=1e5+5;
const int oo=1e8+5;

int m;
int n,k;
int a[N];
int IT[N*8];
int F[N][105];


void build(int k,int l,int r){
    if(l>r) return;
    if(l==r){
        IT[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    IT[k]=max(IT[k*2],IT[k*2+1]);
}

int getmax(int k,int l,int r,int u,int v){
    if(r<u||l>v)
        return 0;
    if(l>=u&&r<=v)
        return IT[k];
    int mid=(l+r)/2;
    return max(getmax(k*2,l,mid,u,v),getmax(k*2+1,mid+1,r,u,v));
}

/*
void Solve(){
    FOR(i,1,k) FOR(j,i,n)
        F[i][j]=F[i-1][j-1]+getmax(1,1,n,j,n);
    cout<<F[k][n];
}*/

int Try(int n,int k){
    if(k==1) return getmax(1,1,m,1,n);
    if(F[n][k]) return F[n][k];
    int tmp=oo+5;
    for(int i=n;i>=max(2,k);i--){
        int t=getmax(1,1,m,i,n);
        tmp=min(tmp,t+Try(i-1,k-1));
    }
    F[n][k]=tmp;
    return F[n][k];
}

main(){
    freopen("blocks.in","r",stdin);
    freopen("blocks.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    FOR(i,1,n) cin>>a[i];
    build(1,1,n);
    m=n;
    int t=Try(n,k);
    cout<<Try(n,k);
}

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

blocks.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
blocks.cpp: In function 'int main()':
blocks.cpp:64:9: warning: unused variable 't' [-Wunused-variable]
     int t=Try(n,k);
         ^
blocks.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("blocks.in","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("blocks.out","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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