제출 #958937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958937		MilosMilutinovic	Telefoni (COCI17_telefoni)	C++14	80 / 80	69 ms	8048 KiB

telefoni

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,d;
int a[300005],dp[300005],mini[1200005];

void build(int id,int l,int r){
	if(l==r) return (void)(mini[id]=dp[l]);
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	mini[id]=min(mini[id<<1],mini[id<<1|1]);
}

int query(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return mini[id];
	int mid=(l+r)/2;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return min(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
}

void modify(int id,int l,int r,int p,int v){
	if(l==r) return (void)(chkmin(mini[id],v));
	int mid=(l+r)/2;
	if(p<=mid) modify(id<<1,l,mid,p,v);
	else modify(id<<1|1,mid+1,r,p,v);
	mini[id]=min(mini[id<<1],mini[id<<1|1]);
}

int main(){
	n=readint(); d=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	for(int i=1;i<=n;i++) dp[i]=1e9;
	dp[1]=1-a[1];
	build(1,1,n);
	for(int i=2;i<=n;i++){
		dp[i]=query(1,1,n,max(1,i-d),i-1)+1-a[i];
		modify(1,1,n,i,dp[i]);
	}
	printf("%d\n",dp[n]);
	return 0;
}

• Subtask 1: 80 / 80