akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define INF 1000000000000000
#define fi first
#define se second
#define all(v) v.begin(),v.end()
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
#define pb push_back
struct edge{int to,cost;};
typedef pair<int,int> P;
int n,m,r,d[111111];
vector<edge>v[111111];
void dijkstra(int x){
	fill(d,d+n,INF);
	d[x]=0;
	priority_queue<P,vector<P>,greater<P>>q;
	q.push({x,0});
	while(!q.empty()){
		P p=q.top();
		q.pop();
		for(edge e:v[p.first]){
			if(d[e.to]>d[p.first]+e.cost){
				d[e.to]=d[p.first]+e.cost;
				q.push({e.to,d[e.to]});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>r;
	rep(i,m){
		int a,b,c;
		cin>>a>>b>>c;
		v[a].pb({b,c});
	}
	dijkstra(r);
	rep(i,n){
		if(d[i]==INF)puts("INF");
		else cout<<d[i]<<endl;
	}
	return 0;
}



Measured memory_bytes: 34084
#include <stdio.h>
#include <stdlib.h>

int asc(const void *a, const void *b){
  if(*(long *)a > *(long *)b){
    return 1;
  }else if(*(long *)a == *(long *)b){
    asc(a+1, b+1);
  }else{
    return -1;
  }
}

int main(void){
	int i, j, k;

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

	long pos[50][2] = {};
	for(i = 0; i < n; i++){
		scanf("%ld%ld", &pos[i][0], &pos[i][1]);
	}

	qsort(pos, n, sizeof(long)*2, asc);

	long dif[2500][2] = {};
	for(i = 0; i < n-1; i++){
		for(j = i+1; j < n; j++){
			for(k = 0; ; k++){
				if(dif[k][0] == 0 && dif[k][1] == 0){
					dif[k][0] = pos[j][0]-pos[i][0];
					dif[k][1] = pos[j][1]-pos[i][1];
					break;
				}
			}
		}
	}

	int ans = 0, cnt = 0;
	for(i = 0; ; i++){
		if(dif[i][0] == 0 && dif[i][1] == 0) break;
		cnt = 0;
		for(j = i+1; ;j++){
			if(dif[j][0] == 0 && dif[j][1] == 0) break;
			if(dif[j][0] == dif[i][0] && dif[j][1] == dif[i][1]) cnt++;
		}
		if(cnt > ans) ans = cnt;
	}

	if(n == 1) printf("1\n");
	else printf("%d\n",n-ans-1);

	return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		// ArrayList???????????????
		ArrayList<Integer> list = new ArrayList<Integer>();

		// Integer????????°??????????????????
		list.add(Integer.valueOf(scanner.nextInt()));
		list.add(Integer.valueOf(scanner.nextInt()));
		list.add(Integer.valueOf(scanner.nextInt()));

		// ????????§???????????????
		Collections.sort(list);

		System.out.println(list.get(0) + " " + list.get(1) + " " + list.get(2));

	}
}

Measured memory_bytes: 17164
// AtCoder Grand Contest 011
// D - Half Reflector

#include <cstdio>
#define MAX_N 200000
using namespace std;
typedef long long int ll;


int N;
ll K;
char ans[MAX_N + 1];

int main() {

  char c;
  int inv;

  scanf("%d%lld", &N, &K);
  scanf("%*c");
  ans[N + 1] = '\0';

  inv = 0;
  int j = 0;
  for (int i = 0; i < N; i++) {
    scanf("%c", &c);
    if ((c - 'A' + i) % 2 == 0) {
      inv++;
    }
    if ((ll)inv + i >= K) {
      ans[j] = ((c - 'A') + (i - j)) % 2 + 'A';
      if (j == 0 && K == (ll)inv + i) {
        ans[j] = 'B';
      }
      j++;
    }
  }
  if (j == 0 && N % 2 == 1) {
    ans[0] = (inv + K + 1) % 2 + 'A';
    j++;
  }
  for (; j < N; j++) {
    ans[j] = (N - j + 1) % 2 + 'A';
  }
  printf("%s\n", ans);

  return 0;

}




Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define ANS cout << ans << endl
#define RETURN(x)    \
  cout << x << endl; \
  return 0
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

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

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll 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(ret);
  return (ret);
}

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

signed main() {
  init();
  vll C(9);
  rep(i, 9) cin >> C[i];
  ll a = C[0] + C[1] + C[2];
  ll b = C[3] + C[4] + C[5];
  ll c = C[6] + C[7] + C[8];

  if (a % 3 == b % 3 && b % 3 == c % 3) {
  } else {
    COUT("No");
    return 0;
  }

  ll aa = C[0] + C[3] + C[6];
  ll bb = C[1] + C[4] + C[7];
  ll cc = C[2] + C[5] + C[8];
  if (aa % 3 == bb % 3 && bb % 3 == cc % 3) {
    COUT("Yes");
  } else {
    COUT("No");
  }

  return 0;
}

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

using namespace std;

#define loop(i, n) for(int i = 0;i < int(n);i++)
#define rloop(i, n) for(int i = int(n);i >= 0;i--)
#define range(i, a, b) for(int i = int(a);i <= int(b);i++)
#define SZ(c) int(c.size())
#define ALL(c) c.begin(), c.end()
#define RALL(c) c.rbegin(), c.rend()
#define PI acos(-1)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define sfi1(v) scanf("%d",&v)
#define sfi2(v1, v2) scanf("%d %d",&v1,&v2)
#define sfi3(v1, v2, v3) scanf("%d %d %d",&v1,&v2,&v3)
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1, v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1, v2, v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
#define endl '\n'

typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
typedef long long ll;
typedef pair<int, int> pii;


int main() {

#ifndef ONLINE_JUDGE
    //freopen("in.in", "r", stdin);
    //freopen("out.in", "w", stdout);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    int n, x;
    cin >> n >> x;
    int sum = 0, cur;
    range(i, 1, n) {
        cin >> cur;
        sum += cur;
        if (sum == x) {
            cout << i + 1 << endl;
            return 0;
        } else if (sum > x) {
            cout << i << endl;
            return 0;
        }
    }

    cout << n + 1 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

    bool r = false;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        r = r || a % 2 != 0;
    }

    cout << (r ? "first" : "second") << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

string stones(vector<int> &v, int k) {
    bool dp[k + 1];  // Memory
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= k; i++) {
        for(int move : v) {
            if(move > i) continue;
            if(dp[i - move] == 0) dp[i] = 1;
        }
    }
    return (dp[k] ? "First" : "Second");
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    cout << stones(v, k) << endl;
    return 0;
}

Measured memory_bytes: 3736
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long int ll;

double dist(double a,double b,double c,double d){
	return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}

ll mod=1e9+7;

//繰り返し二乗法
ll power(ll a,ll b){
	ll res=1;
	while(b>0){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

struct perm{
private:
	int sz;
	vector<ll> p,invp;
public:
	perm(int n){
		sz=n+1;
		p.resize(sz),invp.resize(sz);
		p[0]=1;
		for(int i=1;i<=sz-1;i++){
			p[i]=p[i-1]*i%mod;
		}
		invp[sz-1]=power(p[sz-1],mod-2);
		for(int i=sz-2;i>=0;i--){
			invp[i]=invp[i+1]*(i+1)%mod;
		}
	}
	ll comb(ll x,ll y){
		if(x<y||y<0)return 0;
		return (p[x]*invp[x-y]%mod)*invp[y]%mod;
	}
};
perm p(1<<20);

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int x,y; cin >> x >> y;
	if((x+y)%3){
		cout << 0 << endl;
		return 0;
	}
	int cnt=(x+y)/3;
	x-=cnt;
	y-=cnt;
	cout << p.comb(x+y,x) << endl;
} 

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

const int INF = 1001001001;

int main(){
 int N,M;
 cin>>N>>M;
 int a[M],b[M];
 for(int i=0;i<M;i++){
     cin>>a[i]>>b[i];
 }
 vector<int>count(N);
 for(int i=0;i<M;i++){
     count[a[i]-1]++;
     count[b[i]-1]++;
 }
 for(int i=0;i<N;i++){
     cout<<count[i]<<endl;
 }
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int n, m;
	static int[][] cost = new int[101][101];
	static int[][] time = new int[101][101];
	
	public static void main(String args[]){
		while(true) {
			n = sc.nextInt();
			m = sc.nextInt();
			if (n == 0 && m == 0) break;
			for (int i = 0; i < m + 1; i++) {
				for (int j = 0; j < m + 1; j++) {
					cost[i][j] = time[i][j] = 1<<29;
				}
			}
			for (int i = 0; i < n; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				cost[a][b] = cost[b][a] = sc.nextInt();
				time[a][b] = time[b][a] = sc.nextInt();
			}
			solve();
			int k = sc.nextInt();
			for (int i = 0; i < k; i++) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				int r = sc.nextInt();
				if (r == 0) {
					System.out.println(cost[start][end]);
				} else {
					System.out.println(time[start][end]);
				}
			}
		}
	}
	
	static void solve(){
		for (int k = 0; k <= m; k++) {
			for (int i = 0; i <= m; i++) {
				for (int j = 0; j <= m; j++) {
					cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
					time[i][j] = Math.min(time[i][j], time[i][k] + time[k][j]);
				}
			}
		}
	}
}


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

using namespace std;

typedef long long ll;

const ll mod = (ll)1e9 + 7;

void solve() {
    string s;
    cin >> s;

    bool fq = (s[0] == 'A');

    int cnt = 0, pos = -1;
    for (int i = 2; i <= (int)s.size() - 2; i++) if (s[i] == 'C') cnt++, pos = i;
    bool sq = (cnt == 1);

    bool tq = true;
    for (int i = 0; i < s.size(); i++) {
        if (i != 0 && i != pos) {
            if ('A' <= s[i] && s[i] <= 'Z') {
                tq = false;
            }
        }
    }

    if (fq&&tq&&sq) {
        cout << "AC";
    } else {
        cout << "WA";
    }
}

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

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#define MP make_pair
using ll = long long;
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<vector<ll> >A(N,vector<ll>(N));
  vector<vector<ll> >B(N,vector<ll>(N));
  for(int i=0; i < N; i++)
    for(int j=0; j < N; j++){
      ll a;
      cin >> a;
      A[i][j] = a;
      B[i][j] = a;
    }


  bool exist = true;
  ll ans = 0;
  for(int k=0; k < N; k++){
    for(int i=0; i < N; i++){
      for(int j=0; j < N; j++){
	if(A[i][j] > min(A[i][j], A[i][k]+A[k][j]))
	  exist = false;
	if(A[i][j] == A[i][k] + A[k][j] && i != k && j != k)
	  B[i][j] = 0;
      }
    }
  }
  for(int i=0; i < N; i++)
    for(int j=0; j < N; j++)
      ans += B[i][j];
  if(exist)
    cout << ans/2 << endl;
  else
    cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 1664
# Your code here!
n,a,b=gets.split

def tanaka(aa)
    sum=0
    jj=0
    aa.length.times{
        sum+=aa[jj]
        
        jj+=1
        
    }
    return sum
    
end




n=n.to_i
a=a.to_i
b=b.to_i
array=gets.split.map(&:to_i)
array=array.sort.reverse

aaa=tanaka(array[0..a-1])

answer=aaa/a.to_f



p answer



kosuu=array[0..a-1].count(array[a-1])
zentai=array.count(array[a-1])


def combi (a,b)
    
    answer2=1
    s=a
    t=1
    
    b.times{
        answer2=answer2*s/t
        s=s-1
        t=t+1
        
        
    }
    
   return answer2 
end


answer3=combi(zentai,kosuu)
kkk=a-1
loop{
    if array[0]!=array[kkk]  || kkk==b-1
        break
    end
    
    answer3+=combi(zentai,kkk+2)
    
    if kkk==b-1
        break
    end
    
    kkk+=1
    
    
}

puts answer3



Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
ll C[maxn][maxn];
int main() {
    for(int i = 0 ; i <= 103 ; i++)
    {
        C[i][0] = 1;
        for(int j = 1 ; j <= i ; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    ll n, k, res = 0;
    while(cin >> n >> k) {
        res = 0;
        for(ll l = 1; l <= n; l++) {
            int ans = (l+1)/(k+1);
            for(int i = 0; i <= ans; i++) {
                ll x = l - i*k + i;
                if(x % 2 == 0) {continue;}
                res += C[x/2+1][i];
            }
        }
        cout << res << endl;
    }
}



Measured memory_bytes: 3180
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;


namespace AtCoder
{
	class Program
	{
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] str = Console.ReadLine().Split(' ');
            int[] P = new int[N];
            for (int i = 0; i < N; i++) P[i] = int.Parse(str[i]);
            int min = 1000000 ,ans = 0;
            for(int i = 0; i < N; i++)
            {
                if(P[i] < min)
                {
                    ans++;
                    min = P[i];
                }
            }
            Console.WriteLine(ans);
            Console.ReadLine();
        }
    }
    
}


Measured memory_bytes: 31068
import copy

class Solver:
    def __init__(self, _n, _k):
        self.n = _n
        self.k = _k

        self.solve()
    
    def solve(self):
        ans = 0.0

        for point in range(1, self.n + 1):
            i = 0
            while point < self.k:
                point = point * 2
                i = i + 1
            ans = ans + (1.0 / self.n) * pow((1.0 / 2), i)

        # print("{:.09f}".format(ans))
        print(ans)
def main():
    n, k = (int(i) for i in input().split())
    Solver(n, k)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define rev(v) reverse(v.begin(), v.end())
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define dab(v) for(auto i:v)cout<<i<<' '; cout << endl;
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return 1; } return 0; }
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
int gcd(int a, int b) { if (a % b == 0) { return(b); } else { return(gcd(b, a % b)); } }


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	int K;
	cin >> K;
	string str;
	cin >> str;

	if (K >= str.size()) {
		cout << str;
	}
	else {
		rep(i, K) {
			cout << str.at(i);
		}
		cout << "...";
	}

	return 0;
}


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

bool isLeapYear(int year){
    return ( year%4 == 0 && year%100 != 0 || year%400 == 0 )? true : false ;
}

int main(){
	int a,b;
	bool flag, iniFlag = true;
	
	while( cin >> a >> b , a || b ){
		flag = true;
		if( iniFlag == false ){
			cout << endl;
		}else{
			iniFlag = false;
		}	

		for(int i=a ; i<=b ; i++){
			if( isLeapYear(i) ){
				flag = false;
				cout << i << endl;
			}
		}
		if( flag ) cout << "NA" << endl;		
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

int main(){

	int N,M,D;
	cin >> N >> M >> D;

	int answer = 0;
	int Z[100];

	for(int i=0;i<M;i++){
		Z[i] = 0;
	}

	for(int i=0;i<N;i++){
		string sp;
		cin >> sp;
		int kari = 0;

		for(int j=0;j<M;j++){
			if(sp[j] == '.'){
				kari++;
				Z[j]++;

				if(j == M-1){
					if(kari >= D){
						answer += kari-D+1;
					}
				}
				if(i ==  N-1){
					if(Z[j] >= D){
						answer += Z[j]-D+1;
					}
				}
			}

			else {
				if(kari >= D){
					answer += kari-D+1;
				}
				kari = 0;
			
				if(Z[j] >= D){
					answer += Z[j]-D+1;
				}
				Z[j] = 0;
				
			}
		}
	}

	cout << answer << endl;
	return 0;
}



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

typedef long long LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

template<typename Container>
bool include(const Container& c, const typename Container::value_type& v) {
  return ( c.end() != std::find(c.begin(),c.end(),v) );
}

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  int cnt = 0;
  rep(i, N)
    cin >> S[i];

  std::sort(S.begin(), S.end());
  S.erase(std::unique(S.begin(), S.end()), S.end());

  cout << S.size() << endl;

  return 0;
}


Measured memory_bytes: 9576
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

vector<int> t(1000000);

int main() {
    int k;
    cin >> k;
    int sev = 7;
    int cnt = 0;
    while (1) {
      sev %= k;
      if (t[sev]) {
        cout << -1 << endl;
        return 0;
      }
      t[sev]++;
      cnt++;
      if (sev == 0) break;
      sev = sev*10 + 7;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 7068
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define pb push_back
#define pii pair<int64_t,int64_t>
#define mp make_pair
#define whole(v) begin(v),end(v)
#define print64_t(c,n) for(int64_t i=0;i<n;i++) cout << c[i] << " ";
#define MOD 1000000007
#define INF 0x3f3f3f3f
int64_t dp[102][100003];
int main()
{
	
   	std::ios::sync_with_stdio(false);
	cin.tie(0);
	int64_t n,W;
	cin>>n >>  W;
	int64_t wt[n],val[n];
	for(int64_t i=0;i<n;i++){
		cin >> wt[i] >> val[i];
	}
   	dp[0][0] = 0;
   	for(int64_t i=1;i<=W;i++){
   		dp[0][i] = 0;
   	}
   	for(int64_t i=1;i<=n;i++){
   		dp[i][0] =0;
   	}
   	for(int64_t i=1;i<=n;i++){
   		for(int64_t j=1;j<=W;j++){
   			dp[i][j] = dp[i-1][j];
   			if(j-wt[i-1]>=0){
   				dp[i][j] = max(dp[i][j],dp[i-1][j-wt[i-1]]+val[i-1]);
   			}
   		}
   	}
   	
   	cout << dp[n][W] ;
   	return 0;
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


int N;
int A[222222],B[222222];


signed main(){
    cin>>N;
    rep(i,N)cin>>A[i];
    rep(i,N)cin>>B[i];

    int ans=0;
    rep(i,30){
        int cnt=0;
        vint a(N),b(N);

        int x=1ll<<i;
        int y=1ll<<(i+1);

        rep(j,N){
            a[j]=A[j]%y;
            b[j]=B[j]%y;
        }
        sort(all(a));reverse(all(a));
        sort(all(b));
        int l=0,r=0;

        rep(j,N){
            while(l<N&&a[j]+b[l]<x)l++;
            while(r<N&&a[j]+b[r]<y)r++;
            cnt+=r-l;
        }
        l=0;r=0;
        rep(j,N){
            while(l<N&&a[j]+b[l]<x+y)l++;
            while(r<N&&a[j]+b[r]<y+y)r++;
            cnt+=r-l;
        }

        if(cnt&1)ans^=1ll<<i;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 6552
N = int(input())
h = list(map(int, input().split()))

ans = 0
while True:
    if h.count(0) == N:
        break
    started = False
    for i, n in enumerate(h):
        if n != 0:
            if not started:
                ans += 1
                started = True
            h[i] -= 1
        else:
            started = False
print(ans)


Measured memory_bytes: 3060
#include<stdio.h>
 int main()
 {
     double N;
     double count=0;
     double p;
     int i;
     scanf("%lf",&N);
     for(i=N;i>=1;i--)
     {
         if(i%2!=0)
            count++;
     }
     p=count/N;
     printf("%lf",p);
     return 0;


 }


Measured memory_bytes: 128
n = int(input())
W = [int(s) for s in input().split()]

k = 10e3
for i in range(len(W)-1):
    a = sum(W[:i+1])
    b = sum(W[i+1:])
    d = abs(a - b)
    if d == 0:
        k = d
        break
    else:
        if k > d:
            k = d
        else:
            pass

print(k)


Measured memory_bytes: 3060
/*
THE BEST IS YET TO COME
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define r(i,s,l) for(int i=s;i<l;i++)
#define mod 1000000007
#define INT_BITS 32
#define ld long double
#define pp pair<long long,long long>
#define ss second
#define ff first
#define N 2000005
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int main()
{
    fast();
    int x,y,z;
    cin>>x>>y>>z;
    swap(x,y);
    swap(x,z);
    cout<<x<<" "<<y<<" "<<z;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10000;
struct node{
	int l,r,p,s,deg,dep,h;
};
int n,v,l1,r1,tmp,root;
int vis[N]={0};
node tree[N];


int build(int k,int depth){
	if ((tree[k].l==-1)&&(tree[k].r==-1)) {
		tree[k].deg=0;
		tree[k].dep=depth;
		return tree[k].h=0;
	}
	else if ((tree[k].l!=-1)&&(tree[k].r!=-1)){
		tree[tree[k].l].p=k;
       	tree[tree[k].r].p=k;
		tree[tree[k].l].s=tree[k].r;
		tree[tree[k].r].s=tree[k].l;
		tree[k].deg=2;
		tree[k].dep=depth;
		return tree[k].h=max(build(tree[k].l,depth+1),build(tree[k].r,depth+1))+1;
	}
	else if (tree[k].l!=-1){
		tree[tree[k].l].p=k;

		tree[tree[k].l].s=-1;


		tree[k].deg=1;
		tree[k].dep=depth;
		return tree[k].h=build(tree[k].l,depth+1)+1;		
	}
	else if (tree[k].r!=-1){

       	tree[tree[k].r].p=k;

		tree[tree[k].r].s=-1;
		
		tree[k].deg=1;
		tree[k].dep=depth;
		return tree[k].h=build(tree[k].r,depth+1)+1;		
	}



}
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>v>>l1>>r1;
		tree[v].l=l1;
		tree[v].r=r1;
		if (tree[v].l!=-1) vis[tree[v].l]=1;
		if (tree[v].r!=-1) vis[tree[v].r]=1;
	}
	for(int i=0;i<n;i++){
		if (vis[i]==0){
			root=i;
			break;
		}
	}
	build(root,0);
	tree[root].p=-1;
	tree[root].s=-1;
	for(int i=0;i<n;i++){
		printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",i,tree[i].p,tree[i].s,tree[i].deg,tree[i].dep,tree[i].h);
		if (i==root) printf("root");
		else if(tree[i].l==-1&&tree[i].r==-1) printf("leaf");
		else printf("internal node");
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 3212
a, b, c = map(int, input().split())
# answer <=> a + 2sqrt(ab) + b < c <=> 2sqrt(ab) < c - a - b <=> 4ab < (c - a - b) ^2

if c - a - b < 0:
    print('No')
else:
    left = 4 * a * b
    right = (c - a - b) ** 2
    if left < right:
        print('Yes')
    else:
        print('No')

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

int N;

int main() {
    cin >> N;
    vector<int> L(N);
    for (int i = 0; i < N; i++) {
        cin >> L[i];
    }
    sort(L.begin(), L.end());
    long long ans = 1LL * N * (N - 1) * (N - 2) / 6;
    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            int l = L[i] + L[j];
            ans -= L.end() - lower_bound(L.begin(), L.end(), l);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
  int n;
  cin >> n;
  
  cout << (n - 2) * 180 << endl;


  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define maxn 200005
#define int long long 
using namespace std;
int n, h[maxn], b[maxn], dp[maxn], seg[maxn*4];
void modify(int l, int r, int d, int x, int val) {
	if ( x > r || x < l )	return;
	if ( l == r && l == x ) {
		seg[d] = val;
		return;
	}
	int mid = l+r>>1;
	modify(l,mid,d<<1,x,val);
	modify(mid+1,r,d<<1|1,x,val);
	seg[d] = max(seg[d<<1],seg[d<<1|1]);
}
int query(int l, int r, int d, int a, int b) {
	if ( a > r || b < l )	return 0;
	if ( a <= l && r <= b )	return seg[d];
	int mid = l+r>>1;
	return max(query(l,mid,d<<1,a,b),query(mid+1,r,d<<1|1,a,b));
}
main() {
	ios::sync_with_stdio(false);
	//   sync_with_YinHsuan(true);
	cin.tie(0);
	cin >> n;
	for ( int i=1; i<=n; ++i )	cin >> h[i];
	for ( int i=1; i<=n; ++i )	cin >> b[i];
	for ( int i=1; i<=n; ++i ) {
		int mx = query(1,n,1,1,h[i]-1);
		dp[h[i]] += mx+b[i];
		modify(1,n,1,h[i],dp[h[i]]);
	}
	cout << query(1,n,1,1,n) << '\n';
	return 0;
}


Measured memory_bytes: 11264
int main()
{
  	char u[3];
	int n,i;
  	double x,sum;
	scanf("%d",&n);
	for(i=0;i<n;++i){
		scanf("%lf %s",&x,u);
      
		if(u[0]=='J'){
			sum+=x;
			continue;
		}
      
		sum+=x*380000;
	}
	printf("%lf",sum);
  
	return 0;
}

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

int main()
{
    long h;
    cin >> h;

    int count = 0;
    for (; count < 100; count++)
    {
        if (h == 1)
        {
            break;
        }
        h = h >> 1;
    }
    long ans = 1;
    for (int i = 0; i < count + 1; i++)
    {
        ans *= 2;
    }
    cout << ans - 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <climits>

using namespace std;

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

	int n;
	cin >> n;
	vector<int> w(n);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
		sum += w[i];
	}

	int ans = INT_MAX;
	int l = 0;
	int r = sum;
	for (int i = 0; i < n; i++) {
		l += w[i];
		r -= w[i];
		ans = min(ans, abs(l - r));
	}

	cout << ans << endl;

}

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

using namespace std;

int main()
{
    string s1;
    string s2;
    string s3;
    cin >> s1;
    cin >> s2;
    cin >> s3;
    s1[0] = toupper(s1[0]);
    s2[0] = toupper(s2[0]);
    s3[0] = toupper(s3[0]);
    cout << s1[0] <<s2[0] << s3[0]<< endl;
    return 0;

}

Measured memory_bytes: 256
import numpy as np
N, D = map(int, input().split())
X = np.zeros((N,D))
for i in range(N):
  X[i][:] = list(map(int, input().split()))

n = 0
for i in range(N):
  for j in range(i+1, N):
    dist = np.linalg.norm(X[i]-X[j])
    if dist.is_integer():
      n += 1

print(n)

Measured memory_bytes: 21616
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        
        if(c >= a && c <= b)
        System.out.println("Yes");
        else
        System.out.println("No");
    }
}


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

int main() {
	long long N;
	cin >> N;
	vector <long long> an (N+1);
	vector <long long> bn (N);
	
	for (int i=0;i<N+1;i++){
		cin >> an.at(i);
	}
	
	for (int i=0;i<N;i++){
		cin  >> bn.at(i);
	}
	
	long long count=0;
	long long q =0;
	
	if (an.at(0)<=bn.at(0)){
			count = count +an.at(0);
			q= bn.at(0)-an.at(0);
		}
		
		else if (bn.at(0)<an.at(0)){
			count = count +bn.at(0);
			q= 0;
		}
		
	for (int i=1; i<N;i++){
		
		if (q>=an.at(i)){
			count = count +an.at(i);
			q = bn.at(i);
		}
		
		else if (q< an.at(i) && bn.at(i)+q >= an.at(i)){
			count = count + an.at(i);
			q = bn.at(i)+q-an.at(i);
		}
		
		else if(bn.at(i)+q<an.at(i)){
			count = count + bn.at(i)+q;
			q=0;
		}
	}
	
	count = count + min(q,an.at(N));
	
	cout << count << endl;
	
	
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int INFTY = (1 << 21); // 2097152
// const ll INFTY = (1LL << 60);
const ll MD = 1000000007LL;
// fprintf(stderr, "%d %lld \n", x, xll);


int N;
int main() {
	string S;
	cin >> S;
	int ret = 0;
	rep(i, S.length()){
		if(i % 2 == 0 && S[i] == 'g'){ ret += 0; }
		if(i % 2 == 0 && S[i] == 'p'){ ret += -1; }
		if(i % 2 == 1 && S[i] == 'g'){ ret += 1;}
		if(i % 2 == 1 && S[i] == 'p'){ ret += 0;}
	}
	cout << ret << endl;
}

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

//{{{
/********************************************************************/
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef queue<int> qi;
typedef stack<int> si;
typedef deque<int> dqi;

#define reps(i, a, b) for (int i = a; i < b; ++i)
#define rep(i, n) reps(i, 0, n)
#define REPS(i, a, b) reps(i, a, b)
#define REP(i, n) rep(i, n)
#define deps(i, a, b) for (int i = a; i >= b; --i)
#define dep(i, n) deps(i, n, 0)
#define DEPS(i, a, b) deps(i, a, b)
#define DEP(i, n) dep(i, n)

#define pf push_front
#define pb push_back
#define mp make_pair
#define fst first
#define FST fst
#define sec second
#define SEC sec
#define sz(obj) ((int)(obj).size())
#define all(v) (v).begin(), (v).end()
#define ALL(v) all(v)
#define endl '\n'

const int INF = 999999999;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

inline bool inside(int y, int x, int H, int W) { return y >= 0 && x >= 0 && y < H && x < W; }
inline int in() { int x; std::cin >> x; return x; }
template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << '\n';
}
template <typename T> void print(T x) { std::cout << x << '\n'; }

/****************************************************************/
//}}}

signed main()
{
  int n, m;
  long long int ans = 0;
  cin >> n >> m;

  if (abs(n - m) >= 2);
  else if (abs(n - m) == 1) {
    ans = 1;
    for (int i = 0; i < n; i++) ans = (ans * (i + 1)) % MOD;
    for (int i = 0; i < m; i++) ans = (ans * (i + 1)) % MOD;
  }
  else {
    ans = 1;
    for (int i = 0; i < n; i++) ans = (ans * (i + 1)) % MOD;
    for (int i = 0; i < m; i++) ans = (ans * (i + 1)) % MOD;
    ans = ans * 2 % MOD;
  }

  cout << ans << endl;

  return (0);
}

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

string mr(char c,int n){
	string s = "";
	for(int i =0;i<n;i++)
	{
		s += c;
	}
	return s;
}

int main() {
	int sx,sy,tx,ty;
	cin >> sx >> sy >> tx >> ty;
	int x = tx - sx,y = ty - sy;
	string kai = "";
	kai += mr('U',y);
	kai += mr('R',x);
	kai += mr('D',y);
	kai += mr('L',x+1);
	kai += mr('U',y+1);
	kai += mr('R',x+1);
	kai += 'D';
	kai += 'R';
	kai += mr('D',y+1);
	kai += mr('L',x+1);
	kai += 'U';
    cout << kai << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main(void){
  int i,j,n,m,cn;
  char c,s[5]={'S','H','C','D','\0'};
  static int card[4][13];
  scanf("%d\n",&n);
 
  for(i=0;i<n;i++){
    scanf("%c %d\n",&c,&m);
    for(j=0;j<4;j++)
      if(s[j]==c)
        card[j][m-1]=1;
  }
   
  for(i=0;i<4;i++)
    for(j=0;j<13;j++)
      if(card[i][j]==0)
        printf("%c %d\n",s[i],j+1);
 
  return 0;
}


Measured memory_bytes: 2044
#include<iostream>
    #include<vector>
    #include<algorithm>
     
    using namespace std;
     
    int main(){
      int n;
      cin >> n;
      vector<long long> a(n),sa(n+1);
      long long i,j;
      for(i = 0;i < n;i++) cin >> a[i];
      sa[0] = 0;
      for(i = 0;i < n;i++) sa[i+1] = sa[i] + a[i];
      sort(sa.begin(),sa.end());
      long long ans = 0;
      for(i = 0,j = 0;i < n;i++){
        if(sa[i] == sa[i+1]){
          j++;
        }
        else{
          ans += j*(j+1)/2;
          j = 0;
        }
      }
      ans += j*(j+1)/2;
      cout << ans << endl;
    }

Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793
const int INF = 100000000;
int dx[] = {0,1,-1,0,1,-1,1,-1};
int dy[] = {1,0,0,-1,1,-1,-1,1};

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << a * b / 2 << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String A = scan.next();
		String B = scan.next();
		String answer = null;
 
		if(A.equals("1") && B.equals("2")) {
			answer = "3";
		} else if (A.equals("1") && B.equals("3")) {
			answer = "2";
		} else if (A.equals("2") && B.equals("1")) {
			answer = "3";
		} else if (A.equals("2") && B.equals("3")) {
			answer = "1";
		} else if (A.equals("3") && B.equals("1")) {
			answer = "2";
		} else if (A.equals("3") && B.equals("2")) {
			answer = "1";
		}
		System.out.println(answer);
	}
}

Measured memory_bytes: 21716
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

string s;
ll n, a[26];

int main(){
	cin>>s;
	n = s.size();
	ll pa = 0;

	rep(i, n) a[s[i]-'a']++;
	rep(i, 26) pa += a[i]*(a[i]+1)/2;
	cout<<n*(n+1)/2+1-pa<<endl;
	return 0;
}


Measured memory_bytes: 640
//! 尺卂乃卂.卂ﾌ乇乇ㄒ
#include<bits/stdc++.h>
//#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
//Using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Ordered_set;

#define ll              long long
#define int             long long
#define ld             long double
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define vii             vector<vi>
#define vip            vector<pii>
#define mii             map<int,int>
#define mip             map<pair<int,int>,int>
#define mic             map<char,int> 
#define all(v)          v.begin(),v.end()  
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define lb(x)           (x&(-x))
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define itr(it,v)          for(auto it:v)
#define show(arr,n)     for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<"\n";
#define fi(i,n)         for(int i=0;i<n;i++)
#define fir(i,k,n)       for(int i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ff               first 
#define ss               second
#define deb(x) cout << #x << "=" << x << endl
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define check(x) (x && cout<<"Yes\n")||(cout<<"No\n");
#define fin(s)          freopen(s,"r",stdin);  
#define fout(s)         freopen(s,"w",stdout);

const ld pi = 3.141592653589793238462643383279502884;
const int xd[]={-1,0,1,0};
const int yd[]={0,-1,0,1};
int XX[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int YY[] = { -1, 0,  1, -1, 1, -1, 0, 1 };

int expo(int a,int b,int m);
int mmi(int a,int m);
void ipgraph(int m);

const int N=5*(1e5)+10;
vii adj(N);
int a[N];

void  solve(){

}
int32_t main()
{
    FIO
    int n,m; cin>>n>>m;
    string s[n];
    fi(i,n) cin>>s[i];
    int dp[n][m];
    fi(i,n) fi(j,m) dp[i][j]=0;
    if(s[0][0]=='.')
    dp[0][0]=1;
    fi(i,n){
        fi(j,m){
            if(s[i][j]=='.'){
                if(i-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
                if(j-1>=0) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
            }
        }
    }
    cout<<dp[n-1][m-1]<<"\n";
    return 0;

}

void ipgraph(int m){
    int i, u, v;
    while(m--){
          cin>>u>>v;
         u--, v--;
    adj[u].pb(v);
    adj[v].pb(u);
    }
}
int expo(int a,int b,int m){
    if(b==0) return 1;
    if(b==1) return a;
    int val=(expo(a,b/2,m)*expo(a,b/2,m))%m;
    if(b & 1) return (val*a)%m;
    else return val;
}
int mmi(int a,int m){
    return expo(a,m-2,m);
}

Measured memory_bytes: 20864
N,M,Q = map(int,input().split())
ABCD = [list(map(int,input().split())) for _ in range (Q)]
import sys
sys.setrecursionlimit(10**9)
Alist = []
def dfs(v):
    if len(v)==N:
        Alist.append(v)
        return 
    for t in range(v[-1],M+1):
        dfs(v+[t])
dfs([1])

ans = 0
for A in Alist:
    res = 0
    for a,b,c,d in ABCD:
        if A[b-1]-A[a-1]==c:
            res += d
    ans = max(ans,res)
print(ans)

Measured memory_bytes: 16272
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};


int main() {
    ll D;
    cin >> D;
    vl c(26);
    rep(i,26){
        cin >> c[i];
    }
    ll s[D][26];
    rep(i,D){
        rep(j,26){
            cin >> s[i][j];
        }
    }
    vl latest_t(26,0);
    ll k=0;
    FOR(i,1,D+1){
        vl nt=latest_t;
        ll nk=k;
        ll MX=-INF;
        ll ans;
        rep(j,26){
            nt=latest_t;
            nk=k;
            nk+=s[-1+i][j];
            nt[j]=i;
            rep(l,26){
                nk-=c[l]*(i-nt[l]);
            }
            if(nk>MX){
                MX=nk;
                ans=j;
            }
            if(j==25){
                k=MX;
            }
        }
        cout << ans+1 << endl;
        latest_t[ans]=i;
        //cout << k << endl;
    }
}


Measured memory_bytes: 3712
var
	K:Longint;
	L,R,M:int64;
function check(T:int64):Longint;
var
	dp:Array[1..15,0..1,0..1,0..9]of Longint;
	S:String;
	i,j,k,l,nj,lim,sum,z,nz:Longint;
begin
	Str(T,S);
	for i:=1 to length(S)+1 do for j:=0 to 1 do for z:=0 to 1 do for k:=0 to 9 do dp[i,j,z,k]:=0;
	dp[1,0,1,0]:=1;
	for i:=1 to length(S) do begin
		for j:=0 to 1 do begin
			if j=0 then lim:=ord(S[i])-48 else lim:=9;
			for z:=0 to 1 do for k:=0 to 9 do begin
				for l:=0 to lim do begin
					if(z<>1)and((k<l-1)or(l<k-1))then continue;
					nj:=j;
					if l<lim then nj:=1;
					nz:=0;
					if(z=1)and(l=0)then nz:=1;
					inc(dp[i+1,nj,nz,l],dp[i,j,z,k]);
				end;
			end;
		end;
	end;
	sum:=0;
	for k:=0 to 9 do for i:=0 to 1 do begin
		inc(sum,dp[length(S)+1,i,0,k]);
	end;
	check:=sum;
end;
begin
	read(K);
	L:=0;
	R:=3234566667;
	while R-L>1 do begin
		M:=(L+R)div 2;
		if check(M)>=K then R:=M else L:=M;
	end;
	writeln(R);
end.


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

ll cal(ll b, ll N)
{
  ll ret = 0;
  while (N > 0) {
    ret += (N % b);
    N /= b;
  }
  return ret;
}

int main()
{
  ll N, S; scanf("%lld %lld", &N, &S);

  if (N == S) {
    printf("%lld\n", N + 1);
    return 0;
  }
  for (ll b = 2; b * b <= N; ++b) {
    if (cal(b, N) == S) {
      printf("%lld\n", b);
      return 0;
    }
  }

  ll val = N - S;
  ll ans = LLINF;
  for (ll q = 1; q * q <= val; ++q) {
    if (val % q != 0) { continue; }
    ll b = val / q + 1;
    if (b > sqrt(N) and cal(b, N) == S) {
      ans = min(ans, b);
    }
  }
  printf("%lld\n", ans == LLINF ? -1 : ans);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
	string c;
	while (cin >> c&&c != "0") {
		int a=0, b=0;
		for (int i = 1; i < c.length(); i++) {
			if (c[i] == 'A')
				a++;
			else
				b++;
		}
		if (a  > b) a++;
		else if (b  > a) b++;
		cout << a << " " << b << endl;
	}
}

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

using mint = modint1000000007;
// using mint = modint998244353;

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << '\n'; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) std::cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << '\n';
}

void solve() {
    Int n;
    cin >> n;
    dsu d(n);
    Int q;
    cin >> q;
    vector<tuple<Int, Int, Int>> v(q);
    for (Int i = 0; i < q; i++) {
        Int t, a, b;
        cin >> t >> a >> b;
        v[i] = tie(t, a, b);
    }
    for (Int i = 0; i < q; i++) {
        Int t, a, b;
        tie(t, a, b) = v[i];
        if (t == 0) {
            d.merge(a, b);
        }
        if (t == 1) {
            print(d.same(a, b));
        }
    }
}

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


Measured memory_bytes: 8236
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main()
{
    let (n, m) = get!(usize, usize);
    let mut es = Vec::new();
    for _ in 0..m {
        let (a, b, c) = get!(usize, usize, i64);
        es.push((a-1, b-1, c));
    }

    let mut ds = vec![i64::min_value()/3; n];
    ds[0] = 0;
    for _ in 0..n {
        for &(a, b, c) in es.iter() {
            if ds[b] < ds[a] + c {
                ds[b] = ds[a] + c;
            }
        }
    }
    let d = ds[n-1];
    for _ in 0..n {
        for &(a, b, c) in es.iter() {
            if ds[b] < ds[a] + c {
                ds[b] = ds[a] + c;
            }
        }
    }
    if d == ds[n-1] {
        println!("{}", d);
    } else {
        println!("inf");
    }
}

Measured memory_bytes: 4352
import sys
input = sys.stdin.readline
import numpy as np

W, H, N = map(int, input().split())

inputs = [list(map(int, input().split())) for i in range(N)]

maps = np.zeros([H+1, W+1])

for this_order in inputs:
    if this_order[2] == 1:
        maps[0:, :this_order[0]+1] = 1
    elif this_order[2] == 2:
        maps[0:, this_order[0]+1:] = 1
    elif this_order[2] == 3:
        maps[:this_order[1]+1] = [1] * (W+1)
    else:
        maps[this_order[1]+1:] = [1] * (W+1)

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if maps[i][j] == 0:
            ans += 1
print(ans)

Measured memory_bytes: 12520