oj.uz

Submission #23161

# Submission time Handle Problem Language Result Execution time Memory
23161 2017-05-03T18:10:58 Z ngkan146 Split the sequence (APIO14_sequence) C++
0 / 100
 66 ms 89064 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,a[100005];
vector <ll> dp[205];
int last[100005][205];
vector <ll> B;
vector <int> M, ID;
bool check(int id){
   return (B[id] - B[id-2]) * (M[id-2] - M[id-1]) <= (B[id-1] - B[id-2]) * (M[id-2] - M[id]);
}
void add_line(ll slope,ll val,ll id){
   M.push_back(slope);
   B.push_back(val);
   ID.push_back(id);
   while(M.size() >= 2 && M[M.size()-2] == M[M.size()-1]){
      if (B[M.size()-2] <= B[M.size()-1]){
         M.erase(M.end()-2);
         B.erase(B.end()-2);
         ID.erase(ID.end()-2);
      }
      else{
         M.erase(M.end()-1);
         B.erase(B.end()-1);
         ID.erase(ID.end()-1);
      }
   }
   while(M.size() >= 3 && check(M.size()-1)) ID.erase(ID.end()-2), M.erase(M.end()-2), B.erase(B.end()-2);
}
int ctrl;
ll get(ll x){
   ctrl = min(ctrl, (int)M.size()-1);
   while(ctrl < M.size()-1 && M[ctrl] * x + B[ctrl] <= M[ctrl+1] * x + B[ctrl+1])
      ++ctrl;
   return ctrl;
}
int main(){
   scanf("%d %d",&n,&k);
   k++;
   for(int i=1;i<=n;i++)
      scanf("%d",&a[i]),
      a[i] += a[i-1];
   dp[0].assign(n+5,-(ll) 1e18);
   dp[0][0] = 0;
   for(int t=1;t<=k;t++){
      M.clear(); B.clear(); ID.clear();
      add_line(0,0,0);
      if (t >= 2) dp[t-2].clear();
      dp[t].assign(n+5,0);
      for(int i=1;i<=n;i++){
         int id = get(a[i]);
         dp[t][i] = M[id] * a[i] + B[id];
         last[i][t] = ID[id];
         add_line(a[i], dp[t-1][i] - 1ll * a[i] * a[i], i);
      }
   }
   vector <int> res;
   int mjk = n;
   for(int t=k;t>1;t--){
      res.push_back(last[mjk][t]);
      mjk = last[mjk][t];
   }
   reverse(res.begin(),res.end());
   printf("%lld\n",dp[k][n]);
   for(int i=0;i<res.size();i++) printf("%d ",res[i]);
   //cout << endl; for(int i=0;i<res.size();i++) cout << dp[i+1][res[i]] << ' ';
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message

sequence.cpp: In function 'long long int get(long long int)':
sequence.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(ctrl < M.size()-1 && M[ctrl] * x + B[ctrl] <= M[ctrl+1] * x + B[ctrl+1])
               ^
sequence.cpp: In function 'int main()':
sequence.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<res.size();i++) printf("%d ",res[i]);
                 ^
sequence.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&n,&k);
                        ^
sequence.cpp:42:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       a[i] += a[i-1];
                     ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 82500 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 82500 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 82500 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 82500 KB contestant found the optimal answer: 1542524 == 1542524
5 Incorrect 0 ms 82500 KB Integer 0 violates the range [1, 9]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 82500 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 82500 KB contestant found the optimal answer: 302460000 == 302460000
3 Incorrect 0 ms 82500 KB Integer 0 violates the range [1, 49]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 82500 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 82500 KB contestant found the optimal answer: 311760000 == 311760000
3 Incorrect 0 ms 82896 KB Integer 0 violates the range [1, 199]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 82632 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 0 ms 82632 KB contestant found the optimal answer: 140412195 == 140412195
3 Incorrect 6 ms 84100 KB Integer 0 violates the range [1, 999]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 83160 KB declared answer doesn't correspond to the split scheme: declared = -2476288992, real = 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 89064 KB declared answer doesn't correspond to the split scheme: declared = -9626222975, real = 16143580801
2 Halted 0 ms 0 KB -