Cerinta completa

There are bulbs in a straight line, numbered from to .
Each bulb has a button associated with it, and there is a cost, , for pressing this button. When some button is pressed, all the bulbs at a distance from bulb will be toggled(off->on, on->off).

Given , , and the costs for each button, find and print the minimum cost of turning off all bulbs if they’re all on initially.

Input Format

The first line contains two space-separated integers describing the respective values of and .
The second line contains space-separated integers describing the respective costs of each bulb (i.e., ).

Constraints

Output Format

Print a long integer denoting the minimum cost of turning off all bulbs.

Sample Input

3 1
1 1 1

Sample Output

1

Explanation

If we press the middle switch, the middle bulb and the closest adjacent bulbs (i.e., the first and third) will turn off. Because all bulbs will be off in one button press, this cost is minimal. Thus, we print as our answer.

Limbajul de programare folosit: cpp14

Cod:

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;
const ll INF=1e14;


int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,t;
  cin>>n>>t;
  vv<pll> g(n+1);
  vector<int> c(n);
  rep(i,n) cin>>c[i];
  ll re=INF;
  rep(i,min(n,t+1)){
    ll sum=0,rb=0;
    for(int j=i;j<n;j+=2*t+1){
      sum+=c[j];
      rb=j+t;
    }
    if(rb>=n-1) MN(re,sum);
  }
  cout<<re<<endl;
  return 0;
}

Scor obtinut: 1.0

Submission ID: 464650268

Link challenge: https://www.hackerrank.com/challenges/turn-off-the-lights/problem

Turn Off the Lights