akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int H,W;
  cin>>H>>W;
  vector<string>S(H);
  for(int i=0;i<H;i++){
    cin>>S[i];
  }
  vector<vector<int>>c(H,vector<int>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S[i][j]=='.'){
        int k=0;
        while(j+k<W&&S[i][j+k]=='.'){k++;}
        for(int v=0;v<k;v++){c[i][j+v]+=k;}
        j=j+k-1;
      }
    }
  }
  for(int j=0;j<W;j++){
    for(int i=0;i<H;i++){
      if(S[i][j]=='.'){
        int k=0;
        while(i+k<H&&S[i+k][j]=='.'){k++;}
        for(int v=0;v<k;v++){c[i+v][j]+=k;}
        i=i+k-1;
      }
    }
  }
  int ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      ans=max(ans,c[i][j]-1);
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 26488
import java.io.File;
import java.io.FileInputStream;
import java.util.Scanner;
import java.util.Map.Entry;
import java.util.function.DoubleToLongFunction;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {
	
	public static void main(String[] args) throws IOException {
		FastScanner sc = new FastScanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int K = sc.nextInt();
		for(int i = 0; i <= N; i++){
			for(int j = 0; j <= M; j++){
				int sum = i * M;
				sum -= i * j;
				sum += (N - i) * j;
				if(sum == K){
					//System.out.println(i + " " + j + " " + sum);
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
	}
}

class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
		this.in = in;
	}
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
    	if (hasNextByte()) return buffer[ptr++];
    	else return -1;
    }
    private static boolean isPrintableChar(int c){
    	return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
    	while(hasNextByte() && !isPrintableChar(buffer[ptr]))
    		ptr++; return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
}


Measured memory_bytes: 22612
import math
N = int(input())
P = list(map(int, input().split(" ")))
Q = list(map(int, input().split(" ")))

def DicNum(P,n): #nがPの何番目か
    count = 0
    for i in range(len(P)):
        if n < P[i]:
            count += 1
    return count

def DicNumP(P): #Pが何番目か
    count = 0
    for i in range(len(P)):
        count += DicNum(P[i:],P[i])*math.factorial(N-i-1)
    return count

print(abs(DicNumP(P)-DicNumP(Q)))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define For(i,m,n) for(int i=m;i<n;i++)
#define FOR(i,n) for(int i=0;i<n;i++)
#define ll long long
#define ull unsigned long long
#define lli long long int
#define pb push_back
ll mob=1000000007;
using namespace std;
int main()
{ 
int s,w;
cin>>s>>w;
if(s>w)cout<<"safe";
else cout<<"unsafe";




return 0;
}











Measured memory_bytes: 3592
//package codeforces;

import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.TreeSet;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
import java.util.Set;

public class Main {
	static Scanner scn = new Scanner(System.in);
	static int mod = 1000000007;
	//static int count = 0;

	public static void main(String[] args) {
		int h=scn.nextInt();
		int a=scn.nextInt(),sum=0;
		int arr[]=new int[a];
		for(int i=0;i<a;i++)
		{
			arr[i]=scn.nextInt();
			sum+=arr[i];
		}
		if(sum>=h)
		{
			System.out.println("Yes");
		}
		else
			System.out.println("No");
	}
}


Measured memory_bytes: 50644
#include<bits/stdc++.h>
#define db(x) cerr<<#x<<" = "<<x<<endl;
using namespace std;
vector<int> e[200005];
long long ans[200005];
void dfs(int x,int fa){
	for(int i=0;i<e[x].size();++i){
		if(e[x][i]!=fa){
			ans[e[x][i]]+=ans[x];
			dfs(e[x][i],x);
		}
	}
	return;
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=q;++i){
		int x,y;;
		scanf("%d%d",&x,&y);
		ans[x]+=y;
	}
	dfs(1,0);
	for(int i=1;i<=n;++i){
		printf("%lld ",ans[i]);
	}
	return 0;
}



Measured memory_bytes: 27392
use std::io;

fn main() {
    let mut line1 = String::new();
    let mut line2 = String::new();
    io::stdin().read_line(&mut line1).unwrap();
    io::stdin().read_line(&mut line2).unwrap();

    let a: i32 = line1.trim().parse().unwrap();
    let s: &str = line2.trim();
    let ans = if a >= 3200 { s } else { "red" };
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define __builtin_popcount __builtin_popcountll

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
    os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m, a ,b;

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    string s;
    cin >> n >> s;
    s.push_back('0');
    vi v;
    int c = 0;
    REP(i, s.size()) {
        if (s[i] == '1') {
            c ++;
        } else {
            if (c) v.push_back(c);
            c = 0;
            v.push_back(0);
        }
    }
    int n = v.size();
    vector<vi> dp(4, vi(n, 0));
    REPS(i, n - 2) {
        chmax(dp[3][i+1], max({dp[0][i], dp[1][i], dp[2][i], dp[3][i]}));
        REPS(j, 3) {
            int l = (j == 1) ? min(v[i-1], 1) : (j == 2 ? max(0, v[i-1] - 1) : v[i-1]);
            if (l && !v[i] && v[i + 1]) {
                chmax(dp[0][i + 1], dp[j][i - 1] + v[i + 1]);
                chmax(dp[1][i + 1], dp[j][i - 1] + v[i + 1] - 1);
                chmax(dp[2][i + 1], dp[j][i - 1] + l);
            }
        }
    }
    cout << max({dp[0][n - 1], dp[1][n - 1], dp[2][n - 1], dp[3][n - 1]}) << endl;
    return 0;
}


Measured memory_bytes: 12948
# -*- coding: utf-8 -*-

import sys
import os

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break

    costs = []
    for a in range(0, 26):
        for b in range(0, 17):
            for c in range(0, 11):
                # candidate
                if a * 200 + b * 300 + c * 500 == n:
                    cost = 0
                    a_bulk_num = a // 5
                    a_price_down_num = a_bulk_num * 5
                    a_normal_price_num = a - a_price_down_num
                    cost += 380 * 0.8 * a_price_down_num + 380 * a_normal_price_num

                    b_bulk_num = b // 4
                    b_price_down_num = b_bulk_num * 4
                    b_normal_price_num = b - b_price_down_num
                    cost += 550 * 0.85 * b_price_down_num + 550 * b_normal_price_num

                    c_bulk_num = c // 3
                    c_price_down_num = c_bulk_num * 3
                    c_normal_price_num = c - c_price_down_num
                    cost += 850 * 0.88 * c_price_down_num + 850 * c_normal_price_num

                    costs.append(cost)

    print(int(min(costs)))

Measured memory_bytes: 7560
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long ll;

int hikaku(const void *n1,const void *n2)
{
    return *(int*)n1-*(int*)n2;
}

int main()
{
    int k,n,ans=0;
    scanf("%d %d",&k,&n);
    int a[n],b[n];

    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    
    qsort(a,n,sizeof(int),hikaku);
    for(int i=0;i<n-1;i++)
    {
        b[i]=a[i+1]-a[i];
    }
    b[n-1]=k-a[n-1]+a[0];

    qsort(b,n,sizeof(int),hikaku);

    ans=k-b[n-1];

    printf("%d\n",ans);
}

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

using namespace std;

int main(){
    
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0; i <n; i ++){
        cin>>v[i];
    }
    
    long long int sum = 0;
    
    for(int i=0; i <n; i ++){
        for(int j=i+1; j <n; j ++){
            sum+=v[i]*v[j];
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}



//head

string s, t;
int ans = INF;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s >> t;
  int n = s.size();
  int m = t.size();
  rep(i, n-m+1) {
    int cnt = 0;
    rep(j, m) {
      if(s[i+j] != t[j]) cnt++;
    }
    chmin(ans, cnt);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3656
#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1<<31)-1

int dat[4*100000+10];
int n,q;

void init(){
    int x=n;
    n=1;
    while(n<x)n*=2;
    rep(i,n*2){
        dat[i]=INF;
    }
}

void update(int m,int x){
    dat[m+n]=x;
    int i=m+n;
    while(i!=1){
        dat[i/2] = min(dat[i],dat[i^1]);
        i=i/2;
    }
}

int find(int s,int t,int i,int a,int b){
//    cout<<a<<" "<<b<<endl;
    if(b<s || t<a)return INF;
    if(s<=a && b<=t)return dat[i];
    return min( find(s,t,i*2,a,(a+b)/2) , find(s,t,i*2+1,(a+b)/2+1,b) );
}

int main(){
    cin>>n>>q;
    init();
    rep(i,q){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==0){
            update(b,c);
        }else{
            cout<<find(b,c,1,0,n-1)<<endl;
        }
    }
}

Measured memory_bytes: 2184
import numpy
s = input()
t = input()
ti = [i for i in range(len(t))]

flg = False
for i in range(len(s)):
    tmp = [t[i] for i in numpy.roll(ti, i)]
    if s == "".join(tmp):
        flg = True
        break
    
if flg:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 21648
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

struct R {
  int l, r;
  bool operator< (R const& rhs) const { return r < rhs.r; }
};
int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N, M; std::cin >> N >> M;
  std::vector<R> rs(M);
  for(auto& rq: rs) {
    int a, b; std::cin >> a >> b;
    rq.l = a-1; rq.r = b-1;
  }
  std::sort(rs.begin(), rs.end());
  int ans = 1, last = rs[0].r;
  for(int i = 1; i < rs.size(); ++i) {
    if(rs[i].l < last) continue;
    ++ans;
    last = rs[i].r;
  }
  fin(ans);
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

const int nmax = 1e9 + 7;
typedef long long ll;

int main(){
  int N, M; cin >> N >> M;

  vector < vector<int> > graph(N + M);

  for (int i = 0; i < N; i++){
    int K; cin >> K;
    for (int j = 0; j < K; j++){
      int L; cin >> L; L += N - 1;
      graph[i].push_back(L);
      graph[L].push_back(i);
    }
  }

  int cnt = 1;
  queue <int> que; que.push(0);
  vector <bool> visited(N + M);
  visited[0] = true;

  while (!que.empty()){
    int start = que.front(); que.pop();

    for (int i = 0; i < graph[start].size(); i++){
      int next = graph[start][i];

      if (visited[next] == false){
        visited[next] = true;
        if (next < N){
          cnt++;
        }
        que.push(next);
      }
    }
  }
  
  if (cnt == N) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}


Measured memory_bytes: 8952
bingo = [list(map(int, input().split())) for _ in range(3)]
n = int(input())
b = [int(input()) for _ in range(n)]

for _b in b:
    for i, row in enumerate(bingo):
        for j, _n in enumerate(row):
            if _b == _n:
                bingo[i][j] = 0

for row in bingo:
    if row == [0, 0, 0]:
        print('Yes')
        break
else:
    for i in range(3):
        if bingo[0][i] == 0 and bingo[1][i] == 0 and bingo[2][i] == 0:
            print('Yes')
            break
    else:
        if bingo[0][0] == 0 and bingo[1][1] == 0 and bingo[2][2] == 0:
            print('Yes')
        elif bingo[0][2] == 0 and bingo[1][1] == 0 and bingo[2][0] == 0:
            print('Yes')
        else:
            print('No')


Measured memory_bytes: 3064
import java.util.*;
class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  long[]a=new long[n+1];
  int b[]=new int[n];
  for(int i=0;i<n;i++){
    b[i]=sc.nextInt();
  	a[b[i]]++;
  }
  long sum=0;
  for(int i=0;i<n+1;i++){
    sum+=a[i]*(a[i]-1)/2;
  }
  for(int i=0;i<n;i++){
  	System.out.println(sum-a[b[i]]*(a[b[i]]-1)/2+(a[b[i]]-2)*(a[b[i]]-1)/2);
  }
}
}


Measured memory_bytes: 96016
import sys

input = sys.stdin.readline

def main():
    ans = ""
    nums = list(map(int, list(input().rstrip("\n"))))
    
    for i in range(2**3):
        ts = sum(nums)
        ops = ['+']*3
        for j in range(3):
            if i>>j&1:
                ts -= nums[j+1]*2
                ops[j]='-'
        if ts == 7:
            for i in range(3):
                ans += str(nums[i])+ops[i]
            ans += str(nums[3])+"=7"
            break
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9200
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(all(x));
#define RSORT(x) sort(rall(x));
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vd = vector<double>;
using vb = vector<bool>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;
const ll inf = 1ll<<29;
const ll mod = 1000000007;
const double eps = 1e-9;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

int main() {
  string S; cin >> S;
  
  string S1 = S.substr(0,2);
  string S2 = S.substr(2);

  bool flag1 = "01"<=S1 && S1<="12";
  bool flag2 = "01"<=S2 && S2<="12";

  if(!flag1 && flag2) cout << "YYMM" << endl;
  if(flag1 && !flag2) cout << "MMYY" << endl;
  if(flag1 && flag2) cout << "AMBIGUOUS" << endl;
  if(!flag1 && !flag2) cout << "NA" << endl;
}

Measured memory_bytes: 256
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

int main() {
    int x, y, z;
    cin >> x >> y >> z;
    int cnt = x / (y + z);
    if (x % (y + z) < z)
        cnt--;
    cout << cnt << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    rep(i, n) cin >> x[i];

    int ans = 0;
    rep(i,n){
        ans += min(x[i], k - x[i]) * 2;
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3600
A, B, H, M = input().split(" ")
A, B, H, M = int(A), int(B), int(H), int(M)

import math

dig = min(abs((H * 60 + M) * 0.5 - M*6), 360 - abs((H * 60 + M) * 0.5 - M*6))
if dig <= 90:
    a2 = A * math.cos((dig/180) * math.pi)
    a3 = A * math.sin((dig/180) * math.pi)
    print(((B-a2)**2 + a3**2)**(1/2))

elif dig > 90:
    dig1 = 180 - dig
    a2 = A * math.sin((dig1/180) * math.pi)
    a3 = A * math.cos((dig1/180) * math.pi)
    print(((B+a3)**2 + a2**2)**(1/2))

Measured memory_bytes: 80076
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
using ll=long long;

int main(){
	int d,g;
	int p[11],c[11];

	cin>>d>>g;
	for(int i=0;i<d;i++)cin>>p[i]>>c[i];

	int ans=1e6;
	for(int x=0;x<(1<<d);x++){ //ビット演算で2^dまで探索;
		int s=0,count=0,rest_max=-1,tmp=0;
		for(int y=0;y<d;y++){	//フラグがたった列をコンプリート;
			if(x>>y&1)s+=100*(y+1)*p[y]+c[y],count+=p[y];
			else rest_max=y;	//フラグがたたない最大の列を保存;
		}
		while(s<g&&tmp<p[rest_max])s+=100*(rest_max+1),tmp++;
		count+=tmp;
		if(s>=g)ans=min(ans,count);
	}
	cout<<ans;
}

		

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

char next(char A, int i, string alpha){
  int j=0;
  int k=0;
  while(k<=26){
    if(A==alpha.at(k)){
      j++;
    }
    if(j>0){
      if(i==0){
        return alpha.at(k);
      }
      i--;
    }
    k++;
    k%=26;
  }
  return 'a';
}

int main(){
  int N;
  string S;
  cin >> N >> S;
  string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  for(int i=0; i<S.size(); i++){
    S.at(i) = next(S.at(i),N,alpha);
  }
  cout << S << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long  
#define ll long long
#define vi vector <int>
#define vii vector <pair<int,int> >
#define vvi vector <vi>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define repD(i,a,b) for (int i=a;i>b;i--)
#define pb push_back
#define pii pair <int,int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define MOD 1000000007
#define M_PI 3.14159265358979323846 

typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
///*X.find_by_order("index")
///X.order_of_key("key")

///----------------------------------------------------------------------------------

void solve()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int ans = a*c;
	ans = max(ans, a*d);
	ans = max(ans, b*c);
	ans = max(ans, b*d);
	cout << ans << "\n";
}
	
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	#ifdef local
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	clock_t TIMER = clock();
	#endif
	
	int t = 1;
	//cin >> t;
	rep(a,0,t)
	{
		//cout<<"Case #"<<a+1<<": ";
		solve();
		#ifdef local
		cout << "\n";
		#endif

	}
	
	#ifdef local
	{TIMER = clock() - TIMER;double time_taken = ((double)TIMER)/CLOCKS_PER_SEC;cerr<<fixed<<setprecision(5)<<"\n\nTime Taken : "<<time_taken<<" seconds\n";}
	#endif
}

Measured memory_bytes: 3664
M = 1000000007
n, k = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(n - 1):
    f, t = map(int, input().split())
    graph[f - 1].append(t - 1)
    graph[t - 1].append(f - 1)

visited = [False] * n

visited[0] = True
cnt = 0
ans = k
que = [0]
while que:
    node = que.pop()
    visited[node] = True
    node_cnt = 0
    for next_node in graph[node]:
        if not visited[next_node]:
            que.append(next_node)
            if cnt < 1:
                ans *= k - 1
                cnt += 1
                node_cnt -= 1
            else:
                ans *= (k - (2 + node_cnt))
                if ans > M:
                    ans %= M
            node_cnt += 1
print(ans % M)


Measured memory_bytes: 69280
N = int(input())
A = list(map(int,input().split(" ")))

cnt = 0
r = 0
tmp = 0
for l in range(N):
	while r < N and (tmp & A[r]) == 0:
		tmp |= A[r]
		r += 1
	cnt += (r - l)
	tmp ^= A[l]
print(cnt)



Measured memory_bytes: 24712
n = input()
a = map(int,raw_input().split())
sum = a[0]
max = a[0]
min = a[0]
for i in range(1,n):
	sum += a[i]
	if min > a[i]:
		tmp = min
		min = a[i]
		a[i] = tmp
	if  a[i] > max:
		tmp = max
		max = a[i]
		a[i] = tmp
print str(min),str(max),str(sum)

Measured memory_bytes: 4996
#include <bits/stdc++.h>
#define newl "\n"
using namespace std;
using lli = long long int;
using vvint = vector <vector <int>>;
const int mod = 1e9 + 7;

const int N = 2e5 + 1;

void solve(){
	string s,t;
	cin >> s >> t;
	int ns = s.length();
	int nt = t.length();
	int minn = 1e8;
	for(int i = 0;i < ns - nt + 1;++i){
		int curr = 0;
		for(int j = 0;j < nt;++j){
			if(t[j] != s[i + j]) ++curr;
		}
		minn = min(minn,curr);
	}
	cout << minn << newl;
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(10);
	#ifdef EXECUTE_LOCALLY
		   freopen("in.txt","r",stdin);
	#endif
	int t = 1;
	//cin >> t;
	while(t--) solve();
	#ifdef EXECUTE_LOCALLY
    	cout << setprecision(3) << "program time: " << (double)clock() / CLOCKS_PER_SEC << newl;
	#endif
	return 0;
}


Measured memory_bytes: 3616
#include<stdio.h>
int main(void){
    int A, B, C, K, max=0, sum=0;
    scanf("%d %d %d", &A, &B, &C);
    scanf("%d", &K);

    sum = A + B + C;
    max = A;
    if(B > max){
        max = B;
    }
    if(C > max){
        max = C;
    }
    sum -= max;

    for(int i=0; i<K; i++){
        max *= 2;
    }

    printf("%d\n", sum + max);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    string w; cin >> w;
    vi hist(30);
    for(auto& e : w) hist[e - 'a']++;

    bool ok = true;
    for(auto& e : hist){
        if(e % 2 == 1) ok = false;
    }
    cout << (ok ? "Yes":"No") << endl;

    return 0;
}


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

#define null                ""
#define all(dat)            dat.begin(), dat.end()
#define over(msg)           puts(msg), exit(0);
#define loop(i, to)         for (int i = 0; i < to; ++i)
#define cont(i, to)         for (int i = 1; i <= to; ++i)
#define forever             for (;;)
#define foreach(i, dat)     for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long           num;

using namespace std;

struct node {
	
	int id, val;
	
	node() {}
	
	node(int id, int val) {
		
		this->id = id;
		
		this->val = val;
		
	}
	
	bool operator < (const node a) const {
		
		return this->val > a.val;
		
	}
	
};

int n, m, ans[100005];

vector<int> g[100005];

int main() {
	
	ios_base::sync_with_stdio(0);
	
	cin >> n;
	
	cont (i, n - 1) {
		
		int u, v;
		
		cin >> u >> v;
		
		g[u].push_back(v);
		
		g[v].push_back(u);
		
	}
	
	priority_queue<node> q;
	
	memset(ans, -1, sizeof(ans));
	
	cin >> m;
	
	cont (i, m) {
		
		int id, val;
		
		cin >> id >> val;
		
		ans[id] = val;
		
		q.push(node(id, val));
		
	}
	
	while (!q.empty()) {
		
		int u = q.top().id;
		
		q.pop();
		
		for (int v : g[u]) {
			
			if (ans[v] == -1) {
				
				ans[v] = ans[u] + 1;
				
				q.push(node(v, ans[v]));
				
			}
			
		}
		
	}
	
	cont (u, n) {
		
		for (int v : g[u]) {
			
			if (abs(ans[u] - ans[v]) != 1) {
				
				over("No");
				
			}
			
		}
		
	}
	
	cout << "Yes\n";
	
	cont (i, n) {
		
		cout << ans[i] << '\n';
		
	}
	
}


Measured memory_bytes: 7924
# A: S[i], S[j], S[k] が異なるものすべて
# j-i != k-j は扱いづらいので,
# B: S[i], S[j], S[k] が異なる」かつ「j - i = k - j である」条件を探索
# ans = A-B
def resolve():
    N = int(input())
    S = input()

    # 条件1
    r, g, b = 0,0,0
    for s in S:
        if s=="R":
            r += 1
        elif s == "G":
            g += 1
        else:
            b += 1
    rgb = r*g*b
    # 条件2
    sub = 0
    for i in range(N):
        for j in range(i+1, N):
            if S[i]==S[j]:
                continue
            k = 2*j-i
            if k >= N or S[k]==S[i] or S[k]==S[j]:
                continue
            sub += 1
    return print(rgb - sub)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 9168
X, Y = list(map(int, input().split()))

def f(x, p):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a
def nCr(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= f(a, p)
    c *= pow(f(b, p), p - 2, p)
    c *= pow(f(a - b, p), p - 2, p)
    return c % p

if (2*X-Y)%3 != 0 or (2*Y-X)%3 != 0 or Y > X*2 or X > Y*2:
  print(0)
else:
  m = (2*X-Y)//3
  n = (2*Y-X)//3
  print(nCr(m+n, n, 10**9+7))


Measured memory_bytes: 3064
#include <iostream>
#include <string>

using namespace std;

int main() {
	string a;
	cin >> a;
	string b = "";
	for (int i = a.size()-1; i >= 0; i--) {
		b += a[i];
	}
	int counter = 0;
	for (int i = 0; i < a.size()/2; i++) {
		if (a[i] == 'i' || a[i] == 'w') {
			if (a[i] == b[i]) {
			} else {
				counter++;
			}
		} else {
			if (a[i] == '(' && b[i] == ')') {
			} else if (a[i] == ')' && b[i] == '(') {
			} else {
				counter++;
			}
		}
	}

	if (a.size() % 2 != 0) {
		if (a[(a.size())/2] == 'i' || a[(a.size())/2] == 'w') {
		} else {
			counter++;
		}
	}
	cout << counter << endl;
	return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x;
    cin >> x;
    if(x == 3 || x == 5 || x == 7) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}



Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<random>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<string> ws(n); cin >> ws;
    if((int)set<string>(ws.begin(), ws.end()).size() != n){
        cout << "No" << '\n';
        return 0;
    }
    for(int i = 1; i < n; i++){
        if(ws[i][0] != ws[i - 1].back()){
            cout << "No" << '\n';
            return 0;
        }
    }
    cout << "Yes" << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	int32_t N, M;
	cin >> N >> M;

	int32_t res = 1;
	for (int32_t i = 0; i < M; i++)
		res *= 2;
	res *= M * 1900 + (N - M) * 100;

	cout << res << endl;

	return 0;
}

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

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int n,k,h[100005],dp[100005];
void solve(){
    cin>>n>>k;
    rep(i,1,n+1) cin>>h[i];
    h[0]=hell;
    rep(i,2,n+1){
       // if(i==1) dp[i]=0;
       // else{
            dp[i]=hell;
            rep(j,max(1LL,i-k),i){
                dp[i]=min(dp[j]+abs(h[j]-h[i]),dp[i]);
            }
        //}
    }
    cout<<dp[n]<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 1792
n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
ans=ans*modcomb(n*m-2,k-2,INF)%INF
print(ans)



Measured memory_bytes: 44144
#include <iostream>
#include <stdio.h>
#include <math.h> 
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <string>

using namespace std;

int main() {

	double a, b;
	cin >> a >> b;

	cout << int(ceil((a+b)/2)) << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		PriorityQueue<Double> pq = new PriorityQueue<>(Comparator.reverseOrder());
		for(int i=0;i<N;i++){pq.add(sc.nextDouble());}
		for(int i=0;i<M;i++){
			pq.add(pq.poll()/2);
		}
		Long ans =0L;
		for(int i=0;i<N;i++){
			ans += Math.round(pq.poll()-0.5);
		}
		System.out.println(ans);
		sc.close();
	}
		
}


Measured memory_bytes: 98144
n = int(input())
a = list(map(int,input().split()))

c = 0
for i in range(0,n):
  if a[i]%2==0:
    if a[i] %6 != 0 and a[i] %10 != 0:
      print('DENIED')
      c = 1
      break

if c == 0:
  print('APPROVED')


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,x,y,z;
    scanf("%d %d %d",&a,&b,&c);
    x=a+b;
    y=b+c;
    z=c+a;;
    if(x<=y && x<=z) printf("%d",x);
    else if(y<=x && y<=z) printf("%d",y);
    else printf("%d",z);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

inline int ab(int x) { return (x < 0 ? -x : x); }

int n, x, y, z, a, b, c, i;

int main()
{
    cin >> n;
    cin >> x >> y;
    a = 0;
    c = b = ab(x - y);
    for(i = 3; i <= n; i ++) {
        cin >> z;
        c = min(a+ab(z-x), b+ab(z-y));

        a = b; b = c;
        x = y; y = z;
    }
    cout << c << '\n';
    return 0;
}


Measured memory_bytes: 256
N =int(input())
A = list(map(int,input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

A = sorted(A)
from collections import Counter
check = Counter(A)
for c,k in check.items():
    if k>=N-1:
        A=[c]



def del_dicts(dicts,i):
    del_list=[]
    for k,v in dicts.items():
        if v<i:
            del_list.append(k)
    for d in del_list:
        del dicts[d]
    return dicts

dicts = {}

for i in range(len(A)):
    if i<=2:
        for num in make_divisors(A[i]):
            if num in dicts:
                dicts[num]+=1
            else:
                dicts[num]=1
    
    else:
        del_list=[]
        
        for k in dicts.keys():
            if A[i]%k == 0:
                dicts[k]+=1
    dicts = del_dicts(dicts,i)
print(max(dicts.keys()))

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

using namespace std;

const int DIM = 1e5 + 7;

vector <int> v[DIM];

int d[DIM][3];
int vis[DIM][3];

int main()
{
    int n, m;
    cin >> n >> m;

    while(m--)
    {
        int x, y;
        cin >> x >> y;

        v[x].push_back(y);
    }

    int s, t;
    cin >> s >> t;

    d[s][0] = 1;
    vis[s][0] = true;

    queue <pair <int, int> > q;
    q.push({s, 0});

    while(!q.empty())
    {
        int nod = q.front().first;
        int dist = q.front().second;

        q.pop();

        vis[nod][dist] = false;

        int nxt = (dist + 1) % 3;

        for(auto i : v[nod])
            if(d[i][nxt] == 0 || d[i][nxt] > d[nod][dist] + 1)
            {
                d[i][nxt] = d[nod][dist] + 1;

                if(vis[i][nxt] == 0)
                {
                    vis[i][nxt] = true;
                    q.push({i, nxt});
                }
            }
    }

    if(d[t][0] == 0)
        cout << -1;
    else
        cout << (d[t][0] - 1) / 3;
}


Measured memory_bytes: 8064
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

void rec(int a, int b, int v) {
    if (a == b) {
        cout << a << " ";
        return;
    }

    int c = (a^b) & -(a^b); // a^bのうちの一番小さい1
    v ^= c; // cを使用済みにする
    int d = v & -v; // vのうち未使用のbit
    rec(a, a^d, v);
    rec(a^d^c, b, v);
}

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

    int N, A, B;
    cin >> N >> A >> B;

    if (__builtin_popcount(A ^ B) % 2 == 1) {
        cout << "YES\n";
        rec(A, B, (1 << N) - 1);
    } else {
        cout << "NO\n";
    }

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
const int maxn=(int)1e6+5;
typedef long long ll;
const ll mod=(ll)1e9+7;
ll sum(ll l,ll r){
    return (l+r)*(r-l+1)/2%mod;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n,k;cin>>n>>k;
    ll ans=0;
    for(ll i=k;i<=n+1;i++){
        ans+=sum(n-i+1,n)-sum(0,i-1)+1;
        ans%=mod;ans+=mod;ans%=mod;
        //debug(sum(n-i+1,n)-sum(0,i-1));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3652
DIV = 1_000_000_007
n = gets.to_i
l = n.times.map{ gets.chomp }
l.delete('-')
s = l.size
u = l.count('U')
dp = (s+1).times.map{ [0]*(s+1) }
dp[0][0] = 1
pos = 0
pre = true
for i in (0...s)
  pos += 1 if pre
  if l[i] == 'U' && !pre
    pre = true
  elsif l[i] == 'D' && pre
    pre = false
  end
  for j in (0..i+1)
    dp[i+1][j] = (j > 0 ? dp[i][j-1]*(pos-j) : 0)
    dp[i+1][j] += dp[i][j]*(pre ? pos-j : pos-j-1) if j < i+1
    dp[i+1][j] %= DIV
  end
end
p dp[s][u]

Measured memory_bytes: 9020
N, K = list(map(int, input().split()))
S = input()

# 終端を追加
S = S + 'E'
ans = -1

# standは利用した命令の数であるのでS[0] == '0'のときstand = 1になる
if (S[0] == '0'):
    stand = 1
else:
    stand = 0

L = 0
R = 0

# 尺取り法　(two pointers というみたい)
while(R < N):
    if (stand <= K):
        # 0からはじまる連続列が見つかったらstandを増やす
        if (S[R] == '1' and S[R+1] == '0'):
            stand+=1
        ans = max(ans, R - L + 1)
        R += 1
    elif L == R:
        L += 1
        R += 1
    else:
        if (S[L] == '0' and S[L+1] == '1'):
            stand -= 1
        L += 1

print(ans)


Measured memory_bytes: 3316
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    int n,ans=0; cin>>n;
    vector<int> m(101,0);
    for(int i=2;i<=n;i++){
        int q=i;
        for(int j=2;j<=n;j++){
            while(q%j==0){
                q/=j;
                m[j]++;
            }
        }
    }
    int c74=0,c24=0,c14=0,c4=0,c2=0;
    rep(i,101){
        if(m[i]>=74) c74++;
        if(m[i]>=24) c24++;
        if(m[i]>=14) c14++;
        if(m[i]>=4) c4++;
        if(m[i]>=2) c2++;
    }
    ans+=c74;
    ans+=c14*(c4-1);
    ans+=c24*(c2-1);
    ans+=c4*(c4-1)/2*(c2-2);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>

using namespace std;

int N;
string S[2];

queue<int> q;

int main() {
  cin >> N;
  cin >> S[0];
  cin >> S[1];


  for (int i = 0; i < N; i++) {
    if (S[0][i] == S[1][i]) {
      q.push(0);
    } else {
      q.push(1);
      i++;
    }
  }

  long long ans = 1;
  int pre = -1;
  if (q.front() == 0) {
    ans *= 3;
  } else {
    ans *= 6;
  }
  pre = q.front();
  q.pop();
  while (!q.empty()) {
    if (pre == 1 && q.front() == 0) {
      ans *= 1;
    } else if (pre == 1 && q.front() == 1) {
      ans *= 3;
    } else {
      ans *= 2;
    }
    pre = q.front();
    q.pop();
  }

  ans = ans % 1000000007;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
	char order[4];
	int option = 0;

	cin >> order;

	for(int i=0;i<3;i++)
	{
		if(order[i] == 'o')option+= 100;
	}

	cout << 700 + option << endl;

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N; ll A, B;
    cin >> N >> A >> B;

    vector<ll> h(N);
    REP(i, N) cin >> h[i];

    ll l = 0, r = inf+1;
    while(r - l > 1) {
        ll m = (l + r) / 2;
        debug(l, m, r)

        ll cnt = 0;
        REP(i, N) {
            ll hr = max(h[i] - m * B, 0LL);
            cnt += ceil(hr / double(A - B));
        }

        debug(cnt)

        if (cnt <= m) {
            r = m;
        } else {
            l = m;
        }

    }
    cout << r << endl;
    
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define pb push_back 
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	set<string> df;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		df.insert(s);
	}
	cout << df.size() << '\n';

}

Measured memory_bytes: 19196
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define dump(a) cout << a << endl; 

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文
int main() {
	string s;
	cin >> s;
	char a = s.at(0);
	int cnt = 1;
	for (int i = 1; i < 4; i++) {
		if (s.at(i) == a) cnt++;
		else {
			cnt = 1;
		}
		if (cnt == 3) {
			dump("Yes")
				return 0;
		}
		a = s.at(i);
	}
	dump("No");
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> d(n);
  for (int i = 0; i < n; ++i) cin >> d[i];
  int sum = 0;
  for (int l = 0; l < n; ++l) {
    for (int r = l + 1; r < n; ++r) {
      sum += d[l] * d[r];
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 256