제출 #41291

#제출 시각아이디문제언어결과실행 시간메모리
41291IvanCK개의 묶음 (IZhO14_blocks)C++14
53 / 100
1076 ms4964 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; const int INF = 1e9; const int MAXN = 1e5 + 10; const int MAXK = 101; int vetor[MAXN],dp[MAXN],esq[MAXN],dir[MAXN],N,K; ii seg[4*MAXN]; void build(int pos,int left,int right){ //printf("Build1 %d %d %d\n",pos,left,right); if(left == right){ seg[pos] = ii(dp[left],left); return; } int mid = (left+right)/2; build(2*pos,left,mid); build(2*pos+1,mid+1,right); seg[pos] = max(seg[2*pos],seg[2*pos+1]); } ii query(int pos,int left,int right,int i,int j){ //printf("Query1 %d %d %d %d\n",pos,left,right,i,j); if(left >= i && right <= j) return seg[pos]; int mid = (left+right)/2; if(j <= mid) return query(2*pos,left,mid,i,j); else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j); return max(query(2*pos,left,mid,i,j),query(2*pos+1,mid+1,right,i,j)); } void intervals(int ini,int fim){ //printf("Intervals %d %d\n",ini,fim); if(ini > fim) return; int maioral = query(1,1,N,ini,fim).second; esq[maioral] = ini; dir[maioral] = fim; intervals(ini,maioral-1); intervals(maioral+1,fim); } void build2(int pos,int left,int right){ //printf("Build2 %d %d %d\n",pos,left,right); if(left == right){ seg[pos] = ii(dp[left],left); return; } int mid = (left+right)/2; build2(2*pos,left,mid); build2(2*pos+1,mid+1,right); seg[pos] = min(seg[2*pos],seg[2*pos+1]); } ii query2(int pos,int left,int right,int i,int j){ //printf("Query2 %d %d %d %d\n",pos,left,right,i,j); if(left >= i && right <= j) return seg[pos]; int mid = (left+right)/2; if(j <= mid) return query2(2*pos,left,mid,i,j); else if(i >= mid + 1) return query2(2*pos+1,mid+1,right,i,j); return min(query2(2*pos,left,mid,i,j),query2(2*pos+1,mid+1,right,i,j)); } void solve(int k){ for(int i = 0;i<k-1;i++) dp[i] = INF; vector<ii> sweep; multiset<int> valores; build2(1,1,N); for(int i = 1;i<=N;i++){ int lo = max(esq[i] - 1,1); int hi = i - 1; if(lo > hi || max(lo,hi) <= 0) continue; int novo = query2(1,1,N,lo,hi).first + vetor[i]; sweep.push_back(ii(i,novo)); sweep.push_back(ii(dir[i] + 1,-novo)); } //printf("Ok1\n"); sort(sweep.begin(),sweep.end()); int ptr = 0; for(int i = k;i<=N;i++){ //printf("Sweep\n"); while(ptr < sweep.size() && sweep[ptr].first <= i){ //printf("While\n"); int val = sweep[ptr].second; if(val > 0){ valores.insert(val); } else{ valores.erase(valores.find(-val)); } ptr++; } if(valores.empty()){ dp[i] = INF; } else{ dp[i] = (*valores.begin()); } } //printf("Ok2\n"); sweep.clear(); valores.clear(); } int main(){ scanf("%d %d",&N,&K); for(int i = 1;i<=N;i++){ scanf("%d",&vetor[i]); dp[i] = vetor[i]; } build(1,1,N); intervals(1,N); for(int i = 1;i<=N;i++) dp[i] = query(1,1,N,1,i).first; for(int k = 2;k<=K;k++) solve(k); printf("%d\n",dp[N]); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

blocks.cpp: In function 'void solve(int)':
blocks.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < sweep.size() && sweep[ptr].first <= i){
             ^
blocks.cpp: In function 'int main()':
blocks.cpp:97:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&K);
                      ^
blocks.cpp:99:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&vetor[i]);
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...