akhauriyash/Code-Regression huggingface dataset:
#include<iostream>

int main(){
    long long a, b, c;
    std::cin >> a >> b >> c;
    long long tmp = (c - a - b);
    if(tmp < 0){
        tmp = 0;
    }
    tmp *= tmp;
    
    long long tmpl = 4 * a * b;
    
    if(tmpl < tmp){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
    
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;

long n, sum;
vector<long> v;
int main(){
	cin >> n;

	for (int i = 0; i < n; ++i){
		long buf;
		cin >> buf; sum += buf;
		v.push_back(buf);
	}
	
	sort(v.begin(), v.end());

	printf("%ld %ld %ld\n", v.front(), v.back(), sum);

	return 0;
}

Measured memory_bytes: 1328
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;

int main(void){
  int n,p,i,cnt=0;
  cin>>n;
  for(i=0;i<n;i++){
    cin>>p;
    if(p!=i+1)cnt++;
  }

  if(cnt==2||cnt==0)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

	return 0;
}

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

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

void solve(){
    int ans = 0;
    for(int k=0; k<=7; k++){
        cout << k+1 << endl;
        string res;
        cin >> res;
        if(res == "Yes") return;
        if(res == "Near") ans += 1<<k;
    }
    cout << ans+1 << endl;
    string res;
    cin >> res;
    assert(res == "Yes");
}

int main(){
    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> edges;
    for(int i=8; i<N; i++) for(int k=0; k<=7; k++) if(nth_bit(i, k)) edges.emplace_back(i, k);
    cout << edges.size() << endl;
    for(auto& p : edges) cout << p.first+1 << " " << p.second+1 << endl;
    while(K--) solve();
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  int k, x;
  cin >> k >> x;
  if(500 * k >= x) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3608
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, X;
    cin >> N >> M >> X;
    int sum = 0;
    rep(i, M) {
        int a; cin >> a;
        if (a < X) sum++;
    }
    cout << min(sum, M - sum) << endl;

    return 0;
}


Measured memory_bytes: 256
type
	intArray = array[1..1000] of integer;
var i,n:integer;
    v:intArray;
    ans:real;


procedure	swap(var a,b:integer);
var tmp:integer;
begin
	tmp:=a;
	a:=b;
	b:=tmp
end;
    
procedure QuickSort(var a:intArray;start_index,end_index:integer);
var i,j,x:integer;
begin
	x:=a[(start_index+end_index)div 2];
	i:=start_index;
	j:=end_index;
	while(true)do
	begin
		while(a[i]<x)do i:=i+1;
		while(x<a[j])do j:=j-1;
		if(i<j)then
		begin
			swap(a[i],a[j]);
			i:=i+1;
			j:=j-1;
		end else
		begin
			if(start_index<i-1)then QuickSort(a,start_index,i-1);
			if(j+1<end_index)then QuickSort(a,j+1,end_index);
			exit;
		end;
	end;
end;

begin
	readln(n);
  for i:=1 to n do read(v[i]);
   QuickSort(v,1,n);
   ans := 0.0 + v[1];
   for i:=2 to n do ans := (ans + v[i]) / 2;
	writeln(ans);
end.

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

#pragma warning(disable:4996)

int main()
{
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		sum += x;
	}
	cout << sum - 1-n+1;
	return 0;
		
	
	
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

const int N = 100;
int n;

int main()
{
	scanf("%d",&n);
	if(n%2==1)
	{
		printf("%d\n",n*(n-1)/2-n/2);
		for(int i=1; i<=n; i++)
		{
			for(int j=i+1; j<=n; j++)
			{
				if(i+j==n) continue;
				printf("%d %d\n",i,j);
			}
		}
	}
	else
	{
		printf("%d\n",n*(n-1)/2-n/2);
		for(int i=1; i<=n; i++)
		{
			for(int j=i+1; j<=n; j++)
			{
				if(i+j==n+1) continue;
				printf("%d %d\n",i,j);
			}
		}
	}
	return 0;
}

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

int main() {
  int n;
  string s;
  cin>>n;
  cin>>s;
  int ok = 0, ng = n/2+1;
  while (ok+1 < ng) {
    int mid = (ok+ng)/2;
    bool flag = false;
    rep(j, n-mid) {
      if ((s.substr(j+mid)).find(s.substr(j, mid)) != string::npos) {
        flag = true;
        break;
      }
    }
    if (flag) ok = mid;
    else ng = mid;
  }
  cout<<ok<<endl;
  return 0;
}

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

int main () {
  int h, w, K;
  std::cin >> h >> w >> K;
  std::vector<string> c(h);
  rep(i, h) {
    std::cin >> c[i];
  }
  int ans = 0;
  rep(k, 1 << (h + w)) {
    int black = 0;
    rep(i, h) rep(j, w) {
      int a = k & (1 << j);
      int b = k & (1 << (i + w));
      if (!a && !b && c[i][j] == '#') ++black;
    }
    if(black == K) ++ans;
  }
  std::cout << ans << "\n";
}

Measured memory_bytes: 3612
import java.util.Arrays;
import java.util.Scanner;

public class Main implements Runnable {

    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 128 * 1024 * 1024).start();
    }

    public void run() {
        int n = sc.nextInt();
        int v1[][] = new int[100001][2];
        int v2[][] = new int[100001][2];
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                int s = sc.nextInt();
                v1[s][0] = s;
                v1[s][1]++;
            } else {
                int s = sc.nextInt();
                v2[s][0] = s;
                v2[s][1]++;
            }
        }

        srt2DArray(v1);
        srt2DArray(v2);

        if(v1[0][0] == v2[0][0]) {
            boolean ss = false; // first convert
            for (int i = 0; i < 100001; i++) {
                if (v1[i][1] < v2[i][1]) {
                    break;
                } else if (v1[i][1] > v2[i][1]) {
                    ss = true;
                    break;
                }
            }

            if (!ss) {
                System.out.println(n / 2 - v1[0][1] + n / 2 - v2[1][1]);
            } else {
                System.out.println(n / 2 - v1[1][1] + n / 2 - v2[0][1]);
            }
        } else {
            System.out.println(n / 2 - v1[0][1] + n / 2 - v2[0][1]);
        }
    }

    static void srt2DArray(int[][] array) {
        Arrays.sort(array, (a, b) -> {
            if (a[1] > b[1]) {
                return -1;
            } else if (a[1] == b[1]) {
                return 0;
            } else {
                return 1;
            }
        });
    }
}


Measured memory_bytes: 69568
N=int(input())
S=str(input())
S=list(S)
ans=S.count('R')*S.count('G')*S.count('B')
for i in range(N): #判定を簡単にするためR:=1,G:=2,B:=4と置き換えておく
    if S[i]=='R':
        S[i]=1
    elif S[i]=='G':
        S[i]=2
    elif S[i]=='B':
        S[i]=4
for i in range(0,N-2):
    for j in range(i+1,N-1):
        k=(j-i)+j
        if k>N-1:
            continue
        if S[i]+S[j]+S[k] == 7 :
            ans -= 1
print(ans)

Measured memory_bytes: 9212
#Bingo
bingo = [list(map(int,input().split())) for i in range(3)]
N = int(input())
b = [int(input()) for i in range(N)]
#縦横斜めで８通り。
cnt = [0]*8
for i in range(3):
    for j in range(3):
        if bingo[i][j] in b:
            cnt[i] += 1
            cnt[j+3] += 1
            if i == j:
                cnt[-1] += 1
            if i+j == 2:
                cnt[-2] += 1
ans = "No"
for i in cnt:
    if i >= 3:
        ans = "Yes"
        break
print(ans)

Measured memory_bytes: 9080
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, a, b;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> n;
	vector<ll> v;
	ll ans = 0;
	bool flag = true;
	rep(i, 0, n){
		cin >> a >> b;
		ans += a;
		if(a > b){
			v.push_back(b);
		}
		if(a != b){
			flag = false;
		}
	}
	sort(v.begin(), v.end());
	
	if(flag){
		print(0)
	}
	else{
		print(ans-v[0])
	}
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
template <class T> T input() {T t; cin>>t; return t;}
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define PRINT_ARRAY_H(a) REPALL(__i,a) {cout<<a[__i]<<(__i != a.size()-1 ? " " : "");} newline;
#define e1 first
#define e2 second
#define newline putchar('\n')
#define cspace ' '
#define sspace " "
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};

ll mypow(ll a, ll b, ll mod)
{
    ll r = 1ll;
    while(b != 0){
        if(b&1) r = r * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return r;
}

ll f(int num)
{
    ll r = 0;
    while (num) {
        r += (num & 1ll);
        num /= 2;
    }
    return r;
}

int main()
{
    ll n;
    string x;
    cin>>n>>x;
    ll pop = 0, incpop, decpop;
    ll num, incnum = 0ll, decnum = 0ll;
    REP(i,n) pop += (x[i] == '1');
    incpop = min(pop + 1, n); decpop = max(pop - 1, 0ll);
    REP(i,n) {
        if (x[i] == '1') {
            incnum += mypow(2, n - 1 - i, incpop);
            incnum %= incpop;
            if (decpop != 0) {
                decnum += mypow(2, n - 1 - i, decpop);
                decnum %= decpop;
            }
        }
    }

    //cout<<incpop<<sspace<<decpop<<endl;
    //cout<<incnum<<sspace<<decnum<<endl;
    REP(i,n) {

        int cnt = 1;
        if (x[i] == '0') {
            num = (incnum + mypow(2, n - 1 - i, incpop)) % incpop;
        } else {
            if (decpop == 0) {
                cout<<0<<endl;
                continue;
            }

            num = (decnum - mypow(2, n - 1 - i, decpop) + decpop) % decpop;
        }
        //cout<<num<<": ";
        while (num) {
            num = num % f(num);
            cnt++;
        }

        cout<<cnt<<endl;
    }

    return 0;
}


Measured memory_bytes: 3720
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int i, number_left, number_right;
    for(i = 0; ; i++) {
      number_left = Integer.parseInt(sc.next());
      number_right = Integer.parseInt(sc.next());
      if(number_left == 0 && number_right == 0) break;
      if(number_right < number_left) {
        int temp = number_right;
        number_right = number_left;
        number_left = temp;
      }
      System.out.println(number_left + " " + number_right);
    }
  }
}



Measured memory_bytes: 36076
k, n = map(int, input().split())
a = [0] * n

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

max = 0
max_i = 0
for i in range(n - 1):
    if a[i+1] - a[i] > max:
        max = a[i+1] - a[i]
        max_i = i

if k - a[-1] + a[0] > max:
    max = k - a[-1] + a[0]
    max_i = len(a) - 1

print(k - max)

Measured memory_bytes: 78924
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
Xs = nl()
if N >= M:
    print(0)
    import sys
    sys.exit()

Xs = sorted(Xs)
Ls = []
for i in range(1, len(Xs)):
    Ls.append(Xs[i] - Xs[i-1])
Ls = sorted(Ls, reverse=True)
print(sum(Ls) - sum(Ls[:N-1]))



Measured memory_bytes: 13968
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long int ll;
typedef unsigned long long int ull;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,c;
  string s,t;
  cin >>a;
  cout <<a*a*a;
}

Measured memory_bytes: 3580
#include <stdio.h>

int main(){

  int a,b,x,tmp;

  scanf("%d %d",&a,&b);
  
  if(a < b){
    tmp = a;
    a = b;
    b = tmp;
  }

  x = a % b;
  while(x!=0){
    a = b;
    b = x;
    x =a % b;
  }
  printf("%d\n",b);
  
  return 0;
}

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

int main(){
    char a,b;
    cin >> a >> b;
    char ans;
    if(a == 'H'){
        ans = b;
    }else{
        if(b == 'H'){
            ans = 'D';
        }else{
            ans = 'H';
        }
    }
    cout << ans << endl;
}


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

using namespace std;

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> L(M, 0);
    for (int i = 0; i < M; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int s;
            cin >> s;
            L[i] |= (1 << (s-1));
        }
    }
    vector<int> p(M);
    for (int i = 0; i < M; i++) {
        cin >> p[i];
    }
    
    int ans = 0;
    for (int bit = 0; bit < (1<<N); ++bit) {
        bool ok = true;
        for (int i = 0; i < M; i++) {
            if(__builtin_popcount(bit & L[i]) % 2 != p[i]){
                ok = false;
            }
        }
        if(ok) {
            ans++;
        }
    }
    
    cout << ans << endl;
}

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


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector <int> a(2*N);
  for(int i = 0;i<2*N;i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  int ans = 0;
  for(int i = 0;i<N;i++){
    ans = ans + a[i*2];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var x, a, b float64
	fmt.Scan(&x, &a, &b)
	if math.Abs(x-a) < math.Abs(x-b) {
		fmt.Println("A")
	} else {
		fmt.Println("B")
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define INF 100000000

int main() {

	int n, m, r;
	cin >> n >> m >> r;

	vector<int> rr(r);
	for (int i = 0; i < r; i++) {
		cin >> rr[i];
		rr[i]--;
	}

	int a, b;
	long long int c;

	vector< vector<long long int> > dp(n, vector<long long int>(n, INF));

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		a--;
		b--;
		dp[a][b] = dp[b][a] = c;
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}

	sort(rr.begin(), rr.end());

	long long int MIN = INF;

	do {
		long long int ans = 0;
		for (int i = 0; i < r-1; i++) {
			ans += dp[rr[i]][rr[i + 1]];
		}
		MIN = min(MIN, ans);
	} while (next_permutation(rr.begin(), rr.end()));

	cout << MIN << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int a,b,c;
	ll k;
	scanf("%i %i %i %lld",&a,&b,&c,&k);
	if(k&1) printf("%i\n",b-a);
	else printf("%i\n",a-b);
	return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  int c,n,m;
  cin >> c >> n >> m;
  vector<int> dp(c+1,0);
  int s,p;
  rep(i,n){
    cin >> s >> p;
    per(j,c+1){
      if(j>=s) dp[j]=max(dp[j],dp[j-s]+p);
    }
  }
  repp(i,1,m+1){
    cout << dp[c/i]*i << endl;
  }
  return 0;
}



Measured memory_bytes: 3120
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repp(i,a,b)  for(int i=a;i<=(int)(b);i++)
#define cs ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
int main(){
    cs;
    int x;
    vector<int> v(5);
    rep(i,5) cin>>v[i];
    cin>>x;
    rep(i,5){
        repp(j,i+1,4) if(v[j]-v[i]>x) {cout<<":(";return 0;}
    }
    cout<<"Yay!";
}

Measured memory_bytes: 256
import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))


N,M=acinput()
d=[[]for i in range(N+1)]
for i in range(M):
    p, s = input().split(" ")
    p=int(p)
    d[p].append(s)

#d=sorted(d,key=lambda x:x[1])

pen=0

nsolve=0
for sd in d:
    #ssd=sorted(sd)
    #print(sd)
    pem_tmp = 0
    for ssd in sd:
    
        if ssd=="AC":
            nsolve+=1
            pen+=pem_tmp
            break
        else:
            pem_tmp+=1

print(nsolve,pen)


Measured memory_bytes: 29268
N,M,K=map(int, input().split())


#隣り合うブロックN-1
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

p=998244353
n = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p) 階乗のmod
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
ans=0

for i in range(K+1):
    if i==0:
        ans+=(M*pow(M-1,N-1,p)%p)
        ans%=p
    else:
        ans+=cmb(N-1,i,p)*(M*pow(M-1,N-1-i,p)%p)
        ans%=p
print(ans)

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/03/02  Problem: 002_agc_c / Link: https://agc002.contest.atcoder.jp/tasks/agc002_c?lang=en  ----- */
/* ------問題------

N 本のロープがあります。 ロープは 1 から N まで番号が振られています。 ロープ i の長さは ai です。
最初、1≤i≤N−1 について、ロープ i の右端とロープ i+1 の左端が結ばれています。 高橋君は次の操作を N−1 回行い、すべての結び目をほどこうとしています。
ひと繋がりのロープのうち、長さの総和が L 以上のものをひとつ選ぶ。 選んだひと繋がりのロープに結び目があれば、結び目のうちどれかひとつをほどく。
高橋君は結び目をほどく順番を工夫し、すべての結び目をほどくことができるでしょうか？ 可能か判定し、可能ならば結び目をほどく順番をひとつ求めてください。

-----問題ここまで----- */
/* -----解説等-----

ケツに着目する

----解説ここまで---- */

LL N, L;


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

	cin >> N >> L;
	VL a(N);
	FOR(i, 0, N) {
		cin >> a[i];
	}
	LL pos = -1;
	FOR(i, 0, N - 1) {
		if (a[i] + a[i + 1] >= L) {
			pos = i;
		}
	}
	if (pos == -1) {
		cout << "Impossible" << endl;
	}
	else {
		cout << "Possible" << endl;
		VI ans(N - 1);
		FOR(i, 0, pos) {
			cout << i + 1 << " ";
		}
		FORR(i, N - 1, pos) {
			cout << i << " ";

		}cout << endl;
	}

	return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int main()
{
long int n;
vector<long int> a;
cin>>n;
long int x,i;
for(i=0;i<n;i++)
{
cin>>x;
a.push_back(x);
}
long int crnmny=1000,stk;
for(i=0;i<n-1;i++)
{
if(a[i]<a[i+1])
{
stk=crnmny/a[i];
crnmny+=(a[i+1]-a[i])*stk;
}
}
cout<<crnmny;
return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()



int main() {
    int N;
    cin>>N;
    vector<int> a(N);
    for(int i=0;i<N;i++)
        cin>>a.at(i);
    cout<<*max_element(a.begin(),a.end())-*min_element(a.begin(),a.end())<<endl;

}

Measured memory_bytes: 256
N, Q = map(int, input().split())
S = input()
AClist = [0] 
for i in range(N-1):
    if S[i+1] == "C" and S[i] == "A":
        AClist.append(AClist[-1] + 1)
    else:
        AClist.append(AClist[-1])
for i in range(Q):
    l , r = map(int, input().split())
    print(AClist[r-1] - AClist[l-1])

Measured memory_bytes: 6100
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rep2(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rev(i, n) for (int (i) = (n)-1; (i) >= 0; (i)--)
#define rev2(i, a, b) for (int (i) = (a)-1; (i) >= (b); (i)--)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Pll = pair<long long, long long>;
template<class T> using Vec = vector<T>;
template<class T> using VVec = vector<vector<T>>;
long long TEN(int i) {return !i ? 1 : TEN(i-1)*10LL;}
template<class T, class U> 
bool chmin(T& a, const U& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T, class U> 
bool chmax(T& a, const U& b) {if (a < b) {a = b; return 1;} return 0;}

struct IoSetup {
	IoSetup() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} iosetup;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

ll N;

void solve() {
	Vec<ll> dv = divisor(N);
	ll ans = TEN(18);
	rep (i, dv.size()) {
		chmin(ans, dv[i] - 1 + N / dv[i] - 1);
	}
	cout << ans << endl;
}

int main() {
	cin >> N;
	solve();
	
	return 0;
}

Measured memory_bytes: 3684
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<i64>();
    let (n, k) = (v[0] as usize, v[1]);
    let mut a = read_vec::<i64>();
    let mut f = read_vec::<i64>();

    a.sort();
    f.sort();
    f.reverse();

    let h = a.iter().zip(f.iter()).map(|(x, y)| x * y).max().unwrap();
    let criterion = |goal: i64| {
        let mut k = k;
        for i in 0..n {
            if a[i] * f[i] <= goal {
                continue;
            }
            k -= (a[i] * f[i] - goal + f[i] - 1) / f[i];
        }
        k < 0
    };
    let ans = binary_search(-1, h, criterion);
    println!("{}", ans.1);
}

fn binary_search<F>(lb: i64, ub: i64, criterion: F) -> (i64, i64)
where
    F: Fn(i64) -> bool,
{
    let mut ok = lb;
    let mut ng = ub;
    while ng - ok > 1 {
        let mid = (ng + ok) / 2;
        if criterion(mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    (ok, ng)
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

int main(){
    string s;
    cin>>s; 
    if(s=="ABC"){
        cout<<"ARC"<<endl;
    }else{
        cout<<"ABC"<<endl;
    }

}


Measured memory_bytes: 3628
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func main() {
	sc.Split(bufio.ScanWords)
	a := nextInt()
	p := nextInt()
	piesNum := (a*3 + p) / 2
	fmt.Println(piesNum)
}


Measured memory_bytes: 640
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define SZ(X) ((int64_t)((X).size()))
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define intmax (std::numeric_limits<int64_t>::max() / 4)
#define doublemax (std::numeric_limits<double>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);



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

	int N;
	cin >> N;
	vector<string>S(N);
	rep(i, N)cin >> S[i];
	
	vector<vector<int>>a(N, vector<int>(26, 0));
	rep(i, N)rep(j, S[i].size())a[i][S[i][j] - 'a']++;
	rep(i, 26) {
		int ans = intmax;
		rep(j, N)ans = min(ans, a[j][i]);
		char c = 'a' + char(i);
		rep(i, ans)cout << c;
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <limits.h>

#define SENTINEL INT_MAX

int cmpCnt = 0;

void merge(int S[], int left, int mid, int right) {
    int n1 = (mid + 1) - left;
    int n2 = right - mid;

    int L[n1 + 1], R[n2 + 1];
    for (int i = 0; i < n1; i++) L[i] = S[left + i];
    for (int i = 0; i < n2; i++) R[i] = S[(mid + 1) + i];

    L[n1] = SENTINEL;
    R[n2] = SENTINEL;

    int i = 0, j = 0;

    for (int k = left; k <= right; k++) {
        cmpCnt++;
//        printf("L[%d]: %d, R[%d]: %d\n", i, L[i], j, R[j]);
        if (L[i] <= R[j]) {
            S[k] = L[i];
            i++;

        } else {
            S[k] = R[j];
            j++;
        }
    }

    // for (int p = left; p <= right; p++) {
    //     printf("S[%d]: %d\n", p, S[p]);
    // }
}

void mergeSort(int S[], int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = (left + right) / 2;
//    printf("left: %d, mid: %d, right: %d\n", left, mid, right);
    mergeSort(S, left, mid);
    mergeSort(S, mid + 1, right);
//    printf("call merge arg[left: %d, mid: %d, right: %d]\n", left, mid+1, right);
    merge(S, left, mid, right);
}

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

    int S[n];
    for (int i = 0; i < n; i++) scanf("%d", &S[i]);

    mergeSort(S, 0, n - 1);

    for (int i = 0; i < n; i++) {
        if (i == n - 1) {
            printf("%d", S[i]);
        } else {
            printf("%d ", S[i]);
        }
    }
    printf("\n%d\n", cmpCnt);

    return 0;
}



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

using namespace std;

int main()
{
	int n, m, x;
	cin >> n >> m >> x;
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}

	int t = 0;
	for (int i = 0; i < m; i++) {
		if (a[i] < x) {
			t++;
		}
	}
	cout << (t > m - t ? m - t : t) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) obj.begin(),obj.end()
#define pb(obj) push_back(obj)
#define REP(i,N) for(ll i=0;i<N;i++)
typedef long long ll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    char a='a',b;
    for(int i=0;i<4;i++){
        cin>>b;
        if(a==b){cout<<"Bad"<<endl;exit(0);}
        a=b;
    }
    cout<<"Good"<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		int q = sc.nextInt();
		int[][] query = new int[q][4];
		for(int i = 0; i < q; i++){
		    query[i][0] = sc.nextInt()-1;
		    query[i][1] = sc.nextInt()-1;
		    query[i][2] = sc.nextInt();
		    query[i][3] = sc.nextInt();
		}
		
		// 計算
		long result = 0;
		int[] list = new int[n];
		result = func(list, m, 0, 0, query);
		
		// 出力
		System.out.println(result);
	}
	
	static int func(int[] list, int m, int i, int result, int[][] query){
	    if(list.length == i){
	        return calc(list, query);
	    }
	    int from = 1;
	    if(i > 0) from = list[i-1];
	    for(int j = from; j <= m; j++){
	        list[i] = j;
	        result = max(result, func(list, m, i+1, result, query));
	    }
	    return result;
	}
	
	static int calc(int[] list, int[][] query){
	    int sum = 0;
	    for(int i = 0; i < query.length; i++){
	        if(list[query[i][1]] - list[query[i][0]] == query[i][2]){
	            sum += query[i][3];
	        }
	    }
	    return sum;
	}
}



Measured memory_bytes: 27836
#include "bits/stdc++.h"
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
typedef long long ll;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef set<int> SI;
typedef map<string, int> MSI;
typedef map<int, int> MII;
typedef pair<ll, ll> PLL;
typedef pair<ll, pair<ll, ll>> PLLL;

#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MP make_pair
#define PB push_back
#define FF first
#define SS second
#define MOD 1000000007
#define test ll t;cin>>t;while(t--)

void solve()
{
	ll a,b,c,d;
	cin >> a >> b >> c >> d;

	ll x=a*c;
	ll y=a*d;
	ll z=b*c;
	ll p=b*d;

	cout << max(x,max(y,max(z,p)));
}

int main()
{
	flash;

	// test
	// {
	// 	solve();
	// }
	solve();

	return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
int main(void){
  int w,n;
  scanf("%d",&w); scanf("%d",&n);
  int num[n];
  for(int i=1;i<=w;i++){
      num[i]=i;
  }
  for(int i=1;i<=n;i++){
      int a,b,x;
      scanf("%d,%d",&a,&b);
      x=num[a]; num[a]=num[b]; num[b]=x;
  }
  for(int i=1;i<=w;i++)
  printf("%d\n",num[i]);
   return 0;
}



Measured memory_bytes: 1912
//O7Oo7oO7O

#include <bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

using ll = long long int;
const int mxN=1e5+2,mxK=101;
const long long inf=9e18;
ll dp[mxN];
ll st[mxN];
ll n,k;
ll findMin(ll i,ll a[])
{
	if(i>=n-1) 
		return 0;
	if(dp[i]!=-1)
		return dp[i];
	ll mn=inf;
	for(ll j=1;j<=k;j++)
	{
		
		
		if(i+j<=n-1)
		mn=min(mn,abs(a[i+j]-a[i])+findMin(i+j,a));

	}
	
	return dp[i]=mn;
}
int main()
{
	IOS
	
        memset(dp,-1,sizeof(dp));
   	cin>>n>>k;

   	
   	for(ll i=0;i<n;i++) cin>>st[i];
   	//mn=inf;
   	
   	
   	ll ans=findMin(0,st);
   	cout<<ans<<"\n";

    return 0;
}



Measured memory_bytes: 8192
import sys
from collections import defaultdict
import math

def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    g = A[0]

    for i in range(1,N):
        g = math.gcd(g,A[i])

    print(g)





if __name__ == "__main__":
    main()


Measured memory_bytes: 87232
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: u32,
        m: u32,
        a: [u32; m],
    }
    let mut tot = 0;
    for i in a {
        tot += i;
    }
    if n >= tot {
        println!("{}", n-tot);
    } else {
        println!("{}", -1);
    }
}


Measured memory_bytes: 2200
#include <stdio.h>
#define N 10000000
int heap[N];
int last;
unsigned seed=0x12121204;
void push(int n){
    int i=last,j=(i-1)>>1;
    while(i>0&&heap[j]>n){
        heap[i]=heap[j];
        i=j;
        j=(i-1)>>1;
    }
    heap[i]=n;
    last++;
}
int pop(){
    last--;
    int a=heap[0];
    int t=heap[last],i=0,j;
    j=1+(heap[1]>heap[2]);
    while(j<last&&t>heap[j]){
        heap[i]=heap[j];
        i=j;
        if(j*2+1<last&&heap[j*2+1]>heap[j*2+2]){
            j=j*2+2;
        }else{
            j=j*2+1;
        }
    }
    heap[i]=t;
    return a;
}

int abbs(int n){
    if(n>0) return n;
    return -n;
}

int main(void){
    int n,l;
    int a[216],b[216];
    int i,j,h,sorted=1,tmp,min=10000000;
    scanf("%d%d",&n,&l);
    for(i=0;i<n;i++){
        a[i]=l+i;
        b[i]=abbs(l+i);
        if(b[i]<min) min=b[i];
    }
    int sum=0;
    for(i=0;i<n;i++){
        if(b[i]!=min)
            sum+=a[i];
    }
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

long long mod = 1000000007;
long long fact[2200009], inv[2200009];

void init() {
	fact[0] = 1;
	for (int i = 1; i <= 2200000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 2200000; i++) inv[i] = Div(1, fact[i], mod);
}

long long ncr(long long n, long long r) {
	if (n < r || r < 0) return 0;
	return (fact[n] * inv[r] % mod) * inv[n - r] % mod;
}

long long sx, sy, gx, gy;
long long ans = 0;

int main() {
	cin >> sx >> sy >> gx >> gy; init();
	for (int i = sx; i <= gx; i++) {
		long long V1 = ncr((i + 1) + (sy - 1), sy - 1);
		long long V2 = ncr((i + 1) + gy, gy);
		ans += (V2 - V1);
	}
	ans = (ans + mod * mod) % mod;
	cout << ans << endl;
	return 0;
}

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

int main(){
  double n,m,d;
  int D=d;
  cin>>n>>m>>d;
  int k=2*(n-d);
  if(d==0)k/=2;
  cout<<fixed<<setprecision(12)<<(m-1)*k/n/n<<endl;
}


Measured memory_bytes: 256
cards = []
3.times do |i|
  cards << gets.chomp.split(' ').map(&:to_i)
end
patterns = [cards[0], cards[1], cards[2], [cards[0][0],cards[1][0],cards[2][0]], [cards[0][1],cards[1][1],cards[2][1]], [cards[0][2],cards[1][2],cards[2][2]], [cards[0][0],cards[1][1],cards[2][2]], [cards[0][2],cards[1][1],cards[2][0]]]

time = gets.chomp.to_i
nums = []
time.times do |i|
  nums << gets.to_i
end

is_not_bingo = patterns.select { |pettern| (pettern & nums).size == 3 }.empty?

if is_not_bingo
  puts 'No'
else
  puts 'Yes'
end


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

using namespace std;

typedef string::const_iterator State;
class ParseError {};

map<char, int> mp, mp2;
State b;

int f(int a, int b) {
	if(a == 0) return 1;
	if(b == 1) return 1;
	return 0;
}

int ch(State& begin) {
	if(!islower(*begin) && !isupper(*begin)) {cout << *begin; assert(false);}
	int ret;
	if(*begin == 'T') ret = 1;
	else if(*begin == 'F') ret = 0;
	else ret = mp2[*begin];
	begin++;
	return ret;
}

int fomula(State& begin) {
	//cout << *begin << endl;
	if(islower(*begin) || isupper(*begin)) {return ch(begin);}
	else if(*begin == '-') {begin++; return !fomula(begin);}
	else if(*begin == '(') {
		begin++;
		int ret1 = fomula(begin);
		char op = *begin;
		begin++;
		int ret2 = fomula(begin);
		begin++;
		int ret;
		if(op == '*') {
			ret = (ret1 == 1 && ret2 == 1) ? 1 : 0;
		} else if(op == '+') {
			ret = max(ret1, ret2);
		} else if(op == '>') {
			ret = (ret1 == 1 && ret2 == 0) ? 0 : 1;
		} 
		return ret;
	}
}

int equation(State& begin) {
	int ret = fomula(begin), ret2;
	if(*begin == '=') begin++, ret2 = fomula(begin);
	//cout << "ret:" << ret << " ret2:" << ret2 << endl;
	if(ret == ret2) return 1;
	return 0;
}

int a[20];
int main() {
	while(true) {
		string t;
		cin >> t;
		if(t == "#") break;
		string s;
		for(int i=0; i<t.size(); ++i) {
			if(t[i] != '>') s += t[i];
			else s[s.size()-1] = '>';
		}
		//cout << s << endl;
		int idx = 0;
		mp.clear();
		mp2.clear();
		for(int i=0; i<s.size(); ++i) {
			if(islower(s[i]) && mp.find(s[i]) == mp.end()) {
				mp[s[i]] = idx;
				a[idx++] = s[i];
			}
		}
		/*for(auto i: mp) {
			cout << i.first << " " << i.second << endl;
		}*/
	
		bool flag = true;
		for(int i=0; i<(1<<idx); ++i) {
			//cout << "i:" << i << endl;
			for(int j=0; j<idx; ++j) {
				if(i >> j & 1) mp2[a[j]] = 1;
				else mp2[a[j]] = 0;
			}
			//for(auto j: mp2) cout << j.first << " " << j.second << endl;
			State begin = s.begin();
			b = s.begin();
			if(!equation(begin)) flag = false;
			//cout << flag << endl;
		}
		if(flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int mod = 1000000007;
int main() {
	int h, w;
    cin >> h >> w;
    string arr[h+1];
    dp[0][0] = 1;
    for(int i = 0; i < h; i++){
        cin >> arr[i];
    }
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(i != h-1 and arr[i+1][j] != '#')dp[i+1][j] += dp[i][j], dp[i+1][j] %= mod;
            if(j != w-1 && arr[i][j+1] != '#')dp[i][j+1] += dp[i][j], dp[i][j+1] %= mod; 
        }
    }
    cout << dp[h-1][w-1];
}

Measured memory_bytes: 5248
#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cctype>
using namespace std;
int main(){
  string s;
  bool a=false,b=false,c=false,d=false;
  cin >> s;
  if( s.size() >= 6 ) a = true;
  for(int i=0;i<s.size();i++){
    if(isdigit(s[i])) b = true;
    if(islower(s[i])) c = true;
    if(isupper(s[i])) d = true;
  }
  cout << ( a&&b&&c&&d ? "VALID" : "INVALID" ) << endl;
}

Measured memory_bytes: 1180
import sys


n = int(input())
c_now = [0, 0, 0]
for i in range(n):
    txy = list(map(int, input().split()))
    t = txy[0] - c_now[0]
    dis = abs(txy[1] - c_now[1]) + abs(txy[2] - c_now[2])
    if t < dis or (t - dis) % 2 != 0:
        print("No")
        sys.exit()
    c_now = txy
print("Yes")


Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
 
using namespace std;

#define mod 1000000007


int main()
{
    int n;
    cin >> n;
    long long int t[1001], a[1001];
    for(int i = 0; i < n; i++){
        cin >> t[i] >> a[i];
    }
    long long int takahashi = t[0], aoki = a[0];
    for(int i = 1; i < n; i++){
        if(takahashi % t[i] != 0) takahashi += t[i] - (takahashi % t[i]);
        if(aoki % a[i] != 0) aoki += a[i] - (aoki % a[i]);
        if(takahashi / t[i] > aoki / a[i]){
            aoki = (takahashi / t[i]) * a[i];
        } else if(takahashi / t[i] < aoki / a[i]){
            takahashi = (aoki / a[i]) * t[i];
        }
    }
    cout << takahashi + aoki << endl;
    return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define vvll vector <vll>
#define vsi vector <si>
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 4000+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;
int R[MAXN],B[MAXN],G[MAXN];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("a.in","r",stdin);
    #endif
    int n;
    cin>>n;
    string s;
    cin>>s;
    int r=0,b=0,g=0;
    for (int i=0;i<n;i++)
    {
        if (s[i]=='R')
            r++;
        if (s[i]=='B')
            b++;
        if (s[i]=='G')
            g++;
        R[i+1]=r;
        B[i+1]=b;
        G[i+1]=g;
    }
    ll ans=0;
    for (int i=0;i<n;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            if (s[i]==s[j])
                continue;
            if (s[i]!='B'&&s[j]!='B')
            {
                ans+=B[n]-B[j];
                if (j+j-i<n&&s[2*j-i]=='B')
                    ans--;
            }
            if (s[i]!='G'&&s[j]!='G')
            {
                ans+=G[n]-G[j];
                if (j+j-i<n&&s[2*j-i]=='G')
                    ans--;
            }
            if (s[i]!='R'&&s[j]!='R')
            {
                ans+=R[n]-R[j];
                if (j+j-i<n&&s[2*j-i]=='R')
                    ans--;
            }

        }
    }
    cout<<ans;




}


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

int main(){
    ll n,m,h[100005],memo[100005],x,y,ans=0;
    cin >> n >> m;
    rep(i,n){
        cin >> h[i];
        memo[i]=0;
    }
    rep(i,m){
        cin >> x >>y;
        if(h[x-1]>=h[y-1]){
            memo[y-1]=1;
        }
        if(h[y-1]>=h[x-1]){
            memo[x-1]=1;
        }
    }
    rep(i,n){
        if(memo[i]==0){
            ans++;
        }
    }
    cout << ans;
}

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

using namespace std;

typedef long long int ll;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

vector <ll> cnt(35);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    ll N, M;
    cin >> N >> M;

    for(ll i=0; i<N; i++)
    {
        ll K;
        cin >> K;

        for(ll j=0; j<K; j++)
        {
            ll a;
            cin >> a;
            cnt[a]++;
        }
    }

    ll ans = 0;

    for(ll i=1; i<=M; i++)
    {
        if(cnt[i]==N)
        {
            ans++;
        }
    }

    cout << ans << endl;



    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<stdio.h>
#include<vector>
using namespace std;

int main(){
  int p,q,r;
  cin >> p >> q >> r;

  int AB = p + q;
  int BC = q + r;
  int CA = r + p;

  int ans = 0;
  if(AB < BC){
    ans = AB;
  }else{
    ans =  BC;
  }
  if(ans > CA){
    ans = CA;
  }
  cout << ans << endl;

}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include <tuple>

using namespace std;
#define ll long long
#define ld long double
#define int long long
#define all(a) (a).begin(),(a).end()
#define EPS (1e-13)
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define mkp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define ssp(i,n) (i==n-1?"\n":" ")
#define tpop(p) p.top();p.pop()
const int mod = 1e9 + 7;
const int Mod = 998244353;
const ll Inf = 3 * 1e18;
const int inf = 15 * 1e8;
ll read() {
	ll u, k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}
ll bitcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
/*const int fn_ = 2000000;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++) {
			fact_[i] = fact_[i - 1] * i % Mod;
			comp_[i] = mod_pow(fact_[i], Mod - 2, Mod);
		}
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//---------------------------------------------------
signed main() {
	int n;
	cin >> n;
	int t = 1, ans = 0;
	while (t <= n) {
		for (int i = t; i <= n && i < t * 10; i++) {
			ans++;
		}
		t *= 100;
	}
	cout << ans << endl;
}

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

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

#define ll long long int

using namespace std;

int main() {
    ll n, x;
    cin >> n;
    cin >> x;
    vector<ll> M(n);
    ll cheap = 1e9;
    ll sum = 0;
    for (auto & m : M ) {
        cin >> m;
        cheap = min(cheap, m);
        sum += m;
    }

    cout << (n + (x - sum)/cheap) << endl;
}


Measured memory_bytes: 3600
#template
def inputlist(): return [int(k) for k in input().split()]
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)
#10->n(sinhou)
def len_check(k,n):
    if len(k) == n:
        return k
    else:
        for _ in range(n-len(k)):
            k = '0'+k
        return k
#template
N,M,X = inputlist()
li = [0]*N
cost = 10**9
for i in range(N):
    li[i] = inputlist()
for k in range(2**N):
    ans = [0]*M
    k = len_check(base10to(k,2),N)
    lis = []
    tmp = 0
    count = 0
    for i in range(N):
        if k[i] == '1':
            lis.append(li[i])
    n = len(lis)
    for i in range(n):
        tmp += lis[i][0]
        alg = lis[i][1:]
        for j in range(M):
            ans[j] += alg[j]
    for i in range(M):
        if ans[i] >= X:
            count+=1
    if count == M:
        cost = min(cost,tmp)

if cost == 10**9:
    print(-1)
else:
    print(cost)

Measured memory_bytes: 71436