Submission #227517

#	Time	Username	Problem	Language	Result	Execution time	Memory
227517		DavidDamian	Kisik (COCI19_kisik)	C++11	0 / 90	141 ms	16128 KiB

kisik

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct rect
{
    ll w;
    ll h;
};
ostream& operator<<(ostream& os,rect x)
{
    return os<<x.w<<" "<<x.h;
}
rect A[1005];
rect sum[1005];
rect dp[1005][1005];
rect minArea(int i,int k)
{
    if(k==1)
        return A[i];
    if(i==k)
        return sum[i];
    if(dp[i][k].w==-1){
        ll minimum=LLONG_MAX;
        for(int j=1;j<=i-k+1;j++){
            rect comb=minArea(i-j,k-1);
            comb.w+=A[i].w;
            comb.h=max(comb.h,A[i].h);
            ll area=comb.w*comb.h;
            if(area<minimum){
                minimum=area;
                dp[i][k]=comb;
            }
        }
    }
    return dp[i][k];
}
int n,k;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    for(int i=0;i<=1000;i++){
        for(int j=0;j<=1000;j++){
            dp[i][j]={-1,-1};
        }
    }
    cin>>n>>k;
    if(n>1000){
        cout<<1;
        return 0;
    }
    for(int i=1;i<=n;i++){
        cin>>A[i].w>>A[i].h;
    }
    sum[1]=A[1];
    for(int i=2;i<=k;i++){
        sum[i]=sum[i-1];
        sum[i].w+=A[i].w;
        sum[i].h=max(sum[i].h,A[i].h);
    }
    rect opt;
    ll minimum=LLONG_MAX;
    for(int i=k;i<=n;i++){
        rect comb=minArea(i,k);
        ll area=comb.w*comb.h;
        if(area<minimum){
            minimum=area;
            opt=comb;
        }
    }
    ll area=opt.w*opt.h;
    cout<<area<<'\n';
    return 0;
}

Compilation message (stderr)

kisik.cpp: In function 'int main()':
kisik.cpp:70:8: warning: 'opt.rect::w' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll area=opt.w*opt.h;
        ^~~~
kisik.cpp:70:8: warning: 'opt.rect::h' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10