akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No\n"; return;}

const int MOD = 1e9 + 7;

void solve() {
    int n, k; 
    cin >> n >> k;
    int small = 0, big = 0, ans = 0;
    for (int i = k; i <= n + 1; ++i) {
        if (i == k) {
            loop(j, k) {
                small += j;
                big += n - j;
            }
        }
        else {
            small += i - 1;
            big += n - i + 1;
        }
        ans += (big - small + 1) % MOD;
    }
    cout << ans % MOD;
}

signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   //int t; cin >> t; loop(i, t)
   solve();
   return 0;
}

Measured memory_bytes: 3652
/*                        ______
 _______   /\     |``\   |        |  /
    |     /  \    |__/   |____    |/
    |    / _ _\   |  \   |        |\
    |   /      \  |   \  |______  |  \

            Dept. of CSE
        Comilla  University

*/
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Node struct node
#define spc " "
#define  E  2.71828182845904523536
#define pb push_back
#define pp pop_back
#define valid(nx,ny) nx>=0 && nx<n && ny>=0 && ny<m
#define e endl
#define pii pair<int,int>
#define infinity 1<<30

using namespace std;
map<ll ,ll>check;
#define xam 10000
ll ara[xam];

int main()
{

   ll n;
   cin>>n;
    ll cc=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                cc+=(__gcd(i,__gcd(j,k)));
            }
        }
    }
    cout<<cc<<endl;
return 0;
}


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

int main() {

    int a, b;
    cin >> a >> b;

    int ans = -1;
    for (size_t i = 0; i <= 10000; i++)
    {
        float tax8 = floor(i * 0.08);
        float tax10 = floor(i * 0.10);

        if (tax8 == a && tax10 == b) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;   
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string>
main()
{
    long long n,i,a[200005],j,sum1=0,sum2=0,sum=0,min,b=0,c=0;
   scanf("%lld",&n);
      sum1=0;sum2=0;sum=0;
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            sum=sum+a[i];
        }
        for(i=0;i<n-1;i++)
        {  b=b+a[i];
          c=sum-b;
          if(i==0)
            min=fabs(b-c);
          if(fabs(b-c)<fabs(min))min=fabs(b-c);

        }
        printf("%lld\n",min);



}


Measured memory_bytes: 1792
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,K=map(int, input().split())
    A=list(map(int, input().split()))

    d=1
    keys=list(range(N))
    li={s:-1 for s in keys}
    li[0]=0

    roop=0
    pre_d=0
    for i in range(1,K+1):
        pre_d=d
        d=A[d-1]
        # print("i:"+str(i)+" "+str(pre_d)+"->"+str(d))
        if li[d-1]!=-1:
            roop=i-li[d-1]
            # print("detect_roop:"+str(i)+"~"+str(li[d-1]))
            break
        else:
            li[d-1]=i

    if roop!=0:
        k=1
        for j in range((K-li[d-1]-1)%roop+li[d-1]+1):
            k=A[k-1]
        print(k)
    else:
        print(d)


if __name__ == '__main__':
    main()


Measured memory_bytes: 42752
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;

vector<ll> m(51), n(51);
 
ll sub(int N, ll X) {
    if (N == 0) { return X; }
    ll w = m[N-1];
    if (X <= 1) return 0;
    X -= 1;
    if (X <= w) return sub(N-1, X);
    X -= w;
    if (X <= 1) return n[N-1] + X;
    X -= 1;
    if (X <= w) return n[N-1] + 1 + sub(N-1, X);
    X -= w;
    return n[N];
}
 
ll solve(int N, ll X) {
    return sub(N, X);
}
 
int main() {
    m[0] = n[0] = 1;
    for (int i=1; i<=50; ++i) {
        m[i] = m[i-1]*2 + 3;
        n[i] = n[i-1]*2 + 1;
    }
 
 
    int N; ll X;
    cin >> N >> X;
    cout << solve(N,X) << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	x := readI()
	if x == 0 {
		fmt.Println(1)
	} else {
		fmt.Println(0)
	}
}

/*-----------Input utils-----------*/

var sc = bufio.NewScanner(os.Stdin)

func init() {
	if len(os.Args) >= 2 {
		if os.Args[1] == "debug" {
			debug()
		}
	}
	const buf = 200100
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, buf), buf)
}

func debug() {
	testFile, err := os.Open("./test/sample-1.in")
	if err != nil {
		fmt.Fprintln(os.Stderr, "There is no testfile.")
		os.Exit(1)
	}
	sc = bufio.NewScanner(testFile)
}

func readS() string {
	sc.Scan()
	return sc.Text()
}

func readR() []rune {
	return []rune(readS())
}

func readI() int {
	i, _ := strconv.Atoi(readS())
	return i
}

func readF() float64 {
	f, _ := strconv.ParseFloat(readS(), 64)
	return f
}


Measured memory_bytes: 1780
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int ans = Math.min(b / a, c);
		System.out.println(ans);
	}
}

Measured memory_bytes: 23252
INTEGER A,B,C,D
READ*,A,B,C,D
WRITE(*,FMT="(I0)",advance='no') C+B-D
WRITE(*,FMT="(A)",advance='no') " "
WRITE(*,FMT="(I0)",advance='no') D-A+C
WRITE(*,FMT="(A)",advance='no') " "
WRITE(*,FMT="(I0)",advance='no') A+B-D
WRITE(*,FMT="(A)",advance='no') " "
WRITE(*,FMT="(I0)",advance='no') B-A+C
END

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define repd(i,a,b) for (ll i = (a); i < (b); i++)
#define INF LLONG_MAX
#define mod 1000000007
typedef long long ll;

int main(void)
{
	int N;
	cin >> N;
	set<string> S;
	string a;
	rep(i,N)
	{
		cin >> a;
		S.insert(a);
	}
	cout << S.size() << endl;
	return 0;
}


Measured memory_bytes: 19204
# -*- coding: utf-8 -*-
# 整数の入力

a, b = map(int, input().split())

smaller = min(a, b)
bigger = b if a == smaller else a

diff = bigger - smaller
residual = 16 - smaller * 2
if diff * 2 > residual:
    print(":(")
else:
    print("Yay!")


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

int main()
{
    string W, T;
    int count = 0;
    int i, len;

    cin >> W;
    len = 0;
	for(i = 0; W[i]; i++){
        if(W[i] <= 'Z') W[i] = W[i] + 32;
        len++;
    }
    while(1){
        cin >> T;
        if(T == "END_OF_TEXT") break;

		for(i = 0; T[i]; i++){ if(T[i] <= 'Z') T[i] = T[i] + 32;}

        if(W == T) count++;
    };

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <map>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int h[n];
    int current[n];
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
        current[i] = 0;
    }
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        while (current[i] < h[i])
        {
            for (int j = i; j < n; j++)
            {
                if (current[j] >= h[j])
                    break;
                current[j]++;
            }
            count++;
        }
    }
    cout << count << endl;
}


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

const int MAX_N=1e5;
int N,M;
typedef pair<int,int> P;
int v2g[MAX_N];
map<int,int> g2v[MAX_N];

int main(){
	cin>>N>>M;
	REP(i,N){
		v2g[i]=i;
		g2v[i].insert(P(i,0));
	}
	bool ans=true;
	REP(i,M){
		int L,R,D;
		cin>>L>>R>>D;
		L--;
		R--;
		if (v2g[L]==v2g[R]){
			int g=v2g[L];
			if (g2v[g][R]-g2v[g][L]!=D){
				ans=false;
			}
		}else{
			int f,t,d;
			if (g2v[v2g[L]].size()<g2v[v2g[R]].size()){
				f=v2g[L];
				t=v2g[R];
				d=-D-g2v[f][L]+g2v[t][R];
			}else{
				f=v2g[R];
				t=v2g[L];
				d=D-g2v[f][R]+g2v[t][L];
			}
			for(auto i:g2v[f]){
				g2v[t][i.first]=i.second+d;
				v2g[i.first]=t;
			}
		}
	}
	cout<<(ans ? "Yes" : "No")<<endl;
	return 0;
}

Measured memory_bytes: 37504
import java.util.Scanner;

public class Main {
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    int A = Integer.parseInt(sc.next());
    int B = Integer.parseInt(sc.next());
    
    if (A == 1 && B == 1) {
      System.out.println("Draw");
    } else if (A == 1) {
      System.out.println("Alice");
    } else if (B == 1) {
      System.out.println("Bob");
    } else if (A > B) {
      System.out.println("Alice");
    } else if (A < B) {
      System.out.println("Bob");
    } else {
      System.out.println("Draw");
    }
  }
}

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

const ll MAXN = 200000;

ll N, A, B, ans=0, tmp=0;
vector<ll> DP(MAXN, 0);

const ll MAX = 500000;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    ll res=1;
    for(int i=n-k+1;i<=n;i++) {
        res *= i;
        res %= MOD;
    }
    res *= finv[k];
    res %= MOD;
    return res;
}

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

signed main(){
    cin >> N >> A >> B;
    COMinit();
    //cout << COM(N, A) << " " << COM(N, B) << endl;
    ans = modpow(2, N, MOD)-1-COM(N, A)-COM(N, B);
    while(ans>=MOD||ans<0) {
        if(ans>=MOD) ans -= MOD;
        else ans += MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 13568
#include<iostream>
using namespace std;
int main() {
  int a=0,b=0,c=0,d=0;
  for(int i=0;i<4;i++){
    char s;
    cin >> s;
    if(s == '1') a++;
    if(s == '4') b++;
    if(s == '7') c++;
    if(s == '9') d++;
  }
  if(a*b*c*d == 1) cout << "YES";
  else cout << "NO";
  return 0;
}

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

bool inBoard(int y,int x){
    if(x>=0 && x<W && y>=0 && y<H){
        return true;
    }
    return false;
}

int main(){
    cin >> H >> W;
    vector<string> s(H);
    for(int i=0;i<H;i++){
        cin >> s[i];
    }
    
    int dx[] = {0,1,0,-1};
    int dy[] = {1,0,-1,0};
    for(int y=0;y<H;y++){
        for(int x=0;x<W;x++){
            if(s[y][x] == '.'){
                continue;
            }
            bool ok = false;
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y +dy[i];
                if(!inBoard(ny,nx)){
                    continue;
                }
                if(s[ny][nx]  == '#'){
                    ok = true;
                }
            }
            if(!ok){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};


struct edge {int to;LL cost;};

const int M_N=10000;

vector<edge> G[M_N+1];
struct Dijkstra{

    LL d[M_N+1];
    void init(int n){
        fill(d,d+n,LINF);
    }

    void dijkstra(int s){
        priority_queue<P,vector<P>,greater<P>> que;
        que.push(P(0,s));
        d[s] = 0;
        while(!que.empty()){
            P p=que.top();
            que.pop();
            int v=p.second;
            if(d[v]<p.first) continue;
            for(int i=0;i<G[v].size();i++){
                edge e=G[v][i];
                if(d[e.to]>d[v]+e.cost){
                    d[e.to]=d[v]+e.cost;
                    que.push(P(d[e.to],e.to));
                }
            }
        }
    }

};


int main(){
    int n;cin >> n;
    int x,y;cin >> x >> y;
    x--,y--;
    G[x].pb({y,1});
    G[y].pb({x,1});
    for (int i = 0; i < n-1; i++) {
        G[i].pb({i+1,1});
        G[i+1].pb({i,1});
    }
    vector<int> ans(n,0);
    for (int i = 0; i < n; i++) {
        Dijkstra ds;
        ds.init(n);
        ds.dijkstra(i);
        for (int j = 0; j < n; j++) {
            ans[ds.d[j]]++;
        }
    }
    for (int i = 1; i < n; i++) {
        cout << ans[i] / 2 << endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rng(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;


int main() {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  while(k>=0) {
    if(a<b&&b<c) {
      cout << "Yes" << endl;
      return 0;
    }
    if(a>=b) b *= 2;
    else if(b>=c) c *= 2;
    k--;
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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

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

const int INF = INT_MAX / 2;

vector<int> as;

int main(void) {
    int N;
    cin >> N;

    as.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> as[i];
    }
    sort(as.begin(), as.end());

    {
        int n = as.back();

        int k = -INF;
        for (int i = 0; i < N - 1; i++) {
            if (n % 2 == 0 &&
                    (abs(n / 2 - as[i]) < abs(n / 2 - k))) {
                k = as[i];
            }
            if (n % 2 == 1 &&
                    (abs(n / 2 - as[i]) < abs(n / 2 - k) || abs(n / 2 + 1 - as[i]) < abs(n / 2 + 1 - k))) {
                k = as[i];
            }
        }

        cout << n << " " << k << endl;
    }

    return 0;
}


Measured memory_bytes: 3680
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    N, M = map(int, sysread().split())
    print(N*max(N-1,0)//2 + M*max(M-1, 0)//2)
if __name__ == "__main__":
    run()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
typedef long long ll;
#define _GLIBCXX_DEBUG
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<char>cvec;
typedef pair<ll, ll> LP;
typedef tuple<ll, ll, ll> LT;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
int main()	{
  string s,t;
  cin>>s;
  t=s;
  reverse(all(s));
  int cnt=0,n=s.size();
  rep(i,n){
    if(s[i]!=t[i])
      cnt++;
  }
  cout<<cnt/2<<endl;
}

Measured memory_bytes: 256
IDENTIFICATION DIVISION.
PROGRAM-ID. A-Birthday.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 INP      PIC X(100).
01 IN-A     PIC 9(3).
01 IN-B     PIC 9(3).
01 IN-C     PIC 9(3).
01 IN-D     PIC 9(3).
01 AB       PIC 9(3).
01 BC       PIC 9(3).
01 AC       PIC 9(3).

PROCEDURE DIVISION.
MAIN-001.
  ACCEPT INP.
  UNSTRING INP DELIMITED BY ALL ' '
      INTO IN-A IN-B IN-C IN-D.
  
  COMPUTE AB = IN-A - IN-B.
  COMPUTE BC = IN-B - IN-C.
  COMPUTE AC = IN-A - IN-C.

  IF (AC <= IN-D) OR (AB <= IN-D AND BC <= IN-D)
    DISPLAY 'Yes'
  ELSE 
    DISPLAY 'No'
  END-IF.
 
MAIN-EXIT.
  STOP RUN.

Measured memory_bytes: 384
l=input()
s=[0]*(len(l)+1)
t=[0]*(len(l)+1)
t[0]=1
m=10**9+7
for i in range(1,len(l)+1):
    if l[i-1]=="1":
        s[i]=(s[i-1]*3+t[i-1])%m
        t[i]=(t[i-1]*2)%m
    else:
        s[i]=(s[i-1]*3)%m
        t[i]=t[i-1]%m
print((s[-1]+t[-1])%m)

Measured memory_bytes: 11100
N = int(input())
L = input().split(" ")

import collections

even = collections.Counter(L[::2]).most_common(2)
odd = collections.Counter(L[1::2]).most_common(2)

if even[0][0] != odd[0][0]:
    print(N - even[0][1] - odd[0][1])
else:
    # even[0][0] == odd[0][0]
    if len(even) == 1 or len(odd) == 1:
        print(N // 2)
    else:
        print(N - max(even[0][1] + odd[1][1], even[1][1] + odd[0][1]))


Measured memory_bytes: 16172
#include <bits/stdc++.h>
const int maxn=2e5+10,mod=1e9+7;
typedef long long ll;
using namespace std;
int n,m,k,t;
int main()
{
    int i,j;
    //freopen("in.txt","r",stdin);
    int s;
    scanf("%d%d%d",&n,&k,&s);
    for(i=1;i<=k;i++)
    {
        printf("%d ",s);
    }
    for(i=k+1;i<=n;i++)
    {
        if(s!=1e9)
        printf("%d ",s+1);
        else printf("%d ",s-1);
    }
    return 0;
}


Measured memory_bytes: 1280
#include<stdio.h>
int main(){
  int n,i,check=0;
  scanf("%d",&n);
  char s[n+1];
  scanf("%s",s);
  if(n%2!=0)
    check=1;
  for(i=0;i<n/2;i++)
    if(s[i]!=s[n/2+i])
      check=1;
  if(check==1)
    printf("No\n");
  else
    printf("Yes\n");
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define e8 100000000
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int dp[42][401][401];
int a,b,c,a1,a2,n,b1;
int u[42][401][401];
int main(){
  r(i,42)r(j,401)r(k,401)dp[i][j][k]=1e8;
  dp[0][0][0]=0;
  u[0][0][0]=1;
  cin>>n>>a1>>b1;
  r(i,n){
    cin>>a>>b>>c;
    r(j,401)r(k,401)
      if(u[i][j][k]){
        if(dp[i+1][j+a][k+b]!=1e8)dp[i+1][j+a][k+b]=min(dp[i+1][j+a][k+b],dp[i][j][k]+c),u[i+1][j+a][k+b]=1;
        else dp[i+1][j+a][k+b]=dp[i][j][k]+c,u[i+1][j+a][k+b]=1;
      }
    r(j,401)r(k,401)
      if(dp[i][j][k]!=1e8){
        dp[i+1][j][k]=min(dp[i][j][k],dp[i+1][j][k]);
        u[i+1][j][k]=1;
    }
  }
  int ans=e8;
  r(j,401)r(k,401)if(u[n][j][k])if(j&&k){
    if(k*a1==j*b1){
      ans=min(ans,dp[n][j][k]);
    }
  }
  if(ans==1e8)cout<<-1<<endl;
  else cout<<ans<<endl;
}

Measured memory_bytes: 51072
//https://atcoder.jp/contests/dp/tasks/dp_h
#include <bits/stdc++.h>
#define ALL(e) e.begin(), e.end()
#define RALL(e) e.rbegin(), e.rend()
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define dbg(x) (cerr << #x << ":" << x)
#define mid (l + r) / 2
#define fi first
#define sc second
#define N 1000000009

using namespace std;

typedef long long int lli;

int main(){
	ios::sync_with_stdio(0);
	int h, w;
	cin >> h >> w;

	char mat[h+1][w+1];

	for(int i=0; i<h; i++){
		string r; cin >> r;
		for(int j=0; j<w; j++)
			mat[i][j] = r[j];
	}

	lli dp[h+1][w+1];
	memset(dp, 0, sizeof dp);

	dp[h-1][w-1] = 1;

	for(int i=h-1; i>=0; i--){
		for(int j=w-1; j>=0; j--){
			if(i == h-1 and  j== w-1) continue;
			if(mat[i][j] == '#') continue;

			dp[i][j] = (dp[i+1][j] + dp[i][j+1]) % 1000000007;
		}
	}

	cout << dp[0][0] % 1000000007;

	return 0;
}

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


Measured memory_bytes: 3620
N,M=map(int, input().split())
A=list(map(int, input().split()))
L=[]
for i in range(M):
    b,c=map(int, input().split())
    L.append((b,c))

for a in A:
    L.append((1,a))
L=sorted(L, reverse=True, key=lambda x: x[1])
ans=0
count=N
for l in L:
    n,v=l
    ans+=v*min(count, n)
    count-=n
    if count<=0:
        break

print(ans)

Measured memory_bytes: 85912
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}
const int N=50005*6;
int n,m,q,mod,g,z;
struct Edge{
	int a,b,c;
}e[N];
int fa[N];
int getf(int x){
	return fa[x]==x?x:fa[x]=getf(fa[x]);
}
int Hash(int x,int p,int q){
	return (x-1)*6+p*3+q;
}
void Merge(int x,int y){
	fa[getf(y)]=getf(x);
}
int check(int x,int y){
	return getf(x)==getf(y);
}
int pw2[2][1000005];
void Solve(int s,int t,int r){
	swap(s,t);
	r=(r+z)%mod;
	For(p,0,1)
		For(q,0,2)
			if (check(Hash(s,0,0),Hash(t,p,q))&&pw2[p][(r+(3-q)*g)%mod])
				return (void)puts("YES");
	puts("NO");
}
int main(){
	n=read(),m=read(),q=read(),mod=read();
	For(i,1,m)
		e[i].a=read(),e[i].b=read(),e[i].c=read();
	g=0;
	For(i,2,m)
		g=gcd(g,abs(e[i].c-e[1].c));
	if (!g)
		g=mod;
	z=e[1].c%g;
//	outval(g);outval(z);
	mod=gcd(mod,g*3);
	For(i,0,n*6-1)
		fa[i]=i;
	For(i,1,m){
		int a=e[i].a,b=e[i].b,c=(e[i].c-z)/g%3;
		For(p,0,1)
			For(q,0,2){
				Merge(Hash(a,p,q),Hash(b,p^1,(q*2+c)%3));
				Merge(Hash(b,p,q),Hash(a,p^1,(q*2+c)%3));
			}
	}
	clr(pw2);
	int tmp=z;
	For(i,0,mod-1)
		pw2[i&1][tmp]|=1,tmp=tmp*2%mod;
	while (q--){
		int s=read(),t=read(),r=read();
		Solve(s,t,r);
	}
	return 0;
}

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

int main()
{
  long long n, d, a;
  cin >> n >> d >> a;
  vector< pair<int,int> > xh(n);
  vector<long long> dm(n+1);
  for(int i=0; i<(n); ++i){
    cin >> xh[i].first >> xh[i].second;
    dm[i]=0;
  }
  dm[n]=0;
  sort(xh.begin(),xh.end());
  d += d;
  int ix = 0;
  long long dmg = 0, tot = 0;
  for(int i=0; i<(n); ++i){
    while(ix<n && xh[ix].first <= xh[i].first + d) ix++;
    dmg += dm[i];
    if( xh[i].second - dmg > 0 ){
      long long cnt1 = ( xh[i].second - dmg + (a-1) ) / a;
      tot += cnt1;
      cnt1 *= a;
      dmg += cnt1;
      dm[ix] -= cnt1;
    }
  }
  cout << tot << "\n";
  return 0;
}


Measured memory_bytes: 3328
N = int(input())
H = list(map(int,input().split()))
maxval = 0
tmp = 0
bef = H[0]
H.remove(H[0])

for elem in H:
    if elem <= bef:
        tmp += 1
        bef = elem
    else:
        maxval = max([tmp, maxval])
        tmp = 0
        bef = elem
maxval = max([tmp, maxval])
print(maxval)


Measured memory_bytes: 14252
function Main(input){
    input=input.split("\n");  //ここまで必須
    var moji=input[1].length;
    var limit=input[0];

    if (moji<=limit){console.log(input[1])}
    else {console.log(input[1].slice(0,input[0])+"...")}
    
}
Main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 29536
n = int(input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    print('YES' if abs((x2 - x1)*(y4 - y3) - (x4 - x3)*(y2 - y1)) < 1e-10 else 'NO')

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

using namespace std;
using ll = long long;
constexpr int mod = 1e9+7;
constexpr int md = mod;
constexpr int inf = 1000000;
vector<pair<int,int>> v = {{-1,0},{0,-1},{1,0},{0,1}};
int h,w;
vector<vector<int>> m(1020,vector<int>(1020));
vector<vector<char>> c(1020,vector<char>(1020));
queue<pair<int,pair<int,int>>> q;
void bfs(){
    while(!q.empty()){
        auto cur = q.front();q.pop();
        int y = cur.second.first;
        int x = cur.second.second;
        int cost = cur.first;
        for(auto dv : v){
            int dx = x + dv.first;
            int dy = y + dv.second;
            if(dx < 0 || dy < 0 || dx >= w || dy >= h || c[dy][dx] == '#')continue;
            q.push({cur.first+1,{dy,dx}});
            c[dy][dx] = '#';
            m[dy][dx] = cost + 1;
        }
    }
}
int main(){
    cin>>h>>w;
    vector<pair<int,int>> v;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            cin>>c[i][j];
            if(c[i][j] == '#')v.emplace_back(i,j);
        }
    }
    for(auto a : v){
        q.push({0,{a.first,a.second}});
    }
    bfs();
    int ret = 0;
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            ret = max(ret,m[i][j]);
        }
    }
    cout << ret << endl;
    return 0;
}



Measured memory_bytes: 25712
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func main() {
	scanner.Split(bufio.ScanWords)

	nBalls := nextInt()
	nBoxes := nextInt()

	if nBalls <= nBoxes {
		fmt.Println(1)
	} else {
		fmt.Println(0)
	}
}



Measured memory_bytes: 1116
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll powll(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define in2(a,b) scanf("%lld %lld",&(a),&(b))
#define in3(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c))
#define ind(a) scanf("%lf", &(a))
#define ins(a) scanf("%s", (a))
#define inc(a) scanf("%c", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a))
//      puts(a) printf("%s\n", a) 文字はこっち
//your code here!
int main(void){
    ll H, W, sum=0;
    char A[10];
    in2(H, W);
    rep(_, H){
        ins(A);
        rep(j, W) if(A[j]=='#') sum++;
    }
    if(sum==(H+W-1)) puts("Possible");
    else puts("Impossible");
    return 0;
}


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

#include<algorithm>

int a[100001];

int main() {
	int n, k;
	while (cin >> n >> k && n != 0 && k != 0) {
		a[0] = 0;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
			a[i] += a[i - 1];
		}
		int maxi = 0;
		for (int i = k; i <= n; ++i) {
			maxi = max(maxi, a[i] - a[i - k]);
		}

		cout << maxi << endl;
	}

	return 0;
}

Measured memory_bytes: 3412
#include<stdio.h>

int main(){
  int cen,x,y,r;

  scanf("%d %d",&x,&y);

  if(x<y){
    cen = x;
    x = y;
    y = cen;
  }
  r = x % y;
  while(r!=0){
    x = y;
    y = r;
    r = x % y;
  }

  printf("%d\n",y);
return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define pb push_back
#define pll pair <ll, ll>
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#define plll pair <pair <ll, ll>, ll>
#define pllll pair <pair <ll, ll>, pair <ll, ll> >
#define psl pair <string, ll>
#define all(a) a.begin(), a.end()

typedef long long ll;

typedef long double ld;

using namespace std;

const ll maxn = 1e6;
const ll inf = 1e15;

ll n, m, k, t;

ll A[maxn];

vector <ll> A1;

ll D[maxn];

ll geti(ll x) {
    return lower_bound(all(A1), x) - A1.begin();
}

int main() {
    pyshnapyshnakaa;
    ll q, w, e, a, b, c;
    cin >> n;
    for (q = 0; q < n; q++) {
        cin >> A[q];
        // A1.pb(A[q]);
    }
    ll ans1 = 1, ans2 = 1;
    for (q = 1; q < n; q++) {
        if (A[q] > A[q - 1]) {
            ans1++;
        }
        if (A[q] < A[q - 1]) {
            ans2++;
        }
    }
    ll ans = min(ans1, ans2);
    // sort(all(A1));
    // A1.resize(unique(all(A1)) - A1.begin());
    // for (q = 0; q < n; q++) {
    //     A[q] = geti(A[q]);
    // }
    vector <ll> cur = {0, A[0]};
    D[0] = 0;
    for (q = 1; q <= n; q++) {
        // cout << "CUR: " << endl;
        // for (w = 0; w < cur.size(); w++) {
        //     cout << cur[w] << " ";
        // }
        // cout << endl;
        ll d = A[q] - A[q - 1];
        vector <ll> go;
        go.pb(0);
        go.pb(d);
        sort(all(go));
        vector <ll> cur1(6, -inf);
        for (e = 0; e < cur.size(); e++) {
            for (w = 0; w < go.size(); w++) {
                cur1[e + w] = max(cur1[e + w], min(cur[e] + go[w], A[q]));
            }
        }
        cur1[2] = A[q];
        // cout << "CUR1:" << endl;
        // for (w = 0; w < cur1.size(); w++) {
        //     cout << cur1[w] << " ";
        // } 
        // cout << endl;
        // D[q] = D[q - 1];
        // sort(all(cur1));
        for (e = 0; e < cur1.size(); e++) {
            if (cur1[e] >= 0) {
                D[q] = D[q - 1] + e;
                break;
            }
        }
        cur.clear();
        for (e = 0; e < cur1.size(); e++) {
            if (cur1[e] >= 0) {
                cur.pb(cur1[e]);
            }
            if (cur.size() >= 3) {
                break;
            }
        }
        // cout << q << " " << D[q] << " D" << endl << endl;
    }
    ll realans = D[n];
    // cout << realans << endl;
    ans = min(ans, realans);
    cout << ans;
    return 0;
}


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

int main() {
    string S;
    cin >> S;

    if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) cout << "Bad" << endl;
    else cout << "Good" << 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);
		long X = sc.nextLong();
		long yen = 100;
		int ans = 0;
		while(yen < X) {
			ans++;
			yen *= 1.01;
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 27008
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cfloat>
using namespace std;

const int NMAX = 100;

int main() {
  int n, m;
  double dp[2][NMAX];
  double g[NMAX][NMAX];
  double lg[NMAX][NMAX];

  while (1) {
    cin >> n >> m;
    if (!n && !m) {
      break;
    }

    for (int i=0; i<n; ++i) {
      for (int j=0; j<n; ++j) {
        cin >> g[i][j];
        lg[i][j] = log(g[i][j]);
      }
    }
    for (int i=0; i<n; ++i) {
      dp[0][i] = 0.0;
    }

    for (int i=0; i<m-1; ++i) {
      for (int j=0; j<n; ++j) {
        dp[!(i&1)][j] = dp[i&1][0] + lg[0][j];
        for (int k=0; k<n; ++k) {
          dp[!(i&1)][j] = max(dp[!(i&1)][j], dp[i&1][k] + lg[k][j]);
        }
      }
    }

    double lans = -DBL_MAX;
    for (int i=0; i<n; ++i) {
      lans = max(lans, dp[!(m&1)][i]);
    }
    cout << fixed << setprecision(2) << round(exp(lans) * 100) / 100. << endl;
  }
  return 0;
}

Measured memory_bytes: 1520
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
// #define INF LLONG_MAX/2

using namespace std;

int MOD = 1000000007;

signed main(){

    string a;
    cin >> a;
    int cnt[26] = {0};
    rep(i,a.size()){
        cnt[a[i] - 'a']++;
    }
    int s = a.size();
    int ans = 1 + s*(s-1)/2;
    rep(i,26){
        ans -= cnt[i]*(cnt[i]-1)/2;
    }
    cout << ans <<endl;
    

    return 0;
}
// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl 

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

int main(void){
   int N;
   cin>>N;
   vector<int> a(N+1);
   for(int i=1;i<=N;i++){
      cin>>a[i];
   }
   int result=1;
   for(int i=1;i<=N;i++){
      result=a[result];
       if(result==2){
         cout<<i<<endl;
         return 0;
      }
      
   }
   cout<<-1<<endl;
   return 0;
}



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

int main() {
	
	ll i, j, k, l, r, test, n, sum=0;
	ll temp;
	cin>>n;
	temp=n;
	while(n>0) {
		r=n%10;
		sum+=r;
		n/=10;
	}
	//cout<<sum;
	if(temp%sum==0) cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()
 
#define REP(i,s,e)	for(int i=(s); i<(e); i++)
#define rep(i,n)	REP(i,0,n)
#define REPE(i,s,e)	for(int i=s; i>e; i--)
#define repe(i,n)	REPE(i,n,-1)


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<vi> vvi;
 
const int IMAX=((1<<30)-1)*2+1;
const int INF=100000000;
const double EPS=1e-10;
//int mod=1000000007


int main(){
	int n,m;
	while(cin>>n>>m){
		if(n ==0 && m == 0) break;
		vi v(n + 1, 0);
		for(int i = 0; i < n ; i++) cin>>v[i];
		vi w;
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				w.pb(v[i]+v[j]);
			}
		}
		sort(all(w));
		int ans=0;
		for(int i = 0; i < w.size(); i++){
			vi::iterator it = upper_bound(all(w),m-w[i]);
			if(it == w.begin()) continue;
			--it;
			ans = max(ans,w[i] + *it);
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 9188
n,a,b,c=map(int,input().split())
s=[input() for _ in range(n)]
if a+b+c==0:
	print("No")
elif a+b+c==1:
	ans=[]
	for x in s:
		if x=="AB":
			if a==b==0:
				print("No")
				exit()
			elif a==0:
				a+=1
				b-=1
				ans.append("A")
			else:
				b+=1
				a-=1
				ans.append("B")
		elif x=="BC":
			if b==c==0:
				print("No")
				exit()
			elif b==0:
				b+=1
				c-=1
				ans.append("B")
			else:
				c+=1
				b-=1
				ans.append("C")
		else:
			if c==a==0:
				print("No")
				exit()
			elif c==0:
				c+=1
				a-=1
				ans.append("C")
			else:
				a+=1
				c-=1
				ans.append("A")
	print("Yes")
	for x in ans:
		print(x)
else:
	ans=[]
	if s[0]=="AB":
		if a==b==0:
			print("No")
			exit()
		else:
			print("Yes")
	elif s[0]=="BC":
		if b==c==0:
			print("No")
			exit()
		else:
			print("Yes")
	else:
		if c==a==0:
			print("No")
			exit()
		else:
			print("Yes")
	s.append("AB")
	for i in range(len(s)-1):
		x=s[i]
		if x=="AB":
			if a<b:
				a+=1
				b-=1
				ans.append("A")
			elif a>b:
				b+=1
				a-=1
				ans.append("B")
			else:
				if "A" not in s[i+1]:
					b+=1
					a-=1
					ans.append("B")
				else:
					a+=1
					b-=1
					ans.append("A")
		elif x=="BC":
			if b<c:
				b+=1
				c-=1
				ans.append("B")
			elif b>c:
				c+=1
				b-=1
				ans.append("C")
			else:
				if "B" not in s[i+1]:
					c+=1
					b-=1
					ans.append("C")
				else:
					b+=1
					c-=1
					ans.append("B")
		else:
			if c<a:
				c+=1
				a-=1
				ans.append("C")
			elif c>a:
				a+=1
				c-=1
				ans.append("A")
			else:
				if "C" not in s[i+1]:
					a+=1
					c-=1
					ans.append("A")
				else:
					c+=1
					a-=1
					ans.append("C")
	for x in ans:
		print(x)

Measured memory_bytes: 17100
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <utility>
#include <typeinfo>
#include <string>
#include <sstream>

using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;

int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    int A, B, C;
    cin >> A >> B >> C;
    int tmp = B / A;
    if (tmp > C) {
        cout << C << endl;
    } else {
        cout << tmp << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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


Measured memory_bytes: 3100
a = (1,3,5,7,8,10,12)
b = (4,6,9,11)
c = set([2])
abc = [a,b,c]
x,y = map(int,input().split())
for i, checker in enumerate(abc):
    if x in checker:
        checker2 = checker
if y in checker2:
    print("Yes")
else:
    print("No")

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

def idid(x):
  c = [i+1 for i in range(n)]
  ans = 0
  div = 1
  for i in range(n):
    div *= i+1
  for i in range(n):
    div //= n-i
    for j in range(len(c)):
      if x[i] == c[j]:
        del c[j]
        ans += j * div
        break
  return ans
print(abs(idid(a)-idid(b)))

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

int main()
{
    string S, T;
    cin >> S >> T;

    if( S == T ){
        cout << "Yes" << endl;
        return 0;
    }

    map<int, int> sw;
    char c1, c2;
    for( int i = 0; i < S.length(); ++i ){
        if( S[i] == T[i] ) continue;

        c1 = S[i];
        c2 = T[i];

        if( c1 < c2 ){
            if( sw.find(c1) != sw.end() && sw[c1] == c2 ){
                cout << "No" << endl;
                return 0;
            }
            sw[c1] = c2;
        } else {
            if( sw.find(c2) != sw.end() && sw[c2] == c1 ){
                cout << "No" << endl;
                return 0;
            }
            sw[c2] = c1;
        }

        
        for( int j = 0; j < S.length(); ++j ){
            if( S[j] == c1 )
                S[j] = c2;
            else if( S[j] == c2 )
                S[j] = c1;

            //cout << "S(" << S[j] << "," << c1 << "): " << S << endl;

            if( S == T ){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cerr << #a << ": " << (a) << "\n"

typedef long long ll;

const int N = 1e5 + 10;
int n, a[N], dp[N];

int main() {
	// freopen("in", "r", stdin);
	// freopen("out", "w", stdout);
	ios::sync_with_stdio(0);cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	dp[n] = 0;
	dp[n - 1] = abs(a[n - 1] - a[n]);
	for (int i = n - 2; i >= 1; i--) {
		dp[i] = min(abs(a[i] - a[i + 1]) + dp[i + 1], abs(a[i] - a[i + 2]) + dp[i + 2]);
	}
	cout << dp[1] << endl;

	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <unordered_map>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100000000;

struct l
{
   string s;
   int t;
};

int main()
{
   int n;
   cin >> n;
   vector<l> a(n);
   rep(i,n)
   {
      string hoge;
      int foo;
      cin >> hoge >> foo;
      a[i].s=hoge;
      a[i].t=foo;
   }
   string s;
   cin >> s;
   bool foo=false;
   int ans=0;
   rep(i,n)
   {
      if(foo)ans+=a[i].t;
      if(s==a[i].s)foo=true;
   }
   cout<<ans<<endl;

   
   return 0;
}

Measured memory_bytes: 256
//----------------------------------------------------------------------
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
//----------------------------------------------------------------------

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(void) {
    int s, w;
    cin >> s >> w;
    cout << (w >= s ? "unsafe" : "safe") << endl;
    return 0;
}

Measured memory_bytes: 3632
// #include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;

#define all(x) begin(x), end(x)
#define rep(i,n) for(int i=0; i<n; i++)

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

    vector<int> p(n);
    rep(i, n) cin >> p[i];

    sort(all(p));
    int ans = 0;
    rep(i, k) ans += p[i];
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
N = int(input())
if N<10:
    ans = N
elif 10<=N and N<100:
    ans = 9
elif 100<=N and N<1000:
    ans = 9+(N-100)+1
elif 1000<=N and N<10000:
    ans = 9+900
elif 10000<=N<100000:
    ans = 9+900+(N-10000)+1
else:
    ans = 90909
    
print(ans)

Measured memory_bytes: 3060
n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
ll = sorted(l)
count, total, i = 0, 0, 0
while count < m:
    count += ll[i][1]
    total += ll[i][0]*ll[i][1]
    i += 1
total += ll[i-1][0]*(m-count)
print(total)

Measured memory_bytes: 61528
import queue
def allvisited():
    for i in range(w):
        for j in range(h):
            if (visited[i][j]==False and s[i][j]=='1'):
                return (False,i,j)
    else:
         return (True,-1,-1)
        
def legal(pos):
    if(0<=pos[0]<w) and (0<=pos[1]<h) and s[pos[0]][pos[1]]=='1' and visited[pos[0]][pos[1]]==False:
        return True
    else:
        return False
    
d=[[0,1],[0,-1],[1,0],[-1,0],[1,1],[-1,1],[1,-1],[-1,-1]]
while(1):
    h,w=map(eval,input().split())
    if (w==0 and h==0): break
    s=[]
    for i in range(w):
        s.append(input().split())
    #print(s)
    Q=queue.Queue()
    visited=[]
    for i in range(w):
        visited.append([False]*h)
    #print(visited)
    count=0
    while(1):
        a=allvisited()
        if (a[0]==False):
            Q.put((a[1],a[2]))
            visited[a[1]][a[2]]=True
            count+=1
        else:
            break
        while(not Q.empty()):
            now=Q.get()
            for i in range(8):
                new=(now[0]+d[i][0],now[1]+d[i][1])
                if(legal(new)):
                    Q.put(new)
                    visited[new[0]][new[1]]=True
    print(count)

Measured memory_bytes: 8472
a,b = map(int,input().split())
s = input()
num = ["0","1","2","3","4","5","6","7","8","9"]

flag = True

if not all(x in num for x in s[0:a]):
    flag = False

if not s[a] == "-":
    flag = False

if not all(x in num for x in s[a+1:a+1+b]):
    flag = False

if flag:
    print("Yes")
else:
    print("No")


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

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> void chmax(T& a,const T& b){if(a < b) a = b;}
template<typename T> void chmin(T& a,const T& b){if(b < a) a = b;}
typedef long long ll;

int N,K;
int cnt [26];

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

	cin >> N >> K;
	FOR(i,0,N){
		string S;
		cin >> S;
		cnt [S.front() - 'A']++;
	}

	FOR(i,0,N){
		sort(cnt,cnt + 26,greater<int>());
		FOR(j,0,K){
			if(cnt [j]){
				cnt [j]--;
			}
			else{
				cout << i << endl;
				return 0;
			}
		}
	}

	cout << N << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
 #include<vector>
 #include<string>
 #include<algorithm>
 #include<map>
 #include<cmath>
 #include<queue>
 #include<stack>
 #include<list>
 
 #define endl "\n"
 using namespace std;
 using ll = long long;
 const ll MOD = 1e9+7;
 const ll INF = 1e18;
 #define REP(i, n) for(int i = 0; i < n; i++)
 using Graph = vector<vector<int>>;
 
 int main(){
     ll n,m,k;
     cin>>n>>m>>k;
     vector<ll> a(n),b(m),sa(n+1),sb(m+1);
     sa[0] = 0,sb[0] = 0;
     for(ll i=0;i<n;i++){
         cin>>a[i];
         sa[i+1] = sa[i] + a[i];
     }
     for(ll i=0;i<m;i++){
         cin>>b[i];
         sb[i+1] = sb[i] + b[i];
     }
    
    ll ans = 0;
    ll right = m;
    for(ll left=0; left<=n; left++){
        while(right > 0 && sa[left] + sb[right] > k){
            right--;
        }
        if(right == 0 && sa[left] + sb[right] > k) continue;
        ans = max(ans,right + left);
    }


     cout<<ans<<endl;
 }

Measured memory_bytes: 9564
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func bitCount(bits int) int {

	bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
	bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
	bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
	bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
	return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff)
}

func main() {
	sc.Split(bufio.ScanWords)

	N, M := getInt(), getInt()
	s := make([]int, M)
	for i := 0; i < M; i++ {
		k := getInt()
		for j := 0; j < k; j++ {
			b := getInt() - 1
			s[i] |= 1 << uint(b)
		}
	}
	p := make([]int, M)
	for i := 0; i < M; i++ {
		p[i] = getInt()
	}

	// for i := 0; i < M; i++ {
	// 	fmt.Printf("%d %b\n", i, s[i])
	// }

	bit := 1 << uint(N)
	ans := 0
	for i := 0; i < bit; i++ {
		ok := true
		for j := 0; j < M; j++ {
			//fmt.Printf("%b %d\n", i, j)
			x := i & s[j]
			y := bitCount(x)
			if y%2 != p[j] {
				ok = false
				break
			}
		}
		if ok {
			ans++
		}
	}
	out(ans)
}


Measured memory_bytes: 640