oj.uz

Submission #227517

# Submission time Handle Problem Language Result Execution time Memory
227517 2020-04-27T16:00:13 Z DavidDamian Kisik (COCI19_kisik) C++11
0 / 90
 141 ms 16128 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -