CSES - Leirikisa 6.3.2017 - Results
Submission details
Task:Aitaus
Sender:Kuha
Submission time:2017-03-06 18:25:30 +0200
Language:C++
Status:READY
Result:56
Feedback
groupverdictscore
#1ACCEPTED21
#2ACCEPTED35
#30
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1details
#2ACCEPTED0.04 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.07 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.07 s2details
#9ACCEPTED0.07 s2details
#10ACCEPTED0.05 s2details
#110.25 s3details
#120.24 s3details
#130.28 s3details
#140.27 s3details
#150.28 s3details

Code

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define pllk pair<long long, long long>
#define M 1000000007
#define INF 0x5ADFACE5
#define LINF 0x51DEEFFEC7C0DECALL
#define N (1<<17)
using namespace std;
ll dp[1111][1111];
ll o[1111][1111];
ll s[1111];
int main () {
ll n;
cin>>n;
vector<ll> v(n + 1);
for (ll i = 1; i <= n; i++) {
cin>>v[i];
}
sort(v.begin() + 1, v.end());
for (ll i = 1; i <= n; i++) s[i] = v[i] + s[i - 1];
for (ll l = 1; l <= n; l++) {
for (ll x = 1; x <= n; x++) {
ll y = x + l - 1;
if (y > n) continue;
if (l == 1) continue;
if (l == 2) {
o[x][y] = x;
dp[x][y] = s[y] - s[x - 1];
} else {
dp[x][y] = LINF;
for (ll k = max(o[x][y - 1], (x + y) / 2); k <= o[x + 1][y]; k++) {
ll p = dp[x][y];
dp[x][y] = min(dp[x][y], dp[x][k] + dp[k + 1][y]);
if (p != dp[x][y]) o[x][y] = k;
}
dp[x][y] += s[y] - s[x - 1];
}
}
}
cout<<dp[1][n]<<endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1

correct output
34

user output
34

Test 2

Group: 1

Verdict: ACCEPTED

input
10
1000 1000 1000 1000 1000 1000 ...

correct output
34000

user output
34000

Test 3

Group: 1

Verdict: ACCEPTED

input
10
713 590 643 971 889 796 972 3 ...

correct output
18501

user output
18501

Test 4

Group: 1

Verdict: ACCEPTED

input
10
991 740 433 558 522 338 240 27...

correct output
15614

user output
15614

Test 5

Group: 1

Verdict: ACCEPTED

input
10
397 775 568 796 632 898 214 84...

correct output
20791

user output
20791

Test 6

Group: 2

Verdict: ACCEPTED

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
9976

user output
9976

Test 7

Group: 2

Verdict: ACCEPTED

input
1000
1000000000 1000000000 10000000...

correct output
9976000000000

user output
9976000000000

Test 8

Group: 2

Verdict: ACCEPTED

input
1000
377480143 777745434 296992200 ...

correct output
4829974948360

user output
4829974948360

Test 9

Group: 2

Verdict: ACCEPTED

input
1000
599885439 985529375 118284730 ...

correct output
4880180545408

user output
4880180545408

Test 10

Group: 2

Verdict: ACCEPTED

input
1000
695015028 950574688 862418845 ...

correct output
5089402448969

user output
5089402448969

Test 11

Group: 3

Verdict:

input
100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1668928

user output
(empty)

Test 12

Group: 3

Verdict:

input
100000
1000000000 1000000000 10000000...

correct output
1668928000000000

user output
(empty)

Test 13

Group: 3

Verdict:

input
100000
391395666 905124111 713186504 ...

correct output
818091245007558

user output
(empty)

Test 14

Group: 3

Verdict:

input
100000
535008265 825579494 118746814 ...

correct output
819167891088786

user output
(empty)

Test 15

Group: 3

Verdict:

input
100000
386356481 309596857 386341601 ...

correct output
816647450882063

user output
(empty)