oj.uz

Submission #337137

# Submission time Handle Problem Language Result Execution time Memory
337137 2020-12-18T15:24:16 Z bigDuck Split the sequence (APIO14_sequence) C++14
50 / 100
 176 ms 12544 KB 
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, a[300010], q, l, r;
int dp[1010][210];
int p[1010];
int dir[1010][210];
vector<int> v;


int32_t main(){
INIT
scanf("%d", &n);
scanf("%d" , &k);
for(int i=1; i<=n ;i++){
    scanf("%d", &a[i]);
    p[i]=p[i-1]+a[i];
}

dp[0][0]=0;
for(int g=1; g<=(k+1); g++){
    dp[0][g]=-1;
}
k++;

for(int i=1; i<=n; i++){
    for(int g=0; g<=k; g++){
        dp[i][g]=-1;
    }
    for(int j=i-1; j>=0; j--){
        for(int g=0; g<k; g++){
            if(dp[j][g]==-1){continue;}
            if(dp[i][g+1]==(-1)){
                dp[i][g+1]=dp[j][g]+(p[i]-p[j])*(p[i]-p[j]);
                dir[i][g+1]=j;
            }
            else{
                    if(  (dp[j][g]+(p[i]-p[j])*(p[i]-p[j]))<dp[i][g+1] ){
                        dir[i][g+1]=j;
                    }
                dp[i][g+1]=min(dp[i][g+1], dp[j][g]+(p[i]-p[j])*(p[i]-p[j]));
            }
        }
    }
}

cout<<( ((p[n]*p[n])-dp[n][k])/2 );
cout<<"\n";
int cnt=1, cr=n;
while(cnt<k){
    v.pb(dir[cr][k-cnt+1]);
    cr=dir[cr][k-cnt+1];
    cnt++;
}
for(int i=k-1-1; i>=0; i--){
    cout<<v[i]<<" ";
}



return 0;
}

Compilation message

sequence.cpp: In function 'int32_t main()':
sequence.cpp:22:9: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   22 | scanf("%d", &n);
      |        ~^   ~~
      |         |   |
      |         |   long long int*
      |         int*
      |        %lld
sequence.cpp:23:9: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   23 | scanf("%d" , &k);
      |        ~^    ~~
      |         |    |
      |         int* long long int*
      |        %lld
sequence.cpp:25:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   25 |     scanf("%d", &a[i]);
      |            ~^   ~~~~~
      |             |   |
      |             |   long long int*
      |             int*
      |            %lld
sequence.cpp:22:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 | scanf("%d", &n);
      | ~~~~~^~~~~~~~~~
sequence.cpp:23:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 | scanf("%d" , &k);
      | ~~~~~^~~~~~~~~~~
sequence.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 364 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 364 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 364 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 1 ms 364 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 1 ms 364 KB contestant found the optimal answer: 1 == 1
7 Correct 1 ms 364 KB contestant found the optimal answer: 1 == 1
8 Correct 1 ms 364 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 364 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 1 ms 364 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 1 ms 364 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 1 ms 364 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 1 ms 364 KB contestant found the optimal answer: 140072 == 140072
14 Correct 1 ms 364 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 1 ms 364 KB contestant found the optimal answer: 805 == 805
16 Correct 1 ms 364 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 1 ms 364 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 492 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 1 ms 492 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 492 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 1 ms 492 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 1 ms 492 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 492 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 1 ms 492 KB contestant found the optimal answer: 687136 == 687136
9 Correct 1 ms 492 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 1 ms 492 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 1004 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 6 ms 1004 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 1004 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 5 ms 1004 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 5 ms 1004 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 6 ms 1004 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 3 ms 1004 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 2 ms 1004 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 3 ms 1004 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3692 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 8 ms 3692 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 176 ms 3692 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 7 ms 3692 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 172 ms 3692 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 153 ms 3692 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 173 ms 3692 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 173 ms 3692 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 50 ms 3692 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 82 ms 3692 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

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