oj.uz

답안 #172940

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
172940 2020-01-02T18:37:48 Z RafaelSus 수열 (APIO14_sequence) C++14
0 / 100
 105 ms 85780 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
 
vector<ll>m,b;
vector<int>idx;
int ptr;
int path[N][205];

void add(ll _m,ll _b,int _idx){
  int sz=m.size();
  while(sz>=2&&(_b-b[b.size()-2])*(m[m.size()-2]-m.back())>=(b.back()-b[b.size()-2])*(m[m.size()-2]-_m)){
    m.pop_back();
    b.pop_back();
    idx.pop_back();
    sz--;
  }
  m.pb(_m);
  b.pb(_b);
  idx.pb(_idx);
}
 
ll func(int pos,ll x){
  return m[pos]*x+b[pos];
}
 
pair<ll,int>get(ll x){
  if(ptr>=m.size())ptr=m.size()-1;
  while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x)){
    ptr++;
  }
  return {func(ptr,x),idx[ptr]};
}

void print(int st,int k){
  if(path[st][k]==0){
    //cout<<st<<' ';
    printf("%d ",st);
    return;
  }
  print(path[st][k],k-1);
  //cout<<st<<' ';
  printf("%d ",st);
}
ll dp[2][N];
ll a[N],pref[N];
int main(){
  //ios::sync_with_stdio(false);
  //cin.tie(0);cout.tie(0);
  
  int n,k;
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++){
    //cin>>a[i];
    scanf("%lld",a+i);
    pref[i]=pref[i-1]+a[i];
  }
  
  for(int i=1;i<=n;i++){
    dp[1][i]=pref[i]*(pref[n]-pref[i]);
    path[i][1]=0;
  }
  for(int i=2;i<=k;i++){
    int v=(i-1)%2;
    m.clear();
    b.clear();
    idx.clear();
    ptr=0;
    add(0,0,0);
    for(int j=i-1;j<n;j++){
      if(j==i-1){
        add(-pref[j],dp[v][j],j);
        continue;
      }
      pair<ll,int>tmp=get(pref[n]-pref[j]);
      dp[v^1][j]=tmp.first+pref[n]*pref[j]-pref[j]*pref[j];
      path[j][i]=tmp.second;
      add(-pref[j],dp[v][j],j);
    }
    //cerr<<m.size()<<' '<<b.size()<<' '<<idx.size()<<'\n';
  }
  ll mx=0,st=1;
  for(int i=1;i<n;i++){
    if(dp[k%2][i]>=mx){
      mx=dp[k%2][i];
      st=i;
    }
  }srand(time(0));
  //cout<<mx<<'\n';
  printf("%lld\n",mx);
  if(rand()%2)
  print(st,k);
}

Compilation message

sequence.cpp: In function 'std::pair<long long int, int> get(ll)':
sequence.cpp:33:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr>=m.size())ptr=m.size()-1;
      ~~~^~~~~~~~~~
sequence.cpp:34:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x)){
         ~~~~~^~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&k);
   ~~~~~^~~~~~~~~~~~~~
sequence.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",a+i);
     ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Correct 2 ms 376 KB contestant found the optimal answer: 999 == 999
3 Correct 2 ms 376 KB contestant found the optimal answer: 0 == 0
4 Correct 2 ms 380 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 2 ms 424 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 2 ms 376 KB contestant found the optimal answer: 1 == 1
7 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1272 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 8952 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 105 ms 85780 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -