Submission #581265

#	Time	Username	Problem	Language	Result	Execution time	Memory
581265		yutabi	K blocks (IZhO14_blocks)	C++14	14 / 100	1 ms	468 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;

int k;

ll nums[100007];


ll ans[11][100007];

int main()
{
    scanf("%d %d",&n,&k);

    for(int i=0;i<n;i++)
    {
        scanf(" %d",&nums[i]);
    }

    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            ans[j][i]=-1;
        }
    }

    ans[0][0]=0;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<k;j++)
        {
            ll mini=-1;

            ll maxi=0;

            for(int l=i;l>=0;l--)
            {
                maxi=max(maxi,nums[l]);

                if(ans[j][l]!=-1 && (mini==-1 || ans[j][l]+maxi<mini))
                {
                    mini=ans[j][l]+maxi;
                }
            }

            ans[j+1][i+1]=mini;
        }
    }

    /*for(int i=0;i<=k;i++)
    {
        for(int j=0;j<=n;j++)
        {
            printf("%lld ",ans[i][j]);
        }

        printf("\n");
    }*/

    printf("%lld\n",ans[k][n]);


}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:21:18: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   21 |         scanf(" %d",&nums[i]);
      |                 ~^  ~~~~~~~~
      |                  |  |
      |                  |  ll* {aka long long int*}
      |                  int*
      |                 %lld
blocks.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
blocks.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf(" %d",&nums[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

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