이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
#define ll long long
vector<pair<int,bool>>pct;
ll dp[200005],last[200005];
int t[200005],cnt[200005];
ll calc(int l,int r)
{
int aux=t[r],st=r+1-aux,dr=aux-l;
ll ans=last[r+1]-last[aux]-last[aux]+last[l];
if (st>dr)
ans=ans-1LL*(st-dr)*pct[aux-1].first;
if (st<dr)
ans=ans+1LL*(dr-st)*pct[aux].first;
return ans;
}
ll min_total_length(vector<int>red,vector<int>blue)
{
int n=blue.size(),m=red.size();
int i;
for(i=0;i<n;i++)
pct.push_back(make_pair(blue[i],1));
for(i=0;i<m;i++)
pct.push_back(make_pair(red[i],0));
sort(pct.begin(),pct.end());
n=n+m;
for(i=1;i<=n;i++)
t[i]=t[i-1]+pct[i-1].first;
ll *dp=&(::dp[1]);
memset(dp,50,sizeof(dp));
int j;
for(i=1;i<n;i++){
t[i]=t[i-1];
if (pct[i].second!=pct[i-1].second){
int pre=t[i];
t[i]=i;
dp[i]=dp[i-1]+calc(i-1,i);
cnt[i]=1;
for(j=pre;j<i;j++)
if (dp[i]>dp[j-1]+calc(j,i))
cnt[i]=i-j,dp[j]=dp[j-1]+calc(j,i);
}
else
if (t[i]>0){
cnt[i]=cnt[i-1];
j=t[i]-cnt[i];
if (cnt[i-1]==i-t[i])
if (j>t[j] && dp[j-1]+calc(j,i)>dp[j-2]+calc(j-1,i))
cnt[i]++,j--;
dp[i]=min(dp[j],dp[j-1])+calc(j,i);
}
}
return dp[n-1];
}
컴파일 시 표준 에러 (stderr) 메시지
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:31:18: warning: argument to 'sizeof' in 'void* memset(void*, int, size_t)' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
31 | memset(dp,50,sizeof(dp));
| ^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |