Submission #10405558
Source Code Expand
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
#define endl '\n'
#define F first
#define S second
const int MAX_N=4e2+4;
int n;
int a[MAX_N];
ll dp[MAX_N][MAX_N], na[MAX_N][MAX_N];
int main()
{
memset(dp,0x7F,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]), dp[i][i]=0, na[i][i]=a[i];
for(int d=1;d<n;d++) for(int i=1,j=i+d;j<=n;i++,j++) for(int k=i;k<j;k++)
{
ll tmp=dp[i][k]+dp[k+1][j]+na[i][k]+na[k+1][j];
if(dp[i][j]>tmp)
{
dp[i][j]=tmp;
na[i][j]=na[i][k]+na[k+1][j];
}
else if(dp[i][j]==tmp)
na[i][j]=min(na[i][j],na[i][k]+na[k+1][j]);
}
printf("%lld\n",dp[1][n]);
return 0;
}
Submission Info
Submission Time |
|
Task |
N - Slimes |
User |
lightbulb12294 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
713 Byte |
Status |
AC |
Exec Time |
47 ms |
Memory |
2816 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:17:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:18:68: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%d",&a[i]), dp[i][i]=0, na[i][i]=a[i];
^
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11 |
Case Name |
Status |
Exec Time |
Memory |
0_00 |
AC |
2 ms |
1536 KB |
0_01 |
AC |
2 ms |
1536 KB |
0_02 |
AC |
2 ms |
1536 KB |
0_03 |
AC |
2 ms |
1536 KB |
1_00 |
AC |
2 ms |
1536 KB |
1_01 |
AC |
45 ms |
2816 KB |
1_02 |
AC |
44 ms |
2816 KB |
1_03 |
AC |
44 ms |
2816 KB |
1_04 |
AC |
47 ms |
2816 KB |
1_05 |
AC |
45 ms |
2816 KB |
1_06 |
AC |
47 ms |
2816 KB |
1_07 |
AC |
44 ms |
2816 KB |
1_08 |
AC |
45 ms |
2816 KB |
1_09 |
AC |
45 ms |
2816 KB |
1_10 |
AC |
43 ms |
2816 KB |
1_11 |
AC |
44 ms |
2816 KB |