akhauriyash/Code-Regression huggingface dataset:
#unionfind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n


    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]


    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)


        if x == y:
            return


        if self.parents[x] > self.parents[y]:
            x, y = y, x


        self.parents[x] += self.parents[y]
        self.parents[y] = x


    def size(self, x):
        return -self.parents[self.find(x)]


    def same(self, x, y):
        return self.find(x) == self.find(y)


    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


    def group_count(self):
        return len(self.roots())


    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
a=list(map(int,input().split()))
if n-1==m:
    print(0)
    exit()
if n<2*(n-m-1):
    print("Impossible")
    exit()
uf=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x,y)
v=[[] for _ in range(n)]
for i in range(n):
    v[uf.find(i)].append((a[i],i))
flag=set()
ans,cnt=0,0
for t in v:
    if t:
        t.sort()
        c,idx=t[0]
        flag.add(idx)
        cnt+=1
        ans+=c
for i in range(n):
    a[i]=(a[i],i)
a.sort()
for i in range(n):
    if cnt==2*(n-m-1):
        break
    c,idx=a[i]
    if idx not in flag:
        ans+=c
        cnt+=1
print(ans)

Measured memory_bytes: 45088
#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
  string S;
  long long K;
  cin >> S;
  cin >> K;
  
  int one_length = 0;
  for(int i = 0; i < S.length(); i++){
    if(S[i] == '1'){
      one_length += 1;
    } else { 
      break;
    }
  }
  
  // x = Sの先頭の１の文字数
  // 先頭に１がある:
  /// K <= one_length  : ans = 1 
  /// K  > one_length  : ans = S[x]
  // 先頭に１がない：
  // -> ans = S[0]
  char ans;
  if(one_length == 0){
    ans = S[0];
  } else {
    if(K<=one_length){
      ans = S[0];
    } else {
      ans = S[one_length];
    }
  }
  cout << ans << endl;  
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <limits>
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
#define pNO cout << "NO" << endl
#define pYES cout << "YES" << endl
#define endl "\n"
#define pi 3.14159265358979
using namespace std;
using ll = long long;

void A(){
    int d,t,s; cin >> d >> t >> s;

    if(d <= t*s){
        pYes;
    }else{
        pNo;
    }
}
int main(){
    A();
    sysp;
}

Measured memory_bytes: 3688
n,a,b = map(int,input().split())
xn = [int(i) for i in input().split()]
dpn = [10**9+7]*n
dpn[0] = 0

for i in range(1,n):
  dpn[i] = min((xn[i]-xn[i-1])*a,b)+dpn[i-1]
print(dpn[n-1])

Measured memory_bytes: 14252
s=list(input())
k=int(input())


count=0
n=len(s)
x=s[0]
y=s[-1]

if s.count(s[0])==n:
    print((n*k)//2)
    exit()

if s[0]!=s[-1]:
    for i in range(1,n):
        if s[i]==s[i-1]:
            count+=1
            s[i]='1'
    print(count*k)


else:
    countA=1
    countB=1
    v=0
    w=0
    for i in range(1,n):
        if s[i]==s[i-1]:
            countA+=1
            
        else:
            v=i
            break
    for i in range(1,n):
        if s[n-1-i]==s[n-1]:
            countB+=1
        else:
            w=n-1-i
            break
    
    for i in range(v,w+1):
        if s[i+1]==s[i]:
            count+=1
            s[i+1]='1'
    print(count*k+countA//2+((countA+countB)//2)*(k-1)+countB//2)

    



        
        
        
    
    
    
    
        
    



        
    
        
        
        
    
    
    
    
        
    




Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s,st;
	cin>>s;
	int n;
	cin>>n;
	int k=s.size();
	int j=1;
	for(int i=0;i<k;i+=n){
		st[j]=s[i];
		j++;
	}
	for(int i=1;i<=j-1;i++){
		cout<<st[i];
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 302;
const long long INF = 1000000009000000009;

int n, k;
int a[N];

long long dp[N][N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    if (n == k)
    {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            dp[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (i - 1 <= k)
            dp[i][i - 1] = min(dp[i][i - 1], (long long)a[i]);
        for (int j = 0; j <= k; ++j)
        {
            for (int ii = i + 1; ii <= n; ++ii)
            {
                if (j + ii - i - 1 <= k)
                {
                    if (a[i] > a[ii])
                        dp[ii][j + ii - i - 1] = min(dp[ii][j + ii - i - 1], dp[i][j]);
                    else
                        dp[ii][j + ii - i - 1] = min(dp[ii][j + ii - i - 1], dp[i][j] + a[ii] - a[i]);
                }
            }
        }
    }
    long long ans = INF;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            if (j + (n - i) <= k)
            {
                ans = min(ans, dp[i][j]);
                if (ans == 2)
                    cout << "";
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 数値
		int n11 = sc.nextInt();
		int n12 = sc.nextInt();
		int n13 = sc.nextInt();
		int n21 = sc.nextInt();
		int n22 = sc.nextInt();
		int n23 = sc.nextInt();
		int n31 = sc.nextInt();
		int n32 = sc.nextInt();
		int n33 = sc.nextInt();
		boolean b11 = false;
		boolean b12 = false;
		boolean b13 = false;
		boolean b21 = false;
		boolean b22 = false;
		boolean b23 = false;
		boolean b31 = false;
		boolean b32 = false;
		boolean b33 = false;
		int n = sc.nextInt();
		int[] bn = new int[n];

		for (int i = 0; i < n; i++) {
			bn[i] = sc.nextInt();
			if (bn[i] == n11) {
				b11 = true;
			}
			if (bn[i] == n12) {
				b12 = true;
			}
			if (bn[i] == n13) {
				b13 = true;
			}
			if (bn[i] == n21) {
				b21 = true;
			}
			if (bn[i] == n22) {
				b22 = true;
			}
			if (bn[i] == n23) {
				b23 = true;
			}
			if (bn[i] == n31) {
				b31 = true;
			}
			if (bn[i] == n32) {
				b32 = true;
			}
			if (bn[i] == n33) {
				b33 = true;
			}
		}

		if ((b11 == true && b12 == true && b13 == true) || (b21 == true && b22 == true && b23 == true)
				|| (b31 == true && b32 == true && b33 == true) || (b11 == true && b21 == true && b31 == true)
				|| (b12 == true && b22 == true && b32 == true) || (b13 == true && b23 == true && b33 == true)
				|| (b11 == true && b22 == true && b33 == true) || (b13 == true && b22 == true && b31 == true)) {
			System.out.println("Yes");
		} else {

			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define ALL(c) begin(c), end(c)
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6+6;


int main(){
    //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.precision(12);cout<<fixed;
    
    ld R;
    cin>>R;
    cout<<R*acos(-1)*2<<endl;
    
    
    
    return 0;
}


Measured memory_bytes: 3796
using System;
using System.Collections.Generic;
using System.Linq;
using static Atcoder;
using System.Threading.Tasks;
using System.ComponentModel;

public class Hello
{

    public static void Main()
    {
        int[] n = SpIntRead(' ');
        Console.WriteLine(n[0] - n[1] + 1);
    }
}


public class Atcoder
{
    static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    public static long LCM(long a, long b)
    {
        long c = a * b;
        if (a < b) Swap(ref a, ref b);
        long d = a % b;
        while (d != 0)
        {
            a = b;
            b = d;
            d = a % b;
        }
        return c / b;
    }
    public static string strReverce(string s)
    {
        return new string(s.Reverse().ToArray());
    }
    public static int intRead()
    {
        return int.Parse(Console.ReadLine());
    }
    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        //double sqrtNum = Math.Sqrt(n);
        for (int i = 3; i < n; i += 2)
        {
            if (n % i == 0) return false;
        }
        return true;
    }
    public static string[] SpRead(char c)
    {
        return Console.ReadLine().Split(c);
    }
    public static int[] SpIntRead(char c)
    {
        return Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
    }
    public static string ToConvertBit(int N, int e)
    {
        string ret = "";
        int r = 0;
        while (N != 0)
        {
            r = N % e;
            ret += r.ToString();
            N -= r;
            N /= e;
        }
        ret = strReverce(ret);
        return ret;
    }

}


Measured memory_bytes: 11348
#include <stdio.h>
#include <stdlib.h>
#define N 100

int main(){

  int A[N],flag=1,kazu,i,j,kari,kou;

  scanf("%d",&kazu);
  if(kazu>100)exit(1);
  for(i=0;i<kazu;i++){
    scanf("%d",&A[i]);
  }

  while (flag){
    flag = 0;
       for(j=1; j<kazu;j++){
	
	 if (A[j] < A[j-1]){
	   kari=A[j-1];
	   A[j-1]=A[j];
	   A[j]=kari;
	   flag = 1;
	   kou++;
	 }
	 
       }
  }
  for(i=0;i<kazu;i++){
    printf("%d",A[i]);
    if(i<kazu-1)printf(" ");
  }
  printf("\n");
  printf("%d\n",kou);
  
  return 0;
}
  



Measured memory_bytes: 2100
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String A = sc.next();
    long n = A.length();
    HashMap<String, Long> map = new HashMap<String, Long>();
    for(char c = 'a'; c <= 'z'; c++) {
      String s = String.valueOf(c);
      map.put(s, (long)0);
    }
    for(int i = 0; i < n; i++) {
      String s = String.valueOf(A.charAt(i));
      map.put(s, map.get(s) + 1);
    }
    long e = 0;
    for(char c = 'a'; c <= 'z'; c++) {
      String s = String.valueOf(c);
      long m = map.get(s);
      e += ((m * (m - 1)) / 2);
    }
    long ans = 1 + ((n * (n - 1)) / 2) - e;
    System.out.println(ans);
  }
}

Measured memory_bytes: 41872
if __name__ == "__main__":
    target = input()
    start = target[:int((len(target)-1)/2)]
    end = target[int((len(target)+3)/2)-1:]
    test = target[::-1]
    print("Yes" if target == target[::-1] and start == start[::-1] and end == end[::-1] else "No")

Measured memory_bytes: 3060
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;


bool visit[100000];

void dfs(const Graph<int> &g, int v, vector<int> &lv) {
  if (!visit[v]) lv.push_back(v);
  visit[v] = true;
  bool finish = true; // 終点になりうる
  for (auto &e: g[v]) {
    if (visit[e.to]) continue;
    dfs(g, e.to, lv);
    return;
  }
}

int main() {
  int n, m;
  cin >> n >> m;
  Graph<int> g(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    g[a].emplace_back(a, b);
    g[b].emplace_back(b, a);
  }
  vector<int> left, right;
  dfs(g, 0, left);
  dfs(g, 0, right);
  reverse(left.begin(), left.end());
  cout << left.size() + right.size() << endl;
  for (int v : left) { 
    cout << v+1 << endl;
  }
  for (int v : right) {
    cout << v+1 << endl;
  }
}

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

int main() {
	int N, M, a; cin >> N >> M; M *= 2;
	vector<int> edge(N);
	for( int i = 0; i < M; i++ ){
		cin >> a;
		edge[a-1]++;
	}
	for( int k : edge ) cout << k << endl;
}

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

using namespace std;

int main(){
	int n;
	cin>>n;
	vector<int> a(n);
	
	for(int &x: a)
		cin >> x;
		
		
	sort(a.rbegin(), a.rend());
	
	int sol = 0;
	
	for(int i = 0; i < n; i++){
		if(i%2 == 0){
			sol += a[i];
		}
		else
			sol -= a[i];
	}
	
	cout << sol;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>

using namespace std;

int N,x[301],y[301];

double get_r(double X, double Y){
    double ret = 0;

    for(int i = 0;i < N;++i)
        ret = max(ret,(X - x[i]) * (X - x[i]) + (Y - y[i]) * (Y - y[i]));

    return ret;
}

double searchY(double X){
    double lo = 0,hi = 1000;

    for(int it = 0;it < 100;++it){
        double a = (2 * lo + hi) / 3;
        double b = (lo + 2 * hi) / 3;

        double ra = get_r(X,a);
        double rb = get_r(X,b);

        if(ra < rb) hi = b;
        else lo = a;
    }

    return get_r(X,lo);
}

double searchX(){
    double lo = 0,hi = 1000;

    for(int it = 0;it < 100;++it){
        double a = (2 * lo + hi) / 3;
        double b = (lo + 2 * hi) / 3;

        double ra = searchY(a);
        double rb = searchY(b);

        if(ra < rb) hi = b;
        else lo = a;
    }

    return searchY(lo);
}

int main(){
    scanf("%d",&N);

    for(int i = 0;i < N;++i)
        scanf("%d %d",&x[i],&y[i]);

    printf("%.15f\n",sqrt(searchX()));

    return 0;
}





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

int main()
{
	ll N, M;
	cin >> N >> M;
	if (N > M) swap(N, M);
	if (N == 1) {
		if (M == 1) {
			cout << 1 << endl;
		}
		else {
			cout << M - 2 << endl;
		}
	}
	else if (N == 2) {
		cout << 0 << endl;
	}
	else {
		cout << (N - 2) * (M - 2) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
// Etavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#define il inline
#define ll long long
#define rep(i,s,t) for(register int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(register int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define file(s) freopen(s".in" ,"r",stdin),freopen(s".out","w",stdout)
#define pt(x) putchar(x)
using namespace std;
il int ci(){
	register char ch;int f=1;
	while(!isdigit(ch=getchar()))f=ch=='-'?-1:1;
	register int x=ch^'0';
	while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
	return f*x;
}

enum{N=100023};

const int mod = 1e9+7;

il ll qpow(ll a,ll b){
	ll ans= 1;
	for(; b; b>>=1,a=a*a%mod) if ( b&1 ) {
		ans= ans*a%mod;
	} return ans;
}
il ll inv(ll x){ return qpow(x,mod-2); }

ll fac[N],Invf[N];
il void init_fac(int n){
	n= min(n,mod-1);
	fac[0]= 1;
	rep(i,1,n) fac[i]=fac[i-1]*i%mod;
	Invf[n]= inv(fac[n]);
	rev_rep(i,n,1) Invf[i-1]=Invf[i]*i%mod;
}
il ll comp(ll n,ll m){
	if( n<m ) return 0;
	return fac[n]*Invf[m]%mod*Invf[n-m]%mod;
}

ll a[N],b[N],s[N];

int main(){
	int n=ci();
	rep(i,1,n){
		a[i]=ci();
		b[i-1]=a[i]-a[i-1];
	}
	n--;
	init_fac(n);
	rep(i,1,n) s[i]=(s[i-1]+inv(i))%mod;
	ll ans= 0;
	rep(i,1,n){
		ans=(ans+b[i]*s[i])%mod;
	}
	printf("%lld\n",(ans*fac[n]%mod+mod)%mod);
	return 0;
}


Measured memory_bytes: 4096
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
//#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000000000000;
const int mod = 1000000007;
int test[345678], aa[345678][2];
signed main() {
	int n, m, k, a, b, c, d, cnt = 0, ans = 0; string s, t; 
	cin >> m;
	for (int h = 1; h < m; h++) {
		cin >> a; test[a]++;
	}
	for (int h = 1; h <= m; h++) {
		cout << test[h] << endl;
	}
	return 0;
}

Measured memory_bytes: 5168
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=23;
const int Mod=1e9+7;
int n;
bool g[MAX_N][MAX_N];
LL dp[MAX_N][1<<MAX_N];
/*int dfs(int now,int S)
{
	if(now==n)
	{
	//	cout<<S<<endl;
		return 1;
	}
	if(dp[now][S])return dp[now][S];
	for(int i=0;i<n;i++)
	{
		if(g[now][i] && (S&(1<<i)))dp[now][S]+=dfs(now+1,S&(~(1<<i)));
		dp[now][S]%=Mod;
	}
	return dp[now][S];
}*/
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>g[i][j];
		}
	}
//	int ans=dfs(0,(1<<n)-1);
	//cout<<ans<<endl;
	dp[0][(1<<n)-1]=1;
	for(int i=0;i<n;i++)
	{
		for(int S=0;S<(1<<n);S++)
		{
			if(__builtin_popcount(S)!=n-i)continue;
			for(int j=0;j<n;j++)
			{
				if(g[i][j] && (S&(1<<j)))
				{
					dp[i+1][S&(~(1<<j))]+=dp[i][S];
					dp[i+1][S&(~(1<<j))]%=Mod;
				}
			}
		}
	}
	cout<<dp[n][0]<<endl;
	return 0;
}

Measured memory_bytes: 278656
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1000005], b[1000005], c[1000005];
int main()
{
    int n, m, cnt = 0;
    cin >> n >> m;
    for(ll i = 0; i < n; i ++)
    {
        cin >> a[i];
    }
    b[0] = 0;
    for(ll i = 1; i <= n; i ++)
    {
        b[i] = b[i-1] + a[i-1];
        if(b[i] <= m)
        {
            cnt ++;
        }
    }
    cout << cnt + 1;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}

};

vector<vl> vv;
vl c;
int w;


ll prob(int f,int e) {
	ll res=1;
	ll l = 1, r = 1;
	l = c[max(0, f)-0];
	r = c[w - 1 - min(e, w - 1)];
	res = l*r;
	return res;
}

ll ans(int h, int k) {
	if (h == 0) {
		if (k == 0)return 1;
		else return 0;
	}
	if (vv[h][k] != -1) {
		return vv[h][k];
	}
	else {
		int hasi = 0;
		if (k == 0 || k == w - 1)hasi++;
		ll res= ans(h - 1, k)*prob(k-1,k+1);
		res %= MOD;
		hasi=(k == 1 || k == w - 1)?1:0;
		if (k != 0) {
			res += ans(h - 1,k - 1) * prob(k - 2, k + 1);
			res %= MOD;
		}
		hasi = (k == 0 || k == w - 2) ? 1 : 0;
		if (k != w - 1) {
			res += ans(h - 1, k + 1) * prob(k - 1, k + 2);
			res %= MOD;
		}
		vv[h][k] = res;
		return res;
	}
}

int main() {
	int h, k;
	cin >> h >> w >> k;
	rep(i, h + 1) {
		vl v;
		rep(j, w) {
			v.push_back(-1);
		}
		vv.push_back(v);
	}
	rep(i,w) {
		c.push_back(1);
	}
	c[1] = 2;
	range(i, 2, w) {
		c[i] = c[i - 1] + c[i - 2];
	}
	cout << ans(h, k - 1) << endl;

}

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

int main() {
    long long mod = 1e9 + 7;
    int n; cin >> n;
    vector<vector<int>> bitCnt(2, vector<int> (60, 0));
    vector<long long> data(n);
    for(int i = 0; i < n; i++) cin >> data[i];

    long long ans = 0;
    for(auto num : data) {
        for(int i = 0; i < 60; i++) {
            ans += (bitCnt[!(num & (1LL << i))][i] * ((1LL << i) % mod)) % mod;
            ans %= mod;
            bitCnt[(bool)(num & 1LL << i)][i]++;
        }
    }

    cout << ans;
}

Measured memory_bytes: 2688
#include <iostream>

using namespace std;

int main() {
    int a, b, c, i, ans = 0;
    
    cin>> a >> b >> c;
    
    for(i = a ; i <= b ; i++){
        if(c % i == 0){
            ans = ans + 1;
        }
    }
    cout<< ans << endl;
    
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        string S;cin>>S;
        if(S[0]=='#') break;
        int cnt=1;
        for(int i=0;i<S.size();i++){
            if(S[i]=='/') cnt++;
        }
        
        vector<vector<int>> state(cnt,vector<int>());
        int h=0;
        
        for(int i=0;i<S.size();i++){
            if(S[i]=='/') h++;
            else if(S[i]=='b') state[h].push_back(1);
            else{
                for(int j=0;j<S[i]-'0';j++){
                    state[h].push_back(0);
                }
            }
        }
        
        int a,b,c,d;cin>>a>>b>>c>>d;
        a--;b--;c--;d--;
        state[a][b]--;
        state[c][d]++;
        
        string T;
        
        for(int i=0;i<cnt;i++){
            int ze=0;
            for(int j=0;j<state[i].size();j++){
                if(state[i][j]==1){
                    if(ze) T+=char('0'+ze);
                    T+='b';
                    ze=0;
                }else ze++;
            }
            if(ze) T+=char('0'+ze);
            if(i!=cnt-1) T+='/';
        }
        
        cout<<T<<endl;
    }
}




Measured memory_bytes: 3196
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <typeinfo>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)
#define ALL(v) v.begin(), v.end()
#define FS first
#define SC second
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define SQR(x) ((x) * (x))
#define BIT(n) (1LL<<(n))
#define PCNT(x) __builtin_popcountll(x)
#define GCD(x,y) __gcd(x,y)
#define LCM(x,y) x/__gcd(x,y)*y
#define PB push_back
#define MP make_pair
#define endl "\n"
using namespace std;
typedef long long lint;
typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<bool> VB;
typedef vector<vector<int> > VVI;
typedef vector<vector<LL> > VVLL;
typedef vector<vector<bool> > VVB;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
const LL INF=2000000000ll;
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; }
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

map<LL,LL> lun;

long long mystoll(string s){
    LL ans = 0;
    for (int i = s.length()-1; i >= 0; i--){
        ans += (s[i]-'0') * pow(10,s.length()-1-i);
    }
    return ans;
}

void setdfs(string s){
    if (s.length() < 11) {
      	string temp;
        if (s[0] - '0' > 1 && s[0] - '0' < 9){
            temp = (char)(s[0]-1) + s;
            lun[mystoll(temp)]++;
            setdfs(temp);
          
          	temp = s[0] + s;
            lun[mystoll(temp)]++;
            setdfs(temp);
          
          	temp = (char)(s[0]+1) + s;
            lun[mystoll(temp)]++;
            setdfs(temp);
        }
        else if (s[0] == '1'){
          	temp = '1' + s;
            lun[mystoll(temp)]++;
            setdfs(temp);
          	temp = '2' + s;
            lun[mystoll(temp)]++;
            setdfs(temp);
            setdfs('0' + s);
        }
        else if (s[0] == '0'){
          	temp = '1' + s;
            lun[mystoll(temp)]++;
            setdfs('1' + s);
            setdfs('0' + s);
        }
        else if (s[0] == '9'){
          	temp = '9' + s;
            lun[mystoll(temp)]++;
            setdfs('9' + s);
          
          	temp = '8' + s;
            lun[mystoll(temp)]++;
            setdfs('8' + s);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);
    int K;
    cin >> K;
  	FOR(i,1,10) lun[i]++;
  
    setdfs("0");
    setdfs("1");
    setdfs("2");
    setdfs("3");
    setdfs("4");
    setdfs("5");
    setdfs("6");
    setdfs("7");
    setdfs("8");
    setdfs("9");
  

    VLL ans;

    for (auto itr : lun){
        ans.push_back(itr.first);
    }
    SORT(ans);
    cout << ans[K-1] << endl;

}


Measured memory_bytes: 46956
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        int x = n/(i+1);
        ll p=x;
        p *= x+1;
        p *= i+1;
        p /= 2;
        ans += p;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3528
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define rep(i,n) for(int i=0;i<n;i++)
#define each(i,n) for(auto &i:n)

int n, m, a, b;
vi e[10000];

vi tsort(int v, vi *e) {
	stack<int> st;
	int ny[v] = {0};
	rep(i,v) rep(j,e[i].size()) ny[e[i][j]]++;
	rep(i,v) {
		if (ny[i]) continue;
		st.push(i);
	}
	vi res;
	while (!st.empty()) {
		int ne = st.top(); st.pop();
		res.push_back(ne);
		rep(i,e[ne].size()) if (--ny[e[ne][i]]==0) st.push(e[ne][i]);
	}
	return res;
}

int main() {
	cin >> n >> m;
	rep(i,m) {
		cin >> a >> b;
		e[a].push_back(b);
	}
	vi r = tsort(n,e);
	rep(i,n) cout << r[i] << endl;
}


Measured memory_bytes: 3756
import java.util.*;

@SuppressWarnings("unchecked")
public class Main {
	// public static void printArray(int[] a) {
	// 	for (int i = 0; i < a.length; i++) {
	// 		System.out.print(a[i] + ", ");
	// 	}
	// 	System.out.println();
	// }

	// public static<T> void printArrayT(T[] a) {
	// 	for (int i = 0; i < a.length; i++) {
	// 		System.out.print(a[i] + ", ");
	// 	}
	// 	System.out.println();
	// }

	public static String joinInt(int[] a, String separator) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				sb.append(separator);
			}
			sb.append(a[i]);
		}
		return sb.toString();		
	}

	static int[] nextIntArray(Scanner sc, int N) {
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		return arr;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] B = new int[N-1];
		for (int i = 0; i < N - 1; i++) {
			B[i] = sc.nextInt();
		}
		long sum = 0;
		sum += B[0];
		for (int i = 1; i < N - 1; i++) {
			sum += (long)Math.min(B[i-1], B[i]);
		}
		sum += B[N-2];
		System.out.println(sum);
	}
}


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

using namespace std;

#ifndef ONLINE_JUDGE
  #define pr_debug(...) do { printf("DEBUG: line %d: %s: ", __LINE__, __PRETTY_FUNCTION__); printf(__VA_ARGS__); } while(0)
  #define pr_vars(...) do { pr_debug(" "); pr_var(split(#__VA_ARGS__, ',').begin(), __VA_ARGS__); } while(0)
#else
  __attribute__ ((constructor)) static void fast_cin() { ios_base::sync_with_stdio(false); cin.tie(0); }
  #define pr_debug(...) do { } while(0)
  #define pr_vars(...) do { } while(0)
#endif /* ONLINE_JUDGE */

using ll = int64_t;
using ull = uint64_t;
#define X first
#define Y second
#define pb push_back

template<typename T> ostream &operator<< (ostream &fout, const vector<T> &vec)
{ for (const auto &el : vec) fout << el << ' '; return fout; }

template<typename T> istream &operator>> (istream &fin, vector<T> &vec)
{ for (size_t i = 0; i < vec.size(); i++) fin >> vec[i]; return fin; }

vector<string> split(const string &s, char c) { vector<string> v; ull st = 0, fn = 0, lvl = 0;
for ( ; fn < s.size(); fn++ ) { if (s[fn] == c && lvl == 0) { v.push_back(s.substr(st, fn - st)); st = fn + 1; }
if (s[fn] == '(') { lvl++; } if (s[fn] == ')') { lvl--; } } v.push_back(s.substr(st, fn - st)); return v; }

void pr_var(vector<string>::iterator it) { (void) it; cout << endl; }
template<typename T, typename... Args> void pr_var(vector<string>::iterator it, T a, Args... args)
{ cout << *it << "=" << a << "  "; pr_var(++it, args...); }

ll div_ceil(ll n, ll d) { ll res = n / d; if (res >= 0) res += n % d ? 1 : 0; return res; }
ll gcd(ll a, ll b) { a = llabs(a); b = llabs(b); while (a && b) a > b ? a %= b : b %= a; return a + b; }
ll lcm(ll a, ll b) { ll c = gcd(a, b); return c == 0 ? 0 : llabs(a / c * b); }

#define setp(a) fixed << setprecision(a)
const double PI = acos(-1.0);
constexpr double EPS = 1e-9;
constexpr double INF = 2e18;

using mp = pair<ll, ll>;
using mt = tuple<ll, ll, ll>;    // unpack: tie(ll, ll, ll) = mt;

constexpr ll MAX = 1e5 + 5;

int main()
{
    string s; cin >> s;
    for (auto c: s)
        if (c == '9') { cout << "Yes" << endl; exit(0); }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;
typedef pair<ll,ll> P;


int main(){
    string s,t;cin>>s>>t;
    ll a,b;cin>>a>>b;
    string u;cin>>u;
    if(s==u)a--;
    else b--;
    cout<<a<<" "<<b<<endl;
}

    









Measured memory_bytes: 3588
#include <bits/stdc++.h>
using ll = long long;
int h, w;

int main() {
    std::cin >> h >> w;
    if (h == 1 || w == 1) {
        std::cout << 1 << std::endl;
        return 0;
    }
    ll even_num = h / 2;
    ll odd_num = h - even_num;
    ll even_w = w / 2;
    ll odd_w = w - even_w;
    long long ans = (odd_num * odd_w) + (even_num * even_w);
    std::cout << ans << std::endl;
    
}

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

from collections import Counter
count = Counter(a)

def choose2(x):
    return int(x*(x-1)/2)
    
total = 0
for i in list(count.values()):
    total += choose2(i)

for i in a:
    s = count[i]
    print(total - choose2(s) + choose2(s-1))

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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = --end(s); i != begin(s); --i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.size(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }

int k, x;
void solve() {
    cin >> k >> x;
    if (500 * k >= x) cout << "Yes" << endn;
    else cout << "No" << endn;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;

int main() {
  long A, B, C, K;
  long ans = 0;
  cin >> A >> B >> C >> K;
  // AがKと同じか大きい場合
  if (A >= K){
    ans = K;
  }
  if (A < K) {
    long margin = K - A;
    // K - AがBよりも小さい
    if (margin <= B) {
      ans = A;
    } else {
      long m_margin = K - A - B;
      ans = A - m_margin;
    }
}
  cout << ans << endl;
}

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

ans=0

for t_idx in range(len(A)-1):
    if A[t_idx] + T <= A[t_idx+1]:
        ans += T
    else:
        ans += A[t_idx+1]-A[t_idx]
ans+=T

print(ans)

Measured memory_bytes: 103772
#include <stdio.h>
#include <math.h>

int main(){
	int a, b;
	while(scanf("%d %d", &a, &b) != 0){
		if(a == 0 && b == 0) break;
		if(a >= b) printf("%d %d\n", b, a);
		else printf("%d %d\n", a, b);
	}
	return 0;
}

Measured memory_bytes: 600
#include <stdio.h>

int main()
{
	int age;
	scanf("%d", &age);

	if (age == 1) {
		printf("Hello World\n");
	}
	else if(age == 2) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", a + b);
	}

	return 0;
}

Measured memory_bytes: 128
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

template<typename T> bool chmin(T& a, const T& b) {
    if (a > b) return a = b, true; else return false;
}

template<typename T> bool chmax(T& a, const T& b) {
    if (a < b) return a = b, true; else return false;
}

// End of template.

int main() {
    cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, a[200200];
    cin >> n;
    rep(i, n) cin >> a[i];

    int64 ans = 0;
    sort(a, a + n, greater());
    ans += a[0];
    for (int i = 2; i < n; ++i) {
        ans += a[i / 2];
    }
    print(ans);

    return 0;
}

/*
     _
  __| |  ___ _ __  _ __
 / _` | / __| '_ \| '_ \
| (_| || (__| |_) | |_) |
 \__,_(_)___| .__/| .__/
            |_|   |_|
*/


Measured memory_bytes: 4432
#include<stdio.h>

int main(){
	
	char a,b;
	scanf("%c %c",&a,&b);
	if(a=='H'){
		printf("%c\n",b);
	}
	else if(a=='D'){
		if(b=='D'){
			printf("%c\n",'H');
		}
		else printf("%c\n",'D');
	}
		
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<30;
ll dp[MAX][3];
bool used[MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N,K;cin>>N>>K;
    vector<ll> point(3);
    cin>>point[0]>>point[1]>>point[2];
    string T;cin>>T;
    map<char,int> MA;
    MA['s']=0;
    MA['p']=1;
    MA['r']=2;
    
    int now=0;
    for(int i=0;i<N;i++){
        
        while(used[now]){
            now++;
            if(now>=N) now=0;
        }
        int vs=MA[T[now]];
        if(now<K){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    if(j==vs) dp[i+1][j]=max(dp[i+1][j],dp[i][k]+point[j]);
                    else dp[i+1][j]=max(dp[i+1][j],dp[i][k]);
                }
            }
        }else{
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    if(j==k) continue;
                    
                    if(j==vs) dp[i+1][j]=max(dp[i+1][j],dp[i][k]+point[j]);
                    else dp[i+1][j]=max(dp[i+1][j],dp[i][k]);
                }
            }
        }
        
        used[now]=1;
        now+=K;
        now%=N;
        
    }
    
    cout<<max({dp[N][0],dp[N][1],dp[N][2]})<<endl;
}




Measured memory_bytes: 4480
#include <iostream>

using namespace std;

int main()
{
  long long  N,D,k=0,v;
  cin>>N>>D;
  k=2*D+1;
  if(N%k==0) {
    v=N/k;
  }
  else{
    v=N/k+1;
  }
  cout<<v;
    return 0;
}


Measured memory_bytes: 256
// 21
#include <bits/stdc++.h>
using namespace std;
#define coutc "\033[48;5;196m\033[38;5;15m"
#define endc "\033[0m"
#define endl '\n'
#define M(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...) M(__VA_ARGS__, rep4, rep3, rep2)(__VA_ARGS__)
#define rep4(_, x, n, s) for (int _ = x; (s < 0) ? _ > n : _ < n; _ += s)
#define rep3(_, x, n) rep4(_, x, n, (x < n ? 1 : -1))
#define rep2(_, n) rep3(_, 0, n)
#define fi first
#define se second
#define pb push_back
#define pairii pair<int, int>
#define all(x) x.begin(), x.end()
#define len(x) int(x.size())
#define lli __int128_t
#define li long long int
#define ld long double
// 4
template <class A, class B>
ostream &operator<<(ostream &o, const pair<A, B> &p) {
  return o << "(" << p.fi << ", " << p.se << ")";
}
// 5
template <class T>
ostream &operator<<(ostream &o, const vector<T> &v) {
  rep(i, len(v)) o << setw(7) << v[i];
  return o << endc << endl << coutc;
}
// 5
template <class A, class B>
ostream &operator<<(ostream &o, const map<A, B> &m) {
  for (auto &kv : m) o << kv;
  return o;
}
// 7
template <class T, class... Ts>
void debug(const T &e, const Ts &... r) {
#ifdef DEBUG
  cerr << coutc << e;
  ((cerr << " " << r), ..., (cerr << endc << endl));
#endif
}

// 3
void _main(int tc) {
  li n, K;
  cin >> n >> K;
  vector<li> v(n);
  rep(i, n) cin >> v[i];
  int mod = 1e9 + 7;
  /************* Recursive *************
  vector<vector<li>> mem(n, vector<li>(K + 1, -1));
  function<int(int, int)> f = [&](int i, int k) -> int {
    if (i == n && k != 0) return 0;
    if (k < 0) return 0;
    if (i == n && k == 0) return 1;
    if (mem[i][k] != -1) return mem[i][k];
    li limit = min(k, v[i]);
    li ans = f(i + 1, k - limit);
    rep(given, limit - 1, -1) { ans = (ans + f(i + 1, k - given)) % mod; }
    return mem[i][k] = ans;
  };
  cout << f(0, K) << endl;
  *********** End Recursive ***********/

  vector<vector<li>> mem(n + 1, vector<li>(K + 1));
  // mem = vector<vector<li>>(n + 1, vector<li>(K + 1));
  rep(i, n + 1) mem[i][K] = 1;

  // rep(i, n - 1, -1) {
  for (int i = n - 1; i >= 0; i--) {
    vector<li> pref = mem[i + 1];

    rep(used, 1, K + 1) { pref[used] = (pref[used] + pref[used - 1]) % mod; }

    // ans = sum(mem[i + 1][Left...Right])

    rep(used, K, -1) {
      li ans = 0;
      li Left = used;
      li Right = used + min(v[i], K - used);
      ans = pref[Right];
      if (Left > 0) ans -= pref[Left - 1];
      // rep(usedHere, Right, Left - 1) {
      //   if (usedHere <= K) ans = (ans + mem[i + 1][usedHere]) % mod;
      // }
      mem[i][used] = ans;
    }
  }
  if (mem[0][0] < 0) mem[0][0] += mod;
  cout << mem[0][0] << endl;
}
// 7
int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0);
  _main(0), exit(0);
  int tc;
  cin >> tc;
  rep(i, tc) _main(i + 1);
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i < n; i++)
#define repv(i,n) for(int i = n-1; i >= 0; i--)
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;

char BUF[3500000];
inline void I(int&a){scanf("%d",&a);}
inline void I(int&a,int&b){scanf("%d%d",&a,&b);}
inline void I(int&a,int&b,int&c){scanf("%d%d%d",&a,&b,&c);}
inline void I(int&a,int&b,int&c,int&d){scanf("%d%d%d%d",&a,&b,&c,&d);}
inline void L(ll&a){scanf("%lld",&a);}
inline void L(ll&a,ll&b){scanf("%lld%lld",&a,&b);}
inline void L(ll&a,ll&b,ll&c){scanf("%lld%lld%lld",&a,&b,&c);}
inline void L(ll&a,ll&b,ll&c,ll&d){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);}
inline void S(string&str){str.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)str.pb(BUF[i]);}
inline void SV(vector<int>&v){v.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)if('a'<=BUF[i]&&BUF[i]<='z')v.pb(BUF[i]-'a');else v.pb(BUF[i]-'A');}

const auto EPS = 1e-10;
const auto INF = 100000000;
const auto MOD = 1000000007;
typedef pair<ll,ll> P;

int n;
string pre[10000], str[10000];
string t;

int main(){
    I(n);
    rep(i,n) S(str[i]);
    rep(i,n) pre[i] = str[i];
    S(t);
    int st = 0, en = 0;
    rep(i,n){
        rep(j,str[i].size()) if(str[i][j] == '?') str[i][j] = 'a';
        if(str[i] <= t) en++;
    }
    rep(i,n){
        rep(j,pre[i].size()) if(pre[i][j] == '?') pre[i][j] = 'z';
        if(pre[i] < t) st++;
    }
    for(int i = st; i <= en; i++){
        cout << i+1;
        if(i == en) cout << endl;
        else cout << " ";
    }
}
































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

int main() {
	int N;
	int a[110]; 
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> a[i];

	sort(a, a + N, greater<int>());
	int Alice = 0;
	int Bob = 0;
	for (int i = 0; i < N; ++i) {
		if (i % 2 == 0) { 
			Alice += a[i];
		}
		else { 
			Bob += a[i];
		}
	}
	cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main()
{
  string input;
  string day[7] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
  cin >> input;

  for (int i=0; i<7; i++) {
    if (input == day[i]) {
      cout << 7-i << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

ll calc(ll a, ll b) {
	return a*a*a*a*a-b*b*b*b*b;
}
int main() {
	ll		a,b,c,i,j,k,n,m,x,y,ans = 0;

	cin >> x;

	a = 64;
	b = 64;

	ans = calc(a , b);
	while(ans != x) {
		if (ans > x) {
			a--;
		} else {
			b--;
		}
		ans = calc(a , b);
	}

	cout << a << ' ' << b << endl;

}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
ll INF = pow(10,9)+7;

int main(){
  string s,t;
  cin >> s >> t;
  int u = s.size() - 1;
  int n=t.size()-1;
  int next = u-1;
  while(u>=0){
    if(s[u]==t[n] || s[u]=='?') n--;
    else{
      n=t.size()-1;
      u=next;
      next=u-1;
      continue;
    } 
    if(n<0){
      break;
    }
    u--;
  }
  
  
  if(u<0){
    cout << "UNRESTORABLE" << endl;
  }
  else{
    string ans="";
    int i=0;
    while(i<s.size()){
      if(i==u){
        ans+=t;
        i+=t.size();
      }
      else if(s[i]=='?'){
        ans+='a';
        i++;
      }
      else{
        ans+=s[i];
        i++;
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 3560
import sys
input=sys.stdin.readline
H,W,K=map(int,input().split())
G=[[0]*W for i in range(H)]

for i in range(K):
    r,c,v=map(int,input().split())
    r,c=r-1,c-1
    G[r][c]=v

dp=[[[-1]*W for i in range(H)] for i in range(4)]

dp[0][0][0]=0
if G[0][0]!=0:
    dp[1][0][0]=G[0][0]

for i in range(H):
    for j in range(W):
        m=max(dp[k][i][j] for k in range(4))
        if i+1<H:
            dp[1][i+1][j]=max(dp[1][i+1][j],m+G[i+1][j])
            dp[0][i+1][j]=max(dp[0][i+1][j],m)
        if j+1<W:
                dp[0][i][j+1]=0
                dp[1][i][j+1]=max(dp[1][i][j+1],dp[1][i][j],dp[0][i][j]+G[i][j+1])
                dp[2][i][j+1]=max(dp[2][i][j+1],dp[2][i][j],dp[1][i][j]+G[i][j+1])
                dp[3][i][j+1]=max(dp[3][i][j+1],dp[3][i][j],dp[2][i][j]+G[i][j+1])
ans=max(dp[i][H-1][W-1] for i in range(4))
print(ans)

Measured memory_bytes: 429908
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**7)
input=sys.stdin.buffer.readline
N,M,S=map(int,input().split())
S=min(S,2500)
INF=10**18
time=[[INF]*2501 for _ in range(N)]
way=[[]for _ in range(N)]
for _ in range(M):
  u,v,a,b=map(int,input().split())
  way[u-1].append((v-1,a,b))
  way[v-1].append((u-1,a,b))
CD=[list(map(int,input().split())) for _ in range(N)]
q=[(0,0,S)]
while q:
  ti,city,cur=heappop(q)
  for nxt,a,b in way[city]:
    if cur>=a:
      if time[nxt][cur-a]>ti+b:
        time[nxt][cur-a]=ti+b
        heappush(q,(ti+b,nxt,cur-a))
  c,d=CD[city]
  nc=min(2500,c+cur)
  nt=ti+d
  if nt<time[city][nc]:
    time[city][nc]=nt
    heappush(q,(nt,city,nc))
for i in range(1,N):
  print(min(time[i]))

Measured memory_bytes: 26304