oj.uz

Submission #958937

# Submission time Handle Problem Language Result Execution time Memory
958937 2024-04-07T07:56:38 Z MilosMilutinovic Telefoni (COCI17_telefoni) C++14
80 / 80
 69 ms 8048 KB 
#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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 67 ms 8048 KB Output is correct
9 Correct 56 ms 8024 KB Output is correct
10 Correct 69 ms 8048 KB Output is correct