akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        inverse = [1] * MAX
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        r = min(r, n-r)
        numerator = self.fact[n]
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def div(self, x, y):
        """ MOD除算 """

        return x * pow(y, self.MOD-2, self.MOD) % self.MOD

N, K = MAP()

acc = list(range(N+2))
acc = list(accumulate(acc))

mt = ModTools(N+1, MOD)
ans = 0
for i in range(K, N+2):
    cnt = (acc[N+1] - acc[N+1-i]) - acc[i] + 1
    ans += cnt
    ans %= MOD
print(ans)


Measured memory_bytes: 35044
#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define __TRUE "Yes"
#define __FALSE "No"
#define cout(x) cout << (x) << endl
#define MAX 100001
using namespace std;

int main() {
  ll N;
  cin >> N;
  vector<ll> c(N),s(N),f(N);
  for(int i=0;i<N-1;i++) {
    cin >> c[i] >> s[i] >> f[i];
  }
  for(ll i=0;i<N;i++){
    ll t = 0;
    for(ll j=i;j<N-1;j++){
      if(t<s[j]) t = s[j];
      else if(t%f[j]==0) ;
      else t = (t+f[j]) - (t%f[j]);
      t += c[j];
    }
    cout << t << endl;
  }
}

Measured memory_bytes: 256
n = int(input())
a = [0]*6
for i in range(n):
    s=input()
    if   s[:1] == "M":j=0
    elif s[:1] == "A":j=1
    elif s[:1] == "R":j=2
    elif s[:1] == "C":j=3
    elif s[:1] == "H":j=4
    else:j=5
    
    a[j]+=1
#print(a)
ans=0
for i in range(5):
    for j in range(5):
        for k in range(5):
            if j == k or i ==k or j==i : f=0
            else:
              f=1
              #z=a[i]* a[j] * a[k] * f
              #if z > 0:print(i,j,k,z)
            ans += a[i]* a[j] * a[k] * f

print(ans//6)

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
	int j,s_length = 0;
	char s[101],p[101];
	scanf("%s",s);
	scanf("%s",p);

	for(int i = 0; s[i] != '\0';i++) s_length++;

	for(int left = 0;s[left] != '\0';left++){
		for(j = 0;p[j] != '\0' && p[j] == s[(left+j)%s_length];j++);
		if(p[j] == '\0'){
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}



Measured memory_bytes: 2696
#include<bits/stdc++.h>
using namespace std;
#include<cstdio>
#define el "\n"
#define sp " "
typedef long long ll;



main()
{
	ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
vector<ll> a(n,0),v(n+1,0),f(n+1,0);
for(ll i=0;i<n;i++)
{
	cin>>a[i];
	f[a[i]]++;
}
ll ans=0;
for(ll i=1;i<=n;i++)
{
	v[i]=(f[i]*(f[i]-1))/2;
	ans+=v[i];
}
ll k;
for(ll i=0;i<n;i++)
{
	k=ans-v[a[i]];
	k+=((f[a[i]]-1)*(f[a[i]]-2))/2;
	cout<<k<<el;
}
}

Measured memory_bytes: 7296
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.ST                 as ST
import qualified Data.Array.Unboxed            as AU
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.Int
import qualified Data.IntMap                   as IM
import           Data.List
import qualified Data.Map                      as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Set                      as S
import           Data.Time
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

main = do
  s<-getLine
  let [_,_,a,b,c,d] = s in if a==b && c==d
    then putStrLn "Yes"
    else putStrLn "No"



Measured memory_bytes: 380
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N_MAX = 2000;
typedef pair<int,int> P;
int main()
{
  int n;
  cin >> n;
  int prime[]={3,5,7,11,13};
  int a;
  int res=0;
  for(int i=0;i<5;i++)
    for(int j=i+1;j<5;j++){
      a=prime[i]*prime[i]*prime[i]*prime[j];
      if(a<=n) res++;
      for(int k=j+1;k<5;k++){
        a=prime[i]*prime[j]*prime[k];
        if(a<=n) res++;
      }
    }
    cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

struct P
{
    int x,y,z;
    bool operator<(const P &a)const{
              return x<a.x;
    }
};


vector<int> v;
//bitset<4001000> b;
int a,c,i,b,k,n,d,e,m;//dy[15]={0,1,0,-1,-1,1,-1,1},dx[15]={1,0,-1,0,1,1,-1,-1};//
int l[5][4111];

int o[5][2333][2335];
int j[2215][2222];
int dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1},dz[10]={0,0,0,0,1,-1};


long long x,y,mod=1000000007;
long long z;

P u[100];
stack<int> s;

//set<int> s;
queue<int> q;

//'1'==49;
//'A'==65;
//'a'==97;
//unordered_
//map<int,int> p;
//list<int> l;

//string r;
char r[3];
//deque<int> de;
bool as(P a,P b)
{
    if(a.y*b.x!=b.y*a.x)
    return a.y*b.x>b.y*a.x;
    return a.y<b.y;
}

int f(int n,int m)
{
    if(n==a+1&&m==a+1) return 0;
    if(n>a+1||m>a+1) return 987654321;
    if(j[n][m]>=0) return j[n][m];
    j[n][m]=f(n+1,m)+o[2][n+1][a]-o[2][n+1][m]+o[0][n+1][a]-o[0][n+1][n];
    j[n][m]=min(j[n][m],f(n,m+1)+o[3][m+1][a]-o[3][m+1][m]+o[1][m+1][a]-o[1][m+1][n]);
    return j[n][m];
}

int main()
{
    memset(j,-1,sizeof(j));
    scanf("%d",&a);
    for(int t=1;t<=a*2;t++)
    {
        scanf("%s %d",r,&n);
        if(r[0]=='B')
        {
            l[0][n]=1;
            for(int h=0;h<2;h++)
            //for(int t=1;t<=a;t++)
            for(int w=1;w<=a;w++)
            if(!l[h][w])
                o[h][w][n]++;
            for(int t=1;t<=a;t++)
                for(int h=0;h<4;h+=2)
                o[h][n][t]+=o[h][n][t-1];
        }
        else
        {
            l[1][n]=1;
            for(int h=2;h<4;h++)
                for(int w=1;w<=a;w++)
            if(!l[h%2][w])
                o[h][w][n]++;
            for(int t=1;t<=a;t++)
                for(int h=1;h<4;h+=2)
                o[h][n][t]+=o[h][n][t-1];
        }
    }
    printf("%d",f(0,0));
}


Measured memory_bytes: 100864
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)



int main(){
    long long a,b,c,d;
    cin>>a>>b>>c>>d;
    long long Max=-1*INF;

    Max=max(b*d,Max);
    Max=max(a*c,Max);
    Max=max(a*d,Max);
    Max=max(b*c,Max);

    cout<<Max<<endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;

int main() {
    string str;
    getline(cin, str);
    for (int i = 0; i < str.size(); ++i) {
        if (str[i] >= 'A' && str[i] <= 'Z') {
            str[i] += 0x20;
        }
        else if (str[i] >= 'a' && str[i] <= 'z') {
            str[i] -= 0x20;
        }
    }
    cout << str << endl;
    
    return 0;
}


Measured memory_bytes: 3136
from collections import deque
 
inf = float('inf')
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0
 
# bfs
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '#':
            continue
        dist = [[inf for j in range(w)] for i in range(h)]
        q = deque()
        
        def update(i, j, x):
            if dist[i][j] != inf:
                return
            dist[i][j] = x
            q.append([i, j])
        
        update(si, sj, 0)
        
        while len(q):
            i = q[0][0]
            j = q[0][1]
            q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                if s[ni][nj] == '#':
                    continue
                update(ni, nj, dist[i][j] + 1)
         
        for i in range(h):
            for j in range(w):
                if dist[i][j] == inf:
                    continue
                ans = max(ans, dist[i][j])
 
print(ans)

Measured memory_bytes: 51548
#include <bits/stdc++.h>
using namespace std;
using str = string;
using ll = long long;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define RREP(i,n) for(int i=int(n)-1; i>=0; i--)
#define FOR(i,f,t) for(int i=int(f); i<=int(t); i++)
#define RFOR(i,f,t) for(int i=int(f); i>=int(t); i--)
#define ALL(vec) (vec).begin(),(vec).end()
#define ASORT(vec) sort(ALL(vec))
#define DSORT(vec) sort(ALL(vec), greater<int>());
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define YES(ans) if(ans) cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define Yes(ans) if(ans) cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define yes(ans) if(ans) cout<<"yes"<<endl; else cout<<"no"<<endl;
#define INF 1000000000000
#define NOD 1000000007
#define PI 3.141592653589793238462643

ll gcd(ll a, ll b) {
  	if (a%b == 0) return(b);
	else return(gcd(b, a%b));
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

int main() {
 	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << b - b/c - b/d + b/lcm(c, d) - (a-1) + (a-1)/c + (a-1)/d - (a-1)/lcm(c, d) <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)

int main(void){
  string n;
  int a=-1,z=-1;
  cin>>n;
  r(i,n.size()){
    if(n.at(i)=='A'&&a==-1){a=i;}
  }
  reverse(n.begin(),n.end());
  r(i,n.size()){
    if(n.at(i)=='Z'&&z==-1)z=n.size()-i;
  }
  cout<<z-a<<endl;




  return 0;
}


Measured memory_bytes: 640
n = int(input())
counter = [0]*(n+1)
for i in range(2, n+1):
    num = i
    j = 2
    while j*j <= num:
        cnt = 0
        while num%j == 0:
            counter[j] += 1
            num //= j
        j += 1
    if num != 1:
        counter[num] += 1
ans = 1
for i in range(n+1):
    if counter[i] > 0:
        ans *= counter[i] + 1
        ans %= int(1e9+7)
print(ans)
        


Measured memory_bytes: 9140
#include<bits/stdc++.h>
#define ll long long
#define MAX 100005
using namespace std;

int dp[MAX][4];
int arr[MAX][4];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            cin>>arr[i][j];
        }
    }

    dp[0][0] = arr[0][0];
    dp[0][1] = arr[0][1];
    dp[0][2] = arr[0][2];
    for(int i=1;i<n;i++){
       for(int j=0;j<3;j++)
          for(int k=0;k<3;k++)
              if(k!=j) dp[i][j] = max(dp[i-1][k] + arr[i][j],dp[i][j]);
    }
    cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]})<<endl;
    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <string>

using namespace std;

using ll = long long;

int main() {
  int n;
  cin >> n;
  vector<tuple<int, int, char, ll, string> > vec;
  for(int i = 0; i < n; ++i) {
    int v, w;
    char t;
    ll d;
    string s;
    cin >> v >> w >> t >> d >> s;
    vec.emplace_back(v, w, t, d, s);
  }
  sort(vec.begin(), vec.end());
  for(auto p : vec) {
    int v, w;
    char t;
    ll d;
    string s;
    tie(v, w, t, d, s) = p;
    cout << v << " " << w << " " << t << " " << d << " " << s << endl;
  }
  return 0;
}



Measured memory_bytes: 12232
#include "bits/stdc++.h"

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 1, -1 , 0 , 0 };
int dy[] = { 0,  0,  1, -1 };
ll MOD = 1000000007;

void solve() {
	int h, w;
	cin >> h >> w;
	string sharp = "";
	rep(i, w+2) sharp = sharp + "#";
	vector<string> v;
	v.pb(sharp);
	rep(i, h) {
		string s;
		cin >> s;
		s = "#" + s + "#";
		v.pb(s);
	}
	v.pb(sharp);
	vP(v);
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int main()
{
  int s,e,x;
  int a=2, b=1;
  scanf("%d %d %d", &s, &e, &x);
  if(s==7)b--;
  else if(s==5)a--;
  if(e==7)b--;
  else if(e==5)a--;
  if(x==7)b--;
  else if(x==5)a--;
  
  if(!(a==0&&b==0))printf("NO");
  else printf("YES");
}

Measured memory_bytes: 128
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
	int n;
	cin >> n;
	string ans;
	switch (n % 10) {
	case 0:
	case 1:
	case 6:
	case 8:
		ans = "pon";
		break;
	case 2:
	case 4:
	case 5:
	case 7:
	case 9:
		ans = "hon";
		break;
	default:
		ans = "bon";
		break;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	int n,a,b,c,nh,ah,z;
	z=0;
	bool bou=true;
	cin>>n;
	vector<int>x(n),y(n),h(n);
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i]>>h[i];
	}
	for(int nx=0;nx<=100;nx++){
		for(int ny=0;ny<=100;ny++){
			for(int st=0;st<n;st++){
				if(h[st]!=0){
					ah=h[st]+abs(nx-x[st])+abs(ny-y[st]);
					break;
				}
			}
			bou=true;
			for(int data=0;data<x.size();data++){
				nh=max(z,ah-abs(nx-x[data])-abs(ny-y[data]));
				if(nh!=h[data]){
					bou=false;
					break;
				}
			}
			if(bou){
				cout<<nx<<" "<<ny<<" "<<ah<<endl;
				return 0;
			}
		}
	}
}


Measured memory_bytes: 256
#define	_USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
using namespace std;
int main(){
	
	double x1,y1,x2,y2,xq,yq;

	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf",&x1,&y1,&x2,&y2,&xq,&yq)!=EOF){
		double m,b,x,y;
		if(x2==x1){
			xq*=-1;
			printf("%.6f %.6f\n",xq,yq);
		}
		else{
			m=(y2-y1)/(x2-x1);
			b=y2-m*x2;
			x=(2*m*yq-(m*m-1)*xq-2*b*m)/(m*m+1);
			y=m*(xq+x)+2*b-yq;
			printf("%.6f %.6f\n",x,y);
		}
		
		
	}

}

	

Measured memory_bytes: 1240
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var w = Console.ReadLine().ToCharArray();
            var result = string.Empty;

            foreach(var item in w)
            {
                if(result.Contains(item))
                {
                    result = result.Replace(item.ToString(), "");
                    continue;
                }
                result += item;
            }
            
            if(result.Any())
            {
                Console.WriteLine("No");
                return;
            }
            Console.WriteLine("Yes");
        }
    }
}


Measured memory_bytes: 11476
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,n;
char s[210000];
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	cin>>n>>a>>b>>c>>d>>s;
	if(a>b){
		swap(a,b);swap(c,d);
	}
	bool che=false;
	for(int i=a;i<max(c,d)-1;i++){
		if(s[i]=='#'&&s[i+1]=='#'){
			cout<<"No"<<endl;return 0;
		};
	}
	if(c<d) {
		cout<<"Yes"<<endl;return 0;
	}
	else{
		for(int i=b-2;i<d-1;i++){
		    if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.'){
			    cout<<"Yes"<<endl;return 0;
		    };
	    }
	cout<<"No"<<endl;return 0;
	}
	return 0;
} 

Measured memory_bytes: 384
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(2 * 10**5 + 1)]
for i, a in enumerate(A * 2):
    L[a] += [i]
before_next = [L[a][bisect.bisect(L[a], i)] for i, a in enumerate(A)]
first_cycle = [None] * N
now = 0
idx = 0
cycle = 0
while True:
    if first_cycle[now] is not None:
        break
    first_cycle[now] = cycle
    now = before_next[now] + 1
    dcycle, now = divmod(now, N)
    cycle += dcycle
cycle2 = cycle
cycle1 = first_cycle[now]
#K cycle目=cycle1+(K-cycle1)%(cycle2-cycle1) cycle目
K2 = cycle1 + (K - cycle1) % (cycle2 - cycle1)
if K2:
    f1 = f2 = 0
    for i in range(N - 1, -1, -1):
        if first_cycle[i] == K2 - 1:
            f1 = 1
            break
    for j in range(N - 1, -1, -1):
        if first_cycle[j] == K2:
            f2 = 1
            break
    if f2:
        B = A[j:]
    elif f1:
        B = A[i:] + A
else:
    B = A
ans = []
cnt = [0] * (2 * 10**5 + 1)
for a in B:
    if cnt[a] > 0:
        while True:
            cnt[ans.pop()] -= 1
            if cnt[a] == 0:
                break
    else:
        ans += [a]
        cnt[a] += 1
print(' '.join(map(str, ans)))


Measured memory_bytes: 78732
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
int main() {
    int a,b;
    cin >> a >> b;
    int cnt = 1;
    int ans = 0;
    while(cnt < b){
        if(cnt != 0){
            cnt += (a-1);
        }else{
            cnt += a;
        }
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

  int n;

  cin>>n;

  set<string>se;

  string str;

  cin>>str;

  se.insert(str);

  char temp=str[str.length()-1];
  
  for(int i=1;i<n;i++){

    cin>>str;

    if(str[0]!=temp){
      cout<<"No"<<endl;
      return 0;
    }

    if(se.count(str)==1){
      cout<<"No"<<endl;
      return 0;
    }

    temp=str[str.length()-1];
    
    se.insert(str);
    
  }

  cout<<"Yes"<<endl;

  return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define f(n) for(int i=0;i<n;i++)
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(k,n) for(int i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(s) scanf("%s",s)
#define pi(x) printf("%d\n",x)
#define pl(x) printf("%lld\n",x)
#define ps(s) printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define OJ \
	freopen("input.txt", "r", stdin); \
	freopen("output.txt", "w", stdout);
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

const int mod = 1'000'000'007;
const int N = 3e5, M = N;
//=======================

void solve() {
	int n,e,k;
	cin>>n>>k;
	vi a,r={0};
	for(int i=0;i<n;i++) cin>>e,a.emplace_back(e);
	for(int i=1;i<n;i++){
		e=INT_MAX;
		for(int j=1;j<=k&&(i-j)>=0;j++) e=min(e,r[i-j]+abs(a[i-j]-a[i]));
		r.emplace_back(e);
	}
	cout<<r[n-1];
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	// OJ;

	// clock_t start,stop;
	// start=clock();
	int t = 1;
	// cin >> t;
	while(t--) {
	  solve();
	}
	// stop=clock();
	// cout<<endl<<stop-start<<"ms";

	return 0;
}

Measured memory_bytes: 4276
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int a; cin >> a;
  long long ans=1;
  
  for(int i=1;i<=a;i++){
  ans=ans*i;
    if(ans>=1000000007){
    ans=ans%1000000007;
    }
  }
    
  cout<<ans<<endl;
}


Measured memory_bytes: 256
s=list(input())
t=list(input())
start=[-1]*26
goal=[-1]*26
for i in range(len(s)):
    a=ord(s[i])-97
    b=ord(t[i])-97
    if start[a]!=-1 or goal[b]!=-1:
        if start[a]!=b or goal[b]!=a:
            print("No")
            exit()
    start[a]=b
    goal[b]=a

print("Yes")


Measured memory_bytes: 6704
#include <bits/stdc++.h>

using namespace std;

typedef long long int lli;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    int alpha[30] = { 0 };

    cin >> s;

    for (auto c : s) alpha[c-'A']++;

    for (auto a : alpha) {
        if (a == 1 || a > 2) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <cmath>

#define mst(a,b)memset(a, b, sizeof(a))
#define repi(a,b)for(int i = a; i < b; i++)
#define repj(a,b)for(int j = a; j < b; j++)
#define pii pair<int,int>

#ifdef LOCAL
#define fre()freopen("in.txt","r",stdin)
#endif
#ifndef LOCAL
#define fre()
#endif

//static int x = []() {
//	std::ios::sync_with_stdio(false);
//	std::cin.tie(NULL);
//	return 0;
//}();

#define FASTIO
#ifdef FASTIO
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
//#define scanf abcabc
//#define printf abcabc
#endif
//#ifndef FASTIO
//#define cin abcabc
//#define cout abcabc
//#endif

typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;

using namespace std;


int main() {
	double w, h, x, y; cin >> w >> h >> x >> y;
	double mw = w / 2.0, mh = h / 2.0, f = 0, ans = w * h / 2.0;
	if (x == mw && y == mh)f = 1;
	cout << ans << " " << f << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define FOR(i,a,b) for(int i=(a);i<=(b);++i) 
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i) 
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
#define CI cin>> 
#define CO cout<<
#define EN <<endl 
#define all(x) (x).begin(),(x).end() 
#define asn ans
using namespace std;
template <typename T> istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; 	return is; }
using ll = long long;

int main() {
	string s; CI s;
	int ans = 0;
	REP(i, 4) {
		if (s[i] == '+')ans++;
		else ans--;
	}
	CO ans EN;
	return 0;
}

Measured memory_bytes: 256
// AtCoder ABC109: B - Shiritori
// 2019.9.12 bal4u

#include <stdio.h>
#include <string.h>

#define gc() getchar_unlocked()

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

int ins(char *s) { // 文字列の入力　スペース以下の文字で入力終了
	char *p = s--;
	do *++s = gc();
	while (*s > ' ');
	*s = 0;
	return s - p;
}

char S[105][15]; int w[105];
int main()
{
	int j, i, c, N;
	
	N = in(); for (i = 0; i < N; i++) w[i] = ins(S[i]);
	c = S[0][w[0]-1];
	for (i = 1; i < N; i++) {
		if (S[i][0] != c) goto No;
		for (j = 0; j < i; j++) if (strcmp(S[i], S[j]) == 0) goto No;
		c = S[i][w[i]-1];
	}
	puts("Yes"); return 0;
No: puts("No"); return 0;
}


Measured memory_bytes: 128
# https://atcoder.jp/contests/abc088/tasks/abc088_c

c_list = []

for i in range(3):
    c = list(map(int, input().split()))
    c_list.append(c)
    
a_list = [[] for i in range(3)]
b_list = [[] for i in range(3)]

a_list[0] = 0
b_list[0] = c_list[0][0]

a_list[1] = c_list[0][1] - b_list[0]
a_list[2] = c_list[0][2] - b_list[0]

b_list[1] = c_list[1][0] - a_list[0]
b_list[2] = c_list[2][0] - a_list[0]

if (
    ((a_list[1] + b_list[1]) == c_list[1][1])
    and ((a_list[2] + b_list[1]) == c_list[1][2])
    and ((a_list[1] + b_list[2]) == c_list[2][1])
    and ((a_list[2] + b_list[2]) == c_list[2][2])
    ):
    print('Yes')

else:
    print('No')    



Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

int n;
int t[200010], p[200010];

bool check(int x) {
    for (int i = 1; i < 2 * n; ++ i) t[i] = (p[i] <= x ? 0 : 1);
    int flag1 = 0, flag2 = 0, f = 0;
    for (int i = 2; i < 2 * n; ++ i) if (t[i] == t[i - 1]) { f = 1; break ; }
    if (!f) {
        if (n % 2 == 0) t[n] ^= 1;
        return t[n];
    }
    // puts("DE");
    flag1 = 1 << 30, flag2 = 1 << 30;
    // for (int i = 1; i < 2 * n; ++ i) printf("%d ", t[i]);puts("");
    int cnt1 = 1 << 30, cnt2 = 1 << 30;
    if (t[n] == t[n - 1] || t[n] == t[n + 1]) return t[n];
    for (int i = n - 1; i > 1; -- i) if (t[i] == t[i - 1]) { flag1 = i; cnt1 = t[i]; break ; }
    for (int i = n + 1; i < 2 * n - 1; ++ i) if (t[i] == t[i + 1]) { flag2 = i; cnt2 = t[i]; break ; }
    // cout << flag1 << ' ' << cnt1 << endl;
    // cout << flag2 << ' ' << cnt2 << endl;
    if (flag1 == (1 << 30)) return cnt2;
    if (flag2 == (1 << 30)) return cnt1;
    return (n-flag1) < (flag2-n) ? cnt1 : cnt2;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < 2 * n; ++ i) scanf("%d", p + i);
    int l = 1, r = 2 * n - 1;
    // cout << check(4) << endl;
    while (l < r) {
        // printf("%d %d\n", l, r);
        int mid = l + r >> 1;
        if (check(mid) == 0) r = mid;
        else l = mid + 1;
    }
    // for (int mid = 1; mid < 2 * n; ++ mid) {
        // if (check(mid) == 0) {
            // printf("%d\n", mid);
            // return 0;
        // }
    // }
    // cout << check(4) << endl;
    // printf("%d\n", check(2));
    cout << l << endl;
    return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main(){
  
  int64_t N;
  int64_t A;
  int64_t B;
  
  scanf("%ld %ld %ld",&N,&A,&B);
  
  if((A + B) % 2LL == 0LL){
    int64_t num = (A + B) / 2LL;
    printf("%ld\n",num - A);
  }
  else{
    
    int64_t num8 = N - B;
    
    int64_t num9 = A - 1;
    
    int64_t num10 = min(num8,num9);
    
    int64_t num11 = (B - A) / 2LL;
      
    int64_t num12 = num10 + num11 + 1LL;
    
    printf("%ld\n",num12);
  }
  
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define in_range(x,l,r) (l<=x && x<r)
using namespace std;
typedef vector<int> vi;

const string dir = "URDL", tank = "^>v<";
const int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1};

int main(){
  int t;
  cin >> t;
  while(t--){
    int h,w;
    cin >> h >> w;
    vector<string> g(h);
    rep(i,h)cin >> g[i];

    int len;
    string command;
    cin >> len >> command;

    int y=0,x=0,d=0;
    rep(i,h)rep(j,w){
      rep(k,4){
	if(g[i][j] == tank[k]){
	  y = i; x = j; d = k;
	  g[i][j] = '.';
	}
      }
    }

    rep(i,command.size()){
      if(command[i] == 'S'){
	int ny = y+dy[d], nx = x+dx[d];
	while(in_range(ny,0,h) && in_range(nx,0,w)){
	  if(g[ny][nx] == '#')break;
	  if(g[ny][nx] == '*'){
	    g[ny][nx] = '.';
	    break;
	  }
	  ny += dy[d]; nx += dx[d];
	}
      }else{
	rep(k,4){
	  if(command[i] == dir[k])d = k;
	}
	int ny = y+dy[d], nx = x+dx[d];
	if(in_range(ny,0,h) && in_range(nx,0,w) && g[ny][nx] == '.'){
	  y = ny; x = nx;
	}
      }
    }

    g[y][x] = tank[d];
    rep(i,h)cout << g[i] << endl;
    if(t!=0)cout << endl;
  }
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>

using namespace std;

deque<int> A;
deque<int>::iterator it;

void insertX(int x)
{
	A.push_front(x);
}

void deleteX(int x)
{
	if(!(A.empty()))
	{
		bool cond = false;
		for(it = A.begin(); it != A.end(); it++)
			if(*it == x)
			{
				cond = true;
				break;
			}
		if(cond)
			A.erase(it);
	}
}

void deleteFirst()
{
	if(!(A.empty()))
		A.pop_front();
}

void deleteLast()
{
	if(!(A.empty()))
		A.pop_back();
}

int main()
{
	int n, m;
	string s;
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++)
	{
		cin >> s;
		
		if(s == "deleteFirst")
			deleteFirst();
		else if(s == "deleteLast")
			deleteLast();
		
		scanf("%d", &m);
		
		if(s == "insert")
			insertX(m);
		else if(s == "delete")
			deleteX(m);
	}
	
	if(!(A.empty()))
	{
		for(it = A.begin(); it != A.end()-1; it++)
			printf("%d ", *it);
		printf("%d\n", *it);
	}
	
	return 0;
}


Measured memory_bytes: 7116
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m;
    cin >> n >> m;
    vi c(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        c[a]++;
        c[b]++;
    }
    rep(i, n) {
        cout << c[i] << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int N;
    int p=0;
    string word;
    cin >> N ;
    for(int i=0;i<N;i++){
        cin >> word;
        if(word=="Y"){
            p=1;
            break;
        }
    }
    if(p==0) cout <<"Three"<<endl;
    else cout <<"Four"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    char a;
    cin >> a;
    if(a >= 'a') cout << 'a' << endl;
    else cout << 'A' << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 3e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];
bool L[MAXN];
bool R[MAXN];
vector<int> RGB[4];

int main()
{
    int n,m,k,a,b,x,y,z,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;

    cin>>n;
    cin>>S;

    for(int i=0;i<3*n;i++)
    {
        if(S[i]=='R')RGB[0].push_back(i);
        if(S[i]=='G')RGB[1].push_back(i);
        if(S[i]=='B')RGB[2].push_back(i);
    }

    for(int i=0;i<n;i++){
        x = RGB[0][i];
        y = RGB[1][i];
        z = RGB[2][i];

        mn = min(x,min(y,z));
        mx = max(x,max(y,z));

        L[mn] = R[mx] = true;
    }

    ll res = 1;

    for(int i=0;i<3*n;i++){
        if(!L[i]&&!R[i]){
            res = (res*(ll)cnt)%PMOD;
            cnt--;
        }
        else if(L[i])cnt++;
    }

    cnt = 0;

    for(int i=3*n-1;i>=0;i--){
        if(!L[i]&&!R[i]){
            res = (res*(ll)cnt)%PMOD;
            cnt--;
        }
        else if(R[i])cnt++;
    }

    for(ll i = 1;i<=n;i++)res = (res*i)%PMOD;

    cout<<res<<"\n";

    return 0;
}


Measured memory_bytes: 2544
n = int(input())
S = input()
ans = S.count('R') * S.count('G') * S.count('B')
for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k>=n:
            continue
        if S[i]==S[j] or S[j]==S[k] or S[i]==S[k]:
            continue
        else:
            ans -=1
print(ans)

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    long long H;
    int N;
    cin >>H >> N;
    long long sum = 0;
    int A;
    for(int i = 0; i < N;i++){
        cin >> A;
        sum += A;
    }
    
    if(H <= sum)cout <<"Yes"<<endl;
    else cout <<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string,int> mp;
    string init_w;
    cin >> init_w;
    mp[init_w]++;
    char end = init_w.back();
    bool ok = true;
    rep(i,n-1) {
        string w;
        cin >> w;
        if (mp[w] || w.front() != end) ok = false;
        mp[w]++;
        end = w.back();
    }
    printf(ok?"Yes\n":"No\n");
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;

void solve(long long X) {
    for (long long a = -200; a <= 200; a++) {
        for (long long b = -200; b <= 200; b++) {
            if (pow(a, 5) - pow(b, 5) == X) {
                cout << a << " " << b << endl;
                return;
            }
        }
    }
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can
// remove this line by using your custom template)
int main() {
    long long X;
    scanf("%lld", &X);
    solve(X);
    return 0;
}


Measured memory_bytes: 4168
from collections import Counter
from operator import mul
from functools import reduce

MOD = 10**9 + 7
def prime_factor(n):
    a = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            a.append(i)
            n = n//i
    if n != 1:
        a.append(n)
    return a

n = int(input())

factor = Counter()

for i in range(2, n+1):
    c = Counter(prime_factor(i))
    factor += c

ans = 1
for e in factor.values():
    ans *= (e+1)
    ans %= MOD

print(ans)

Measured memory_bytes: 3700
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int array[] = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		for (int i = n - 1; i >= 0; i--) {
			if (i == n - 1) {
				System.out.print(array[i]);
			} else {
				System.out.print(" " + array[i]);
			}
		}
		System.out.println();
	}

}

Measured memory_bytes: 26172
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define int long long
#define endl '\n'

const int mod = 1000000007;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> a(2);
    rep(i,2) cin >> a[i];

    int ans = 1;
    int last = 1;
    for(int i = 0; i < n; i++){
        int cnt = 1;
        if(a[0][i] == a[1][i]){
            if(i == 0) {
                cnt = 3;
            } else {
                if(last) {
                    cnt = 2;
                } else {
                    cnt = 1;
                }
            }
            last = 1;
        } else {
            if(i == 0){
                cnt = 6;
            } else {
                if(last){
                    cnt = 2;
                } else {
                    cnt = 3;
                }
            }
            i++;
            last = 0;
        }
        ans *= cnt;
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int A, B;
    cin >> A >> B;
    for (int i = 1; i <= 10000; i++)
    {
        if ((8 * i) / 100 == A && (10 * i) / 100 == B)
        {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int main()
{
	int n,flag=0,a[200005];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;
	}
	map<int,int> :: iterator iter;
	iter=mp.begin();
	for(iter=mp.begin();iter!=mp.end();iter++)
		if(iter->second>1)
			flag=1;
	if(flag==0)
		puts("YES");
	else
		puts("NO");
	
}

Measured memory_bytes: 10368
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define hh putchar(10)
#define gc getchar()
#define ll long long
using namespace std;
#define mtm(a) memset(a,0x3f3f3f3f,sizeof a)
#define mt1(a) memset(a,-1,sizeof a)
#define mt0(a) memset(a,0,sizeof a)
#define fup(i,a,b) for(int i=a,i##e=b;i<=i##e;++i)
#define debug(a) cout<<#a<<'='<<a<<endl

class FIO
{
public:
    template<typename T>FIO& operator >>(T& x){_R(x);return *this;}
    template<typename T>FIO& operator <<(T x){_W(x);return *this;}
private:
    int f,c,a[24],i;
    template<typename T> inline void _R(T& x) {
        for(f=0;(c=getchar())<48;c==45&&(f=1));
        for(x=c^48;(c=getchar())>47;x=(x<<3)+(x<<1)+(c^48));
        if(f)x=-x;
    }
    template<typename T> inline void _W(T x) {
        if(sizeof(x)==1){putchar(x);return;}
        if(x<0)putchar(45),x=-x;
        if(x>99) {
            for(i=0;x;x/=10)a[i++]=x%10;
            while(i--)putchar(a[i]+48);
        } else if (x>9)putchar(x/10+48),putchar(x%10+48);
        else putchar(x+48);
    }
}io;


int f[200004];
int ans[200004];

int main()
{
    int n,m;
    io>>n>>m;
    for(int a,b,i=0;i<m;++i)
    {
        io>>a>>b;
        f[a]++;
        f[b+1]--;
    }
    for(int i=1;i<=1e5;++i)
        f[i]+=f[i-1];
    int sum=0;
    for(int i=1;i<=1e5;++i)
        if(f[i]==m)
        {
            ++sum;
        }
    io<<sum;
    return 0;
}






/*
int a[1005],n;
int ef(int x)
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(a[mid]>x)r=mid-1;
        else if(a[mid]<x)l=mid+1;
        else return 1;
    }
    return 0;
}
int main()
{
    io>>n;
    for(int i=0;i<n;++i)io>>a[i];
    sort(a,a+n);
    int flag=1;
    for(int i=0;i<n;++i)
    {
        for(int j=i+1;j<n;++j) {
            int num=-(a[i]+a[j]);
            if(num<=a[j])break;
            int f=ef(num);
            if(f) flag=0,io<<a[i]<<' '<<a[j]<<' '<<num<<'\n';
        }
    }
    if(flag) puts("No Solution");
    return 0;
}
*/


Measured memory_bytes: 3992
import heapq


def main():
    n, m = map(int, input().split())
    a = list(map(lambda x: int(x)*(-1), input().split()))
    heapq.heapify(a)
    for i in range(m):
        item = heapq.heappop(a)
        heapq.heappush(a, (-1) * (-item // 2))
    print(-sum(a))


if __name__ == '__main__':
    main()


Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
typedef long long ll;
const int MAX = 1e3+1;
const ll mod = 1e9+7;

vector<vector<ll>> dp(MAX,vector<ll>(MAX,-1));
char a[MAX][MAX];
int h, w;

ll dfs(int i, int j){
    if(dp[i][j] != -1) return dp[i][j];
    if(i == h && j == w) return dp[h][w] = 1;
    ll num = 0;
    if(i+1 <= h && a[i+1][j] == '.') (num += dfs(i+1,j)) %= mod;
    if(j+1 <= w && a[i][j+1] == '.') (num += dfs(i,j+1)) %= mod;
    return dp[i][j] = num;
}

int main(){
    cin >> h >> w;
    rep(i,h){
        rep(j,w) cin >> a[i+1][j+1];
    }
    cout << dfs(1,1) << endl;
    return 0;
}

Measured memory_bytes: 9216
/* ****Ragnar7 _Lawliet_**** */
/* First, solve the problem.Then write the code. */
#include<bits/stdc++.h>
#define ll          long long
#define ld 			long double
#define hell        1000000007
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifndef ONLINE_JUDGE
	freopen ("input.txt","r",stdin);
	// freopen ("output.txt","w",stdout);
	#endif
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		ll n,x,t;
		cin>>n>>x>>t;
		ll ans = (n/x)*t;
		if(n%x)
			ans+=t;
		cout<<ans;
		
	}

	
	time
	return 0;
}

Measured memory_bytes: 3604
/*
AizuOnline A1179
Title millenium
*/
#include <stdio.h>
// Select Below
//#include <stdlib.h>
//#include <string.h>
//#include <float.h>
//#include <math.h>
//#include <limits.h>
//Global data section

//
int isLeap(int y)
{
  if((y % 3)==0)
    return(1);
  else
    return(0);
}
int day_of_year(int y)
{
  return(195+isLeap(y)*5);
}
int day_of_month(int y,int m)
{
  return(((!isLeap(y)&&(m % 2)==0)?19:20));
}
int datediff(int y1,int m1,int d1,int y2,int m2,int d2)
{
  int i,s;

  if(y1==y2)
   
      if(m1==m2)
	return(d2-d1);
      else
	{
	  s = day_of_month(y1,m1)-d1;
	  if(m2 > m1+1)
	    for(i=m1+1;i<=m2-1;i++)
	      s += day_of_month(y1,i);
	  return(s+d2);
	}
    
  else
    {
      s = datediff(y2,1,1,y2,m2,d2)+1;
      if(y2 > y1+1)
	for(i=y1+1;i<=y2-1;i++)
	  s += day_of_year(i);
      s += datediff(y1,m1,d1,y1,10,day_of_month(y1,10));
      return(s);
    }
}
main()
{
  int y1,m1,d1,ret,n,i;
  //printf("2001=%d\n",isLeap(2001));
  scanf("%d ",&n);
    
  for(i=0;i<n;i++)
    {
      scanf("%d %d %d ",&y1,&m1,&d1);
      ret=datediff(y1,m1,d1,1000,1,1);
      printf("%d\n",ret);
    }
    
  return(0);
}

Measured memory_bytes: 600
#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int x, int y)
{
    int r;
    if(x<y) swap(x, y);
    while(y>0)
    {
        r = x%y;
        x = y;
        y = r;
    }
    return x;
}
int main()
{
    int x, y;
    cin >> x >> y;
    int d = gcd(x, y);
    cout << d << endl;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1000000007;
#define pb push_back
#define fs first
#define sc second
#define forn(i,k,n) for(int i = k; i < n; ++i)
#define nfor(i,n,k) for(int i = n; i >= k; --i)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define vvpii vector<vector<pait<int,int>>>
#define all(arr) arr.begin(), arr.end()
#define endl '\n'
#define dbgarr(V,n) forn(i,0,n) cout << V[i] << " "; cout << endl;
#define dbgarrrev(V,n) nfor(i,n,0) cout << V[i] << " "; cout << endl;
#define dbgmaze(V) for(auto x: V) {for(auto y : x) cout << y <<  " ";cout << endl;}
 #define dbg2d(V,n,m) forn(i,0,n) {forn(j,0,m) cout << V[i][j] <<  " ";cout << endl;}
#define N 100000
#define inf 1100000001
int dp[101][N] = {};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, c; cin >> n >> c;
	int W[n + 1] , V[n + 1];
	forn(i,1,n + 1) cin >> W[i] >> V[i];
	int sum = 0; forn(i,1,n + 1) sum += V[i];
	forn(i,0,n + 1) forn(j,0,sum + 1) dp[i][j] = inf;
	forn(i,0,n) dp[i][0] = 0;
    forn(i,1,n + 1){
        forn(j,1,sum + 1){
        	if(j >= V[i])
        		dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - V[i]] + W[i]);
        	else dp[i][j] = dp[i - 1][j];
        }
    }
    int ans;
    forn(i,0,sum + 1){
        if(dp[n][i] <= c) ans = i;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 43056
n = int(input())
order = list(map(int, input().split()))
satisfaction = list(map(int, input().split()))
addition = list(map(int, input().split()))

index = order[0]
ans = 0

for i in order:
    ans += satisfaction[i-1]
    if i-1 == index:
        ans += addition[i-2]
    index = i

print(ans)

Measured memory_bytes: 9068
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        sc.nextInt();
        String S = sc.next();

        System.out.println(solve(S));

        sc.close();
    }

    static int solve(String S) {
        int result = 0;
        int x = 0;
        for (char ch : S.toCharArray()) {
            x = x + (ch == 'I' ? 1 : -1);
            result = Math.max(result, x);
        }

        return result;
    }
}

Measured memory_bytes: 21588
#include <iostream>
#include <algorithm>
using namespace std;

struct serial_num{
	int number;
	long serial;
};

bool compare(serial_num number1, serial_num number2){
	return number1.number < number2.number;
}

int main(){
	int N;
	long K;
	cin >> N >> K;
	serial_num nums[N];
	for(int i = 0; i < N; i++){
		cin >> nums[i].number;
		cin >> nums[i].serial;
	}
	sort(nums, nums + N, &compare);
	long count = 0;
	for(int i = 0; i < N; i++){
		count += nums[i].serial;
		if(count >= K){
			cout << nums[i].number << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
  	vector<int> a;
	
  	cin >> n;
  	
  	int tmp;
  	for (int i = 0; i < n + 1; i++) {
      	cin >> tmp;
      	a.push_back(tmp);
    }
  	
  	int b = 0;
  	long long total = 0;
  	for (int i = 0; i < n; i++) {
      	cin >> b;
      	if (a[i] >= b) {
          	total += b;
        } else {
          	total += a[i];
          	total += min(b - a[i], a[i + 1]);
          	a[i + 1] = max(a[i + 1] - (b - a[i]), 0);
        }
    }
  
	cout << setprecision(20) << total << endl;  
  
    return 0;
}

Measured memory_bytes: 892
/* --- author: dxm --- */
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

void qread(int &x){
	int neg=1;x=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
	while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
	x*=neg;
}

const int maxn=100005;
int n,m;
db p[maxn],q[maxn],dp[maxn];
int len[maxn];

int main(){
#ifdef FILE
	freopen("FILE.in","r",stdin);
	freopen("FILE.out","w",stdout);
#endif
	while(scanf("%d",&n)&&n>0){
		m=0;
		REP(i,n){
			scanf("%lf",&p[i]);
			if(m&&p[i]>0.999&&q[m]>0.999)len[m]++;
			else q[++m]=p[i],len[m]=1; 
		}
		dp[m+1]=0;
		for(int i=m;i>=1;i--){
			db cur=0;
			dp[i]=INF;
			for(int j=i;j<=i+100&&j<=m;j++){
				cur*=1/q[j];
				cur+=len[j]*(1/q[j]);
				dp[i]=min(dp[i],cur+dp[j+1]);
			}
			dp[i]++;
		}
		printf("%.10lf\n",dp[1]-1.0);
	}
#ifdef TIME
	printf("Running Time = %d ms\n",int(clock()*1000.0/CLOCKS_PER_SEC));
#endif
	return 0;
}

/*
Input:
-----------------
Output:
*/



Measured memory_bytes: 5920