akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
typedef int long long ll;

using namespace std;
int main(){
    
    int n;
    while(cin>>n){
        int ans=0;
        rep(i,10){
            rep(j,10){
                rep(k,10){
                    rep(l,10){
                        if(i+j+k+l==n){
                            ans++;
                        }
                    }
                }
            }
        }
        
        
        cout<<ans<<endl;
        
        
        
    }
    
    return 0;
}



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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second

typedef long long ll;
typedef pair<ll,int> P;
typedef pair<P,P> PP;

struct edge {
	int to,cost;
	edge(int t,int c):to(t),cost(c) {}
};

int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int ddx[]={1,1,1,0,-1,-1,-1,0},ddy[]={1,0,-1,-1,-1,0,1,1};

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

ll h,w;
ll g[11][11],a[200][200];

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

	cin>>h>>w;
	REP(i,10) {
		REP(j,10) {
			cin>>g[i][j];
		}
	}

	REP(i,h) REP(j,w) cin>>a[i][j];

	REP(k,10) {
		REP(i,10) {
			REP(j,10) {
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
			}
		}
	}

	ll sum=0;
	REP(i,h) {
		REP(j,w) {
			if(a[i][j]==-1) continue;
			sum+=g[a[i][j]][1];
		}
	}

	cout<<sum<<endl;

	return 0;
}


Measured memory_bytes: 640
import sys

sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
graph = [set([]) for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a - 1].add(b - 1)
    graph[b - 1].add(a - 1)


def dfs(graph, visited, v):
    if all(visited):
        return 1

    cnt = 0
    for u in graph[v]:
        if visited[u]:
            continue
        visited[u] = True
        cnt += dfs(graph, visited, u)
        visited[u] = False

    return cnt


visited = [False] * len(graph)
visited[0] = True
ans = dfs(graph, visited, 0)
print(ans)


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

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

    // 累積和と連想配列
    vector<ll> s(n+1);
    map<ll, ll> nums;
    rep(i, n) s[i+1] = s[i] + a[i];
    rep(i, n+1) nums[s[i]]++;

    // 集計処理
    ll ans = 0;
    for (auto it : nums) {
        ll num = it.second; // it.first が it.second 個ある
        ans += num * (num - 1) / 2; //組み合わせ計算 nC2 通り選ぶ。 1C2 = 0 となる。 
    }

    cout << ans << endl;


    return 0;
}

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

int main() {
	int a, b;
	cin >> a >> b;
	int m=-1000;
//	m = max(a, b);
	m = max(m, a - b);
	m = max(m, a + b);
	m = max(m, a * b);
	cout << m << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String[] line;
      MyList list = new MyList();

      for(int i=0; i<n; i++) {
        line = br.readLine().split(" ");
        switch( line[0] ) {
          case "insert" :
            list.insertFirst( Integer.parseInt(line[1]) );
            break;
          case "deleteFirst" :
            list.deleteFirst();
            break;
          case "deleteLast" :
            list.deleteLast();
            break;
          case "delete" :
            list.delete( Integer.parseInt(line[1]) );
            break;
        }
      }

      System.out.println ( list.getAllElements() );
    }
  }
}

class Node {
  Node next,prev;
  int key;

  public Node(int key) {
    this.key = key;
  }
}

class MyList {
  Node nil;
  Node current;
  int size;

  public MyList() {
    nil = new Node(0);
    nil.next = nil.prev = nil;
    size = 0;
  }

  public String getAllElements() {
    StringBuilder buf = new StringBuilder(size*3);

    if(size > 0){
      current = nil.next;
      for(int i=0; i<size; i++){
        buf.append(current.key).append(" ");
        current = current.next;
      }
    }
    buf.setLength(buf.length()-1);

    return buf.toString();
  }
  public void insertFirst(int x) {
    if(size == 0) {
      current = new Node(x);
      nil.next = current;
      nil.prev = current;
      current.prev = nil;
      current.next = nil;
      size++;
    }
    else {
      Node add = new Node(x);
      
      current.prev.next = add;
      add.prev = current.prev;

      add.next = current;
      current.prev = add;

      current = add;
      size++;
    }
  }
  public void deleteFirst() {
    nil.next = current.next;
    current.next.prev = current.prev;

    current = current.next;
    size--;
  }
  public void deleteLast() {
    current = nil.prev;

    nil.prev = current.prev;
    current.prev.next = current.next;

    current = nil.next;
    size--;
  }
  public void delete(int x) {
    Node target = findFirst(x);

    if(target == nil) current = current.next;
    else {
      current.prev.next = target.next;
      current.next.prev = target.prev;
      current = nil.next;
      size--;
    }
  }
  private Node findFirst(int x) {
    while(current != nil) {
      if(current.key == x) break;
      current = current.next;
    }

    return current;
  }
}


Measured memory_bytes: 189028
def main():
    N = int(input())
    A = [int(_) for _ in input().split()]
    B = [int(_) for _ in input().split()]
    if sum(A) < sum(B):
        print(-1)
        return
    tariruhito = []
    tarinai = 0
    output = 0
    for a, b in zip(A, B):
        if a >= b: tariruhito.append(a-b)
        else:
            output += 1
            tarinai += b - a
    tariruhito.sort(reverse=True)
    i = 0
    while tarinai > 0:
        output += 1
        tarinai = max(0, tarinai-tariruhito[i])
        i += 1
    print(output)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 18424
n_m_str=input().split()
n_m=list(map(lambda i : int(i),n_m_str))
n,m=n_m[0],n_m[1]
a=[input() for i in range(n)]
A=[]
for i in a:
    A.append(i.split())
b=[input() for i in range(m)]
Ab=[]
for i in range(n):
    Ab.append(0)
for i in range(n):
    for j in range(m):
        Ab[i]+=int(A[i][j])*int(b[j])
for i in Ab:
    print(i)


Measured memory_bytes: 6296
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int bitcount( long long a ) {
    
    int count = 0;
    for ( int i = 0; i < 10; i++ ) {
        if ( a & (1<<i) ) { count++; }
    }
    return count;
}

int main() {
    
    int N;
    cin >> N;
    vector<long long> F(N,0);
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < 10; j++ ) {
            int a;
            cin >> a;
            if ( a ) { F[i] |= 1<< j; }
        }
    }
    vector< vector<int> > P(N);
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j <= 10; j++ ) {
            int a;
            cin >> a;
            P[i].push_back(a);
        }
    }
    
    long long ans = LLONG_MIN;
    for ( long long i = 1; i < (1<<10); i++ ) {
        
        long long sum = 0;
        for ( int j = 0; j < N; j++ ) {
            sum += P[j][bitcount( i&F[j] )];
        }
        ans = max( ans, sum );
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int n,k,i;
  long long m=0,ans=0;
  cin >> n >> k;
  if (k%2==0){
    for (i=1;i<=n;i++) if (i%k==k/2) m++;
    ans+=m*m*m;
  }
  m=n/k;
  ans+=m*m*m;
  cout << ans << endl;
  return 0;
}

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

int main() {
  int N; cin >> N;
  vector<int> v(N);
  int sum = 0;  
  for (int i = 0; i < N; i++) {
    cin >> v.at(i);
    sum += v.at(i);
  }
  sort(v.begin(), v.end());
  int highs = v.back();
  int ans = sum - highs / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
#define db(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define fr(i,a,n) for(int i=a;i<=(n);++i)
#define rf(i,a,n) for(int i=a;i>=(n);--i)
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define F first
#define S second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pll pair<ll,ll>
#define _ <<" "<<
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<int,pair<int,int>> iii;
typedef vector<ii> vii;
typedef vector<iii> viii;

vvi dp;

// int words(set<string> a, int n, string s){
// 	// db2(s,n);
// 	if(n==0)
// 		if(s.length()==0)
// 			return 1;
// 		else
// 			return 0;
// 	if(dp[n][s.length()]!=-1)
// 		return dp[n][s.length()];
// 	if(a.find(s.substr(n-1))!=a.end()){
// 		dp[n][s.length()]= max(words(a,n-1,s.substr(0,n-1)),words(a,n-1,s));
// 	}
// 	else
// 		dp[n][s.length()]= words(a,n-1,s);
// 	return dp[n][s.length()];
// }

int main(){
	int t=1;
	//cin>>t;
	while(t--){
		ll n,W;
		cin>>n>>W;
		vi w(n),v(n);
		rep(i,n) cin>>w[i]>>v[i];
		// db(n);
		dp.clear();
		dp.resize(n+1,vi(W+1));
		// cout<<words(a,s.length(),s)<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=W;j++){
				if(w[i-1]<=j)
					dp[i][j]=max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]); 
				else
					dp[i][j]=dp[i-1][j];
				// cout<<dp[i][j]<<' ';
			}
			// cout<<endl;
		}
		cout<<dp[n][W]<<endl;
	}
	return 0;
}

Measured memory_bytes: 80256
"use strict";
const input = require("fs").readFileSync("/dev/stdin","UTF-8").trim();

let minDiff = 1000;
const NUM = 753;
for (let i=0;i<input.length-2; i++) {
  const num = Number(input.slice(i,i+3));
  const diff = Math.abs(num-NUM);
  if(diff < minDiff) minDiff = diff;
}

console.log(minDiff);

Measured memory_bytes: 7372
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.stdio;

void main() {
    auto K = readln.chomp.to!BigInt;

    auto F = new BigInt[](610);
    F[0] = F[1] = 1;
    foreach (i; 2..610) F[i] = F[i-1] * i;

    auto ans = new BigInt[](601);
    foreach_reverse (i; 1..601) {
        auto v = F[i+6] / F[7] / F[i-1];
        ans[i] = K / v;
        K %= v;
    }

    string anss = "";
    foreach (i; 1..601) {
        anss ~= "FESTIVA";
        foreach (j; 0..ans[i].to!long) {
            anss ~= "L";
        }
    }

    anss.writeln;
}


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

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i];
    sort(a.rbegin(), a.rend());
    if(n == 2){
        cout << a[0] << endl;
        return 0;
    }
    ll ans = a[0];
    int cnt = 1;
    int flag = 0;
    for(int i = 2; i < n; i ++){
        ans += a[cnt];
        flag++;
        if(flag == 2){
            cnt++;
            flag = 0;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4840
#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);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

vector<int> a;
vector<int> b = {3, 5, 7};
ll n;

void dfs(ll x) {
    rep(i,3) {
        ll nx = x*10 + b[i];
        if (nx > n) continue;
        a.push_back(nx);
        dfs(nx);
    }
}

bool f(int x) {
    vector<int> c(8);
    while (x > 0) {
        c[x%10]++;
        x /= 10;
    }
    bool ok = true;
    if (!c[7]) ok = false;
    if (!c[5]) ok = false;
    if (!c[3]) ok = false;
    return ok;
}

int main() {
    cin >> n;
    dfs(0);
    int ans = 0;
    for (int x : a) {
        if (f(x)) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;

    stack<char> sta;
    int count = 0;
    for(int i = 0; i < s.size(); i++)
    {
        sta.push(s[i]);
        bool flag = true;
        while(flag && sta.size() >= 2)
        {

          char c1 = sta.top();
          sta.pop();
            char c2 = sta.top();
          sta.pop();

          if(c1 != c2)
            {
                count += 2;
            }
            else
            {
                sta.push(c2);
                sta.push(c1);
                flag = false;
            }
        }
    }
    cout << count << endl;
}




Measured memory_bytes: 512
#include <stdio.h>
#include <utility>
#include <set>
typedef long long ll;

int main(void) {
  ll i, j, k, n, ans = 0;
  scanf("%lld", &n);
  ll a;
  std::set< std::pair<ll, ll> > s;
  std::set< std::pair<ll, ll> >::iterator it;
  for(i = 0; i < n; ++i) {
    scanf("%lld", &a);
    it = s.lower_bound(std::make_pair(a - 1, 1));
    if(it == s.end() || (*it).first != a - 1) {
      s.insert(std::make_pair(a, 1));
    } else {
      ll tmp = (*it).second;
      s.erase(it);
      s.insert(std::make_pair(a, tmp + 1));
    }
  }
  for(it = s.begin(); it != s.end(); ++it) {
    if(ans < (*it).second) ans = (*it).second;
  }
  printf("%lld", n - ans);
  return 0;
}

Measured memory_bytes: 12672
/*
ID: your_id_here
PROG: test
LANG: C++11
*/
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
//double pi=3.1415926535898;
//double pi=acos(-1.0);
#define scarr(a,s,e) for(int i=s;i<=int(e);i++) scanf("%d ",&a[i]);
#define prarr(a,s,e) for(int i=s;i<=int(e);i++) printf("%d ",a[i]);
#define speed      ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define rng(i,a,b) for(int i=a;i>=int(b);i--)
#define rep(i,a,b) for(int i=a;i<=int(b);++i)
#define lop(i,n)   for(int i=0;i<int(n);i++)
#define ms(x,a)    memset(x,a,sizeof(x))
#define all(x)     (x).begin(),(x).end()
#define sz(x)      int(x.size())
#define pb         push_back
#define mkp        make_pair
#define sc(x)      scanf("%d",&x)
#define scl(x)     scanf("%lld",&x)
#define pr(x)      printf("%d ",x)
#define prl(x)     printf("%lld ",x)
#define prln(x)    printf("%d\n",x)
#define prlln(x)   printf("%lld\n",x)
#define r0         return 0;
#define CC         continue;
#define scd(x)     scanf("%lf",&x)
#define prd(x)     printf("%.10f\n",x)
#define bb(x)      cerr<< x <<endl;
#define pii        pair<int,int>
#define pis        pair<int,string>
#define vi         vector<int>
#define x         first
#define y         second
//#define max(a,b) a<b?b:a __builtin_popcount;
//#define min(a,b) a<b?a:b
const ll M  = 1e9+7 ;
const int N = 100100;
//////////////////////    Hi    ^_^  hack me if you can :P

int main()
{
    //freopen("output.txt","w",stdout),freopen("input.txt","r",stdin);
    //speed;
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<(b/c)-((a)/c)+((a%c)==0);
    r0;
}

/*

freopen("output.txt","w",stdout);
freopen("input.txt","r",stdin);

ll pwmod(ll a, ll n, ll mod) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}
Wj0944296025*
http://ideone.com/KrXO2S
*/
/*
for (int i=0;i<n;i++)            Hi    ^_^  hack me if you can :P
int mx[]= {0,0,1,-1, 1,1,-1,-1};
int my[]= {1,-1,0,0, 1,-1,1,-1};
bool inside (int i,int j) {return (i>=0 && i<n && j>=0 && j<m);}

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void gcd(LL n,LL m,LL &d,LL &xx,LL &yy){
    if(!m) {d=n; xx=1; yy=0;}
    else {gcd(m,n%m,d,yy,xx); yy-=xx*(n/m);}
}

int getm(int l,int r)
{
    if(l>r)
        return N;
    if(l==r)
        return 0;
    if(l==r-1)
        return s[l] != s[r];
    if(s[l]==s[r])
        return getm(l+1,r-1);
    else
        return 1+min(getm(l+1,r),getm(l,r-1));
}

int BIT[si], a[si], n;
void update(int x, int delta)
{
    for(; x <= N; x += x&-x)
        BIT[x] += delta;
}
int query(int x)
{
    int sum = 0;
    for(; x > 0; x -= x&-x)
        sum += BIT[x];
    return sum;
}

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

*/


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n,y;
  cin>>n>>y;
  rep(i,n+1)for(j=0;i+j<=n;j++){
    int k=n-i-j;
    if(i*1000+j*5000+k*10000==y){
      cout<<k<<" "<<j<<" "<<i<<endl;
      return 0;
    }
  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;
}


Measured memory_bytes: 256
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.io.BufferedReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}
	public Main() {
		while(sc.hasNext()){
			new aoj0110().doIt();
		}
	}
	class aoj0110{
		char num[] = {'0','1','2','3','4','5','6','7','8','9'};
		void doIt() {
			String str = sc.next();
			char ctr[] = str.toCharArray();
			String a = "",b = "",c = "";
			for(int i = 0;i < 10;i++){
				a = "";b = "";c = "";
				int cnt = 0;
				for(int j = 0;j < ctr.length;j++){
					if(ctr[j] == '+')cnt++;
					else if(ctr[j] == '=')cnt++;
					else{
						if(cnt == 0){
							if(ctr[j] == 'X')a = a + num[i];
							else a = a + ctr[j];
						}else if(cnt == 1){
							if(ctr[j] == 'X')b = b + num[i];
							else b = b + ctr[j];
						}else if(cnt == 2){
							if(ctr[j] == 'X')c = c + num[i];
							else c = c + ctr[j];
						}
					}
				}
				int cnta=0,cntb=0,cntc=0;
				if(a.startsWith("0")){
					if(a.length() > 1)cnta++;
				}if(b.startsWith("0")){
					if(b.length() > 1)cntb++;
				}if(c.startsWith("0")){
					if(c.length() > 1)cntc++;
				}
				BigInteger numa = new BigInteger(a);
				BigInteger numb = new BigInteger(b);
				BigInteger numc = new BigInteger(c);
				BigInteger tashi = numa.add(numb);	
				if(cnta == 0 && cntb == 0&& cntc == 0){
					if(tashi.equals(numc)){
						System.out.println(i);
						break;
					}
				}
				if(i == 9)System.out.println("NA");
			}
		}
	}
}

Measured memory_bytes: 22640
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <bitset>
#include <queue>
#include <stack>
#define mod 998244353
#define pb(x) push_back(x)
#define N 300000
using namespace std;
int gh[300000],tot;
int a[300000],w[300000],cnt[50],dp[1<<17];
struct node
{
    int x,next,w;
}edge[310000];
void addedge(int x,int y,int w)
{
    edge[++tot].x=y;
    edge[tot].next=gh[x];
    edge[tot].w=w;
    gh[x]=tot;
}
void dfs(int x,int pre)
{
    for(int p=gh[x];p!=-1;p=edge[p].next)
        if(edge[p].x!=pre)
        {
            a[edge[p].x]=edge[p].w;
            dfs(edge[p].x,x);
        }
    for(int p=gh[x];p!=-1;p=edge[p].next)
        if(edge[p].x!=pre)w[x]^=w[edge[p].x];
    a[x]^=w[x];
    w[x]^=a[x];
}
int n;
bool belong[1<<17];
void prepare()
{
    cin>>n;
    memset(gh,255,sizeof(gh)); tot=0;
    for(int i=1;i<n;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        x++; y++;
        addedge(x,y,w);
        addedge(y,x,w);
    }
    a[1]=0;dfs(1,0);
}
void work()
{
    for(int i=0;i<1<<16;++i)dp[i]=-100;
    dp[0]=0;
    for(int i=0;i<1<<15;++i)
    {
        int tp=i,ts=1,now=0;
        for(;tp;tp>>=1,ts++)if(tp&1)now^=ts;
        if(now==0)belong[i]=1;else belong[i]=0;
    }
}
int main()
{
    prepare();

    for(int i=1;i<=n;i++)cnt[a[i]]++;
    int ans=0;
    cnt[0]=0;
    for(int i=0;i<16;++i)
    {
        ans=ans+cnt[i]/2;
        cnt[i]&=1;
    }
    for(int i=1;i<16;++i)if(cnt[i])ans++;


    work();

    int tmp=(1<<15)-1;
    for(int i=1;i<=tmp;i++)
    if(belong[i])
    {
        dp[i]=1;
        for(int j=i;j;j=(j-1)&i)
        if(belong[j])
        {
            int t;
            if (dp[i]>dp[j]+dp[i^j])t=dp[i]; else t=dp[j]+dp[i^j];
            dp[i]=t;
        }
    }
    int tt=0;
    for(int i=15;i;i--)tt=tt<<1|cnt[i];
    ans-=dp[tt];

    cout<<ans<<endl;
}

Measured memory_bytes: 11904
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <stdint.h>
#include <queue>
#include <bitset>
#include <iomanip>

using namespace std;

#define PI 3.14159265358979323846
#define INF 1e+9
#define DIV_NUM (1000000007)



int main() {

	string S, T;
	cin >> S >> T;
	int A, B;
	cin >> A >> B;
	string U;
	cin >> U;
	if (U == S) A--;
	if (U == T) B--;


	long long int N = 100000000000;
	long long ans = 0;
	for (long long i = 0; i < N; i++) {
		ans += 1;
	}

	ans *= 0;

	A = A - ans;

	cout << A << " " << B << endl;

	return 0;
}


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

typedef long long ll;
typedef pair<int, int> pii;

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

#define endl "\n"

void use_cio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
    return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
    os << "[";
    for (auto x : V) os << x << ", ";
    return os << "]";
}
//--------------------------------------------------//
int n;
int a[100010], b[100010];
vector<pii> Vp;
int main() {
    use_cio();
    cin >> n;
    rep(i, n) cin >> a[i] >> b[i];
    rep(i, n) Vp.push_back({a[i], b[i]});
    sort(all(Vp), [](pii x, pii y) { return x.first + x.second > y.first + y.second; });

    ll ans = 0;
    rep(i, n) {
        if (i & 1)
            ans -= Vp[i].second;
        else
            ans += Vp[i].first;
    }
    cout
        << ans << endl;
}


Measured memory_bytes: 2168
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

    reverse(s.begin(), s.end());

    string tmp;
    for(int i=0; i<s.length(); i++){
        if(s.substr(i, 5) == "maerd") tmp += "maerd", i += 4;
        if(s.substr(i, 5) == "esare") tmp += "esare", i += 4;
        if(s.substr(i, 6) == "resare") tmp += "resare", i += 5;
        if(s.substr(i, 7) == "remaerd") tmp += "remaerd", i += 6;
    }

    cout << (s==tmp ? "YES" : "NO" ) << endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b&&a!=c||a==b&&b!=c||b==c&&a!=b||a==c&&a!=b){cout<<"Yes"<<endl; return 0;}
    if(a==b&&a==c&&b==c||a!=b&&a!=c&&b!=c){cout<<"No"<<endl;return 0;}
    }


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

int main(){
    long long n,s;
    cin >> n >> s;
    long long mod=998244353;
    long long a[n];
    for(long long i=0;i<n;i++) cin >> a[i];
    long long dp[n+1][s+1];
    for(long long i=0;i<=n;i++){
        for(long long j=0;j<=s;j++){
            dp[i][j]=0;
        }
    }
    dp[0][0]=1;
    for(long long i=0;i<n;i++){
        for(long long j=0;j<=s;j++){
            dp[i+1][j]+=2*dp[i][j];
            dp[i+1][j]%=mod;
            if(j+a[i]<=s){
                dp[i+1][j+a[i]]+=dp[i][j];
                dp[i+1][j+a[i]]%=mod;
            }
        }
    }
    cout << dp[n][s] << endl;
}


Measured memory_bytes: 73916
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>
#include <random>
#include <utility>
#include <limits>
#include <list>

/* template start */
 
#define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()

#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  if(sizeof...(t)>0)std::cout<<" :";
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}

template<typename Num>
constexpr Num mypow(Num a, unsigned long long b) {
  if(b==0)return 1;
  if (a==0)return 0;
  Num x = 1;
  while (b > 0) {
    if(b & 1)x*=a;
    a*=a;
    b >>= 1;
  }
  return x;
}

/* template end */

using ll = long long;

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

  ll x;
  std::cin>>x;

  std::cout<<std::lcm(360,x)/x<<"\n";

  return 0;
}

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

int main() {
	int A, B;
	cin >> A >> B;
	int result = -1;
	for (int i = 1; i < 1010; i++) {
		if (int(i * 0.08) == A && int(i * 0.1) == B) {
			result = i;
			break;
		}
	}

	cout << result << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string s;
    cin >> s;
    set<char> left_st[n];
    set<char> right_st[n];
    REP(i,1,n)
    {
        for (auto itr = left_st[i-1].begin();itr != left_st[i-1].end();++itr)
        {
            left_st[i].insert(*itr);
        }
        left_st[i].insert(s[i-1]);
    }
    for (int i=n-2;i>=0;i--)
    {
        for (auto itr = right_st[i+1].begin();itr != right_st[i+1].end(); ++itr)
        {
            right_st[i].insert(*itr);
        }
        right_st[i].insert(s[i+1]);
    }
    set<string> ans;
    // cout << left_st[1].size() << endl;
    // cout << right_st[1].size() << endl;
    REP(i,1,n-1)
    {
        for (auto itr = left_st[i].begin();itr!=left_st[i].end();++itr)
        {
            // cout << i << endl;
            // cout << *itr << endl;

            for (auto litr = right_st[i].begin();litr!=right_st[i].end();++litr)
            {
                // cout << "koko" << endl;
                // string tmp_string;
                // tmp_string = *itr + s[i] + *litr;
                char tmp_char[3];
                tmp_char[0] = *itr;
                tmp_char[1] = s[i];
                tmp_char[2] = *litr;
                // cout << tmp_char[0] << tmp_char[1] << tmp_char[2] << endl;
                string tmp_string(tmp_char, 3);
                // cout << tmp_string << endl;
                // cout << tmp_string << endl;
                ans.insert(tmp_string);
            }
        }
    }
    cout << ans.size() << endl;



    // std::set<int> org[2];
    // org[0].insert(1);
    // org[0].insert(3);
    // // std::set<int> org[1](org[0]);      // コピーコンストラクタ
    // for (auto itr = org[0].begin();itr!=org[0].end();++itr)
    // {
    //     cout << *itr << endl;
    //     org[1].insert(*itr);
    // }

    // for (auto itr = org[1].begin();itr!=org[1].end();++itr)
    // {
    //     cout << *itr << endl;
    // }
}




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

using namespace std;

int main(int argc, char const* argv[])
{
	int n;
	string str;
	cin >> n;
	cin >> str;
	int min = 0;
	for(int i = 1; i < str.size(); i++){
			if(str[i] == 'E')min += 1;
	}
	int current = min;
	for(int i = 1; i < str.size(); i++){
			if(str[i - 1] == 'W')current += 1;
			if(str[i] == 'E')current -= 1;
			if(min > current)min = current;
	}
	cout << min << endl;
	return 0;
}


Measured memory_bytes: 900
import java.util.Scanner;
/**
 * Write a description of class Homework here.
 *
 * @author (your name)
 * @version (a version number or a date)
 */
public class Main
{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        int vacation = sc.nextInt();
        
        int assignments = sc.nextInt();
        
        int sum = 0;
        for(int i = 0; i < assignments; i++){
            int assign = sc.nextInt();
            
            sum += assign;
            
        }
        
        if(sum > vacation) {
            System.out.println("-1");
        } else {
            System.out.println(vacation - sum);
        }

    }
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };




void solve() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << max(a*b, c*d) << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 7676
#include "bits/stdc++.h"

#define REP(i,num) for(ll i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){T x; cin >> x; return (x);}
template<typename T=ll,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int A=in(),B=in(),C=in(),X=in(),Y=in();
	int AB1=A*X+B*Y;
	int AB2=2*C*(min(X,Y));
	if(X>Y){
		AB2+=A*(X-Y);
	}
	else{
		AB2+=B*(Y-X);
	}
	int AB3=2*C*(max(X,Y));
	out(min({AB1,AB2,AB3}));
	return 0;
}


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

#define  SZ(items) (int)items.size()
#define  CLR(a)  memset(a,0,sizeof(a))
#define  SET(a)  memset(a,-1,sizeof(a))

int dx[] = { 0,0,1,-1,-1,-1,1,1 };
int dy[] = { 1,-1,0,0,-1,1,1,-1 };

template <class T> inline T biton(T n, T pos) { return n | ((T)1 << pos); }
template <class T> inline T bitoff(T n, T pos) { return n & ~((T)1 << pos); }
template <class T> inline T ison(T n, T pos) { return (bool)(n & ((T)1 << pos)); }
template <class T> inline T gcd(T a, T b) { while (b) { a = a%b; swap(a, b); } return a; }
template <class T> inline T bigmod(T p, T e, T m) { T ret = 1; for (; e > 0; e >>= 1) { if (e & 1) ret = (ret * p) % m; p = (p * p) % m; } return (T)ret; }


int  n;
vector<int> items;

int dp[4][3009];

int recur(int i, int current) {



	if (current == n) {
		return 1;
	}

	if (current > n)
	{
		return 0;
	}

	if (i == items.size())
	{
		return false;
	}

	if (dp[i][current] != -1) {
		return dp[i][current];
	}

	long long taking=recur(i, items[i] + current);

	long long notTaking=recur(i+1, current);

	return  dp[i][current]=taking+notTaking;
}

void solve() {

	SET(dp);
	for (int i = 0; i < 3; i++) {
		int item;
		cin >> item;
		items.push_back(item);
	}

	cin >> n;

	long long res = recur(0, 0);
	cout << res << endl;
}

int main()
{

	ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(10); cout.tie(nullptr); cin.tie(nullptr);

	int t = 1;

	while (t--) {

		solve();
	}

	return 0;
}

Measured memory_bytes: 384
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	
	max := 0
	maxcnt := 0
	
	if n == 1 {
		fmt.Println(1)
		return
	}
	
	for i := n; i >= 1; i-- {
		temp := i
		cnt := 0
		for temp % 2 == 0 {
			temp /= 2
			cnt++
		}
		if maxcnt < cnt {
			max = i
			maxcnt = cnt
		}
	}
	fmt.Println(max)
}


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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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 (b<a) { a=b; return 1; } return 0; }


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

    cout << N/3 << endl;
}


Measured memory_bytes: 256
from itertools import accumulate
import sys
from heapq import heappush, heappop


def main():
    input = sys.stdin.readline
    S = input()
    a = int(S[:2])
    b = int(S[2:])
    if (a > 12 or a == 0) and 1 <= b <= 12:
        print('YYMM')
    elif 1 <= a <= 12 and (b > 12 or b == 0):
        print('MMYY')
    elif 1 <= a <= 12 and 1 <= b <= 12:
        print('AMBIGUOUS')
    else:
        print('NA')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    d = list(map(int, input().split()))
    m = int(input())
    t = list(map(int, input().split()))
    dc = Counter(d)
    tc = Counter(t)
    for k, v in tc.items():
        if dc[k]<v:
            print('NO')
            break
    else:
        print('YES')

if __name__ == '__main__':
    main()

Measured memory_bytes: 57304
#include <bits/stdc++.h>
using namespace std;
int main(){
  cout << fixed << setprecision(20);
  while (1){
    int n;
    cin >> n;
    if (n == 0){
      break;
    }
    vector<double> s(n);
    for (int i = 0; i < n; i++){
      cin >> s[i];
    }
    double S = 0;
    for (int i = 0; i < n; i++){
      S = S + s[i];
    }
    double m = S / n;
    double Vn = 0;
    for (int i = 0; i < n; i++){
      Vn = Vn + pow(s[i] - m, 2);
    }
    double V = Vn / n;
    double SD = sqrt(V);
    cout << SD << endl;
  }
}


Measured memory_bytes: 3268
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int h,n;
    cin>>h>>n;
    int a[n];
    int k=0;
    for(int j=0;j<n;j++)cin>>a[j];
    for(int j=0;j<n;j++){
        k+=a[j];
    }
    if(k<h){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }
}


Measured memory_bytes: 640
///////////////////// author : TrEbLeCleF /////////////////////
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define For(i, a) for (int i=0; i<(a); i++)
#define FORR(i,a,b) for (int i = (b)-1; i >= a; i--)
#define Forr(i,a) for (int i = (a)-1; i >= 0; i--)
/////////////////////////// DEBUG ///////////////////////////
#define deb(...) cerr << "[" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__) 
void DBG() { cerr << "]\n";}
template<typename T, typename ...Args> void DBG(T first, Args... args){
cerr << first; if(sizeof...(args))cerr<<", "; DBG(args...); }
/////////////////////////// DEBUG ///////////////////////////
#define pb(x) push_back(x)
#define print(v,s,e) for(int i = s; i < e; i++)cout << v[i]<<" ";cout<<"\n";
#define INF 1e17
#define PI 3.14159265358979323846 
int del_x[4] = {-1, 1, 0, 0};
int del_y[4] = {0, 0, 1, -1};
int XX[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int YY[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
/////////////////////////// GLOBAL ///////////////////////////
const int mod = 1e9+7;
int mul(int x,int y){
	int res = x*y;
	if(res >= mod)res%=mod;
	return res;
}
int add(int x, int y){
	int res = x+y;
	if(res >= mod)res-=mod;
	return res;
}
int sub(int x, int y){
	int res = x-y;
	if(res<0)res+=mod;
	return res;
}
int power(int x, int y){
	int res = 1;
	while(y){
		if(y&1)res = mul(res,x);
		y = y>>1;
		x = mul(x,x);
	}
	return res;
}

/////////////////////////// GLOBAL ///////////////////////////
void solve(){
	int n,m;
	cin >> n >> m;
	string matrix[n];
	For(i,n){
		cin >> matrix[i];
	}
	cout <<"";
	int dp[n+1][m+1];
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	For(i,n){
		if(matrix[i][0]!='#')dp[i][0]=1;
		else break;
	}
	For(j,m){
		if(matrix[0][j]!='#')dp[0][j]=1;
		else break;
	}
	For(i,n){
		For(j,m){
			if(matrix[i+1][j+1]!='#')
			dp[i+1][j+1] = add(dp[i+1][j],dp[i][j+1]);
		}
	}
	cout << dp[n-1][m-1] <<"\n";
}

int32_t main(){ 
	#ifndef ONLINE_JUDGE
		clock_t tStart = clock();
		freopen("TC", "r", stdin);
		//freopen("output.txt","w",stdout);
	#endif 
    ios_base:: sync_with_stdio(false); 
   	cin.tie(0); 
	int t=1;
	//cin >> t;
	for(int tt=1;tt<=t;tt++){
		//cout << "Case #"<<tt<<": ";
		solve();
	}
	#ifndef ONLINE_JUDGE
    	cerr << "\nRun Time -> "<<(double)(clock()-tStart)/CLOCKS_PER_SEC <<" sec\n";
    #endif
}

Measured memory_bytes: 8540
# include<bits/stdc++.h>
# define LL long long
using namespace std;
string a,b;
map<char,int> ma,ma1;
char A[201];
int main()
{
	cin>>a>>b;
	a+=a;
	if(a.find(b)==string::npos) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node{
  unsigned int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

void insert(int);
void init();
void printList();
void deleteFirst();
void deleteLast();
void delete();
NodePointer listSearch(int);
void deleteNode(NodePointer);

int main(){
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) {insert(key); np++; size++;}
    else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
	if ( com[6] == 'F' ) deleteFirst();
	else if ( com[6] == 'L' ) deleteLast();
      } else {
	delete(key); nd++; 
      }
      size--;
    }
  } //for

  printList();
  return 0;
}

//最初の一個
void init(){  
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(){
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void deleteNode(NodePointer t){
  if(t == nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
}

void deleteLast(){
  deleteNode(nil->prev);
}

void delete(int key){
  deleteNode(listSearch(key));
}

NodePointer listSearch(int key){
  NodePointer z;
  z = nil->next;
  while( z != nil && z->key != key ){
    z = z->next;
  }
  return z;
}

void insert(int key){
  NodePointer x;

  x = malloc(sizeof(struct node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev =x;
  nil->next = x;
  x->prev = nil;
}


Measured memory_bytes: 32948
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		
		Scanner cd = new Scanner(System.in);
		int x = 48-cd.nextInt();
		cd.close();
		System.out.println(x);
	}

}


Measured memory_bytes: 23124
d, g = map(int, input().split())
p, c = [], []
for _ in range(d):
    tmp_p, tmp_c = map(int, input().split())
    p.append(tmp_p)
    c.append(tmp_c)

res = float('inf')
for i in range(2**d):
    num = 0
    score = 0
    flag = [False] * d
    for j in range(d):
        if (i >> j) & 1:
            num += p[j]
            score += 100 * (j + 1) * p[j] + c[j]
            flag[j] = True
    
    if score >= g:
        res = min(res, num)
        continue
    
    for j in range(d-1, -1, -1):
        if flag[j]:
            continue

        if score + 100 * (j + 1) * p[j] < g:
            num += p[j]
            score += 100 * (j + 1) * p[j]
            continue
        else:
            n = ((g - score) + (100 * (j + 1)) - 1) // (100 * (j + 1))
            num += n
            break
    
    res = min(res, num)

print(res)

Measured memory_bytes: 73372
#include <bits/stdc++.h>
#define FOR(i,a,b) for(register int i=(a);i<(b);++i)
#define ROF(i,a,b) for(register int i=(a);i>=(b);--i)
#define pi pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 300005;
const int maxm = 100;
const int inf = 2147483647;
typedef long long ll;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
ll qpow(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c;b>>=1;}return ans;}
int n,cnt[maxn],a[maxn],tot=1,s[maxn];
bool check(int k,int x){
	int pos=lower_bound(a+1,a+tot,x)-a;
	int ans=s[pos-1]+x*(tot-pos);
	if(ans>=k*x)return true;
	return false;
}
int main(){
	scanf("%d",&n);
	vector<int>b;
	FOR(i,0,n){
		int u;
		scanf("%d",&u);
		if(!cnt[u])b.push_back(u);
		cnt[u]++;
	}
	FOR(i,0,b.size())a[tot++]=cnt[b[i]];
	sort(a+1,a+tot);
	FOR(i,1,tot)s[i]=s[i-1]+a[i];
	FOR(i,1,n+1){
		int l=0,r=n/i,ans=0;
		while(l<=r){
			int mid=l+r>>1;
			if(mid==ans || check(i,mid)){
				l=mid+1;
				ans=mid;
			}else r=mid-1;
		}
		printf("%d\n",ans);
	}
}


Measured memory_bytes: 7804
def main():

    H, W, M = map(int, input().split())
    A = set()
    row = dict()
    col = dict()

    for _ in range(M):
        h, w = map(int, input().split())
        A.add((h-1, w-1))
        row[h-1] = row.get(h-1, 0) + 1
        col[w-1] = col.get(w-1, 0) + 1

    max_row = max(row.values())
    max_col = max(col.values())
    cand_row = set([h for h in row if row[h] == max_row])
    cand_col = set([w for w in col if col[w] == max_col])

    # print(row)
    # print(col)
    # print(max_row, max_col)
    if len(cand_row) * len(cand_col) > M:
        return max_row + max_col
    else:
        for h in cand_row:
            for w in cand_col:
                if (h, w) not in A:
                    return max_row + max_col
        # print('here')
        return max_row + max_col - 1


if __name__ == '__main__':
    print(main())

Measured memory_bytes: 189820