oj.uz

Submission #227518

# Submission time Handle Problem Language Result Execution time Memory
227518 2020-04-27T16:02:42 Z DavidDamian Kisik (COCI19_kisik) C++11
0 / 90
 139 ms 32512 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct rect
{
    ll w;
    ll 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 && dp[i][k].h==-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:66:8: warning: 'opt.rect::w' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll area=opt.w*opt.h;
        ^~~~
kisik.cpp:66: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 22 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 139 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 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 58 ms 16156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 32384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 32504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 32504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 32384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 32512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -