akhauriyash/Code-Regression huggingface dataset:
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(ll i=0; i<(n); i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const long long MOD = 1000000007;

int main(void){
    string s;
    string t;
    ll ans=0;
    cin >> s;
    cin >> t;
    REP(i,s.size()){
        if(s[i] != t[i]){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

char x;
int N;

int main()
{
    int i;

    cin >> N;
    for(i=0; i<N; i++)
    {
        cin >> x;
        if(x=='Y')
        {
            cout << "Four";
            return 0;
        }
    }

    cout << "Three";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main()
{
    std::string str;
    std::cin >> str;
    int max = 0;
    for (int i = 0; (i < str.length()); ++i) {
        int num_match = 0;
        for (int j = i; (j < str.length()); ++j) {
            bool match = false;
            switch (str[j]) {
                case 'A':
                case 'C':
                case 'G':
                case 'T':
                    match = true;
                    break;
                default:
                    break;
            }
            if (!match) break;
            ++num_match;
        }
        max = (max > (num_match)) ? max : num_match;
    }
    std::cout << max << std::endl;
    return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
p = list(map(int,input().split()))
s = [0]
ans = [0]

#累積和
for i in range(n):
    s.append(s[i]+(p[i]+1)/2)

#区間kの和をリストに格納
for i in range(n-k+1):
    ans[i] = s[k+i] - s[i]
    ans.append(ans[i])

#区間kの和の中で最大値
print(max(ans))


Measured memory_bytes: 25060
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    String s = "";
    String t = "";
    for(int i = 0; i < w; i++) {
      if(i < a) {
        s += "0";
        t += "1";
      } else {
        s += "1";
        t += "0";
      }
    }
    for(int i = 0; i < h; i++) {
      if(i < b) {
        System.out.println(s);
      } else {
        System.out.println(t);
      }
    }
  }
}

Measured memory_bytes: 31956
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 1001001001
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int dp[1<<12];

int main(){
	int N,M; cin >> N >> M;
	vector<int> a(M);
	vector<int> bc(M);
	rep(i,M){
		cin >> a[i];
		int b; cin >> b;
		rep(j,b){
			int c; cin >> c;
			c--;
			bc[i] |= 1<<c;
		}
	}
	rep(i,1<<12) dp[i] = INF;
	dp[0] = 0;
	rep(i,1<<N){
		rep(j,M){
			dp[i|bc[j]] = min(dp[i|bc[j]],dp[i]+a[j]);
		}
	}
	
	if(dp[(1<<N)-1] == INF) cout << -1 << endl;
	else cout << dp[(1<<N)-1] << endl;
}
   


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<int,int>mp;
    int t,i,x;
    cin>>t;
   for(i=1;i<=t-1;i++)
    {
      cin>>x;
      mp[x]++;
        }
        for(int i=1;i<=t;i++)
        cout<<mp[i]<<endl;

}


Measured memory_bytes: 13004
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define bg begin()
#define en end()

#define pr_arr(name, a, b) \
  for (int i = (a); i < (b); i++) { \
    for (int j = (a); j < (b); j++) {\
      if (j > (a)) printf(" "); \
      printf("%lld", name[i][j]); \
    }\
    printf("\n");\
  }\

#define YES puts("YES")
#define NO  puts("NO")
#define Yes puts("Yes")
#define No  puts("No")

using namespace std;

static const int MAX = 1000005;

typedef long long ll;

int X;


bool isprime[MAX];

vector<int> eratosthenes_seive(int n) {
	vector<int> v;

	for (int i = 2; i <= n; i++) isprime[i] = true;

    for (int i = 2; i <= n; i++) {
    	if ( isprime[i] == true ) {
    		v.push_back(i);
    		for (int j = i + i; j <= n; j += i) isprime[j] = false;
    	}
    }
    return v;
}


int main(void) {
    scanf("%d", &X);
    eratosthenes_seive(MAX);

    rep(i, X, MAX) {
        if (isprime[i]) {
            printf("%d\n", i);
            return 0;
        }
    }

	return 0;
}


Measured memory_bytes: 1916
#include<iostream>
#include<algorithm>
#include<cstring>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int n;
int a[maxn];
int main()
{
    ios;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    ll x=unique(a,a+n)-a;
    if(x==n)  cout<<"YES";
    else cout<<"NO";
}


Measured memory_bytes: 4416
#include <iostream>

using namespace std;

int INF = 1000000000;

int main(){
  int N, K, tmp, min;
  cin >> N >> K;
  int h[N], dp[N];
  dp[0] = 0;
  for(int i=0; i<N; i++) cin >> h[i];
  for(int i=1; i<N; i++){
    for(int j=1; j<=K; j++){
      if(j == 1) min = min = dp[i-j] + abs(h[i]-h[i-j]);
      if(i-j >= 0  && min > (dp[i-j] + abs(h[i]-h[i-j]))) min = dp[i-j] + abs(h[i]-h[i-j]);
    }
    dp[i] = min;
  }
  cout << dp[N-1] << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
  int n,count;
  scanf("%d",&n);
  while(n!=0)
    {
      count = 0;
      while(n!=1)
	{
	  if(n%2==0)
	    n /=2;
	  else 
	    n = 3*n +1;
	  count++;
	}
      printf("%d\n",count);
      scanf("%d",&n);
    }
  return 0;
}

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

int main() {

  int a,b,c;
  
  cin >>a>>b>>c ;
  if((a<c&&c<b)||(b<c&&c<a)) {
    cout<<"Yes"<<endl;
  }
  else {
  cout<<"No"<<endl;
  }
  
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int ans[100005];
int res[100005];

int main(){
    int n;
    cin>>n;
    for (int i = 0; i <= n;i++){
        cin>>ans[i];
    }
    for (int i = 0; i < n;i++){
        cin>>res[i];
    }
    long long result = 0;
    for (int i = 0;i < n; i++){
        if (ans[i]-res[i]>=0){
            result += res[i];
            ans[i] = ans[i] - res[i];
            res[i] = 0;
        }
        else if (ans[i]-res[i] < 0){
            result += ans[i];
            res[i] = res[i] - ans[i];
            ans[i] = 0;
            if (ans[i+1] - res[i]>=0){
                result +=res[i];
                ans[i+1] = ans[i+1] - res[i];
                res[i] = 0;
            }
            else {
                result += ans[i+1];
                ans[i+1] = 0;
            }
        }
    }
    cout<<result<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define maxn 1000
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef double db;

char s[maxn+5],t[maxn+5];

int main()
{
    scanf("%s%s",s+1,t+1);
    int n=strlen(s+1);
    int m=strlen(t+1);
    int ans=inf;
    rep(st,1,n-m+1) 
    {
        int diff=0;
        rep(i,1,m) diff+=s[st+i-1]!=t[i];
        ans=min(ans,diff);
    }
    printf("%d\n",ans);
    return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int k;
    vector<int> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cin >> k;
    cout << a[k - 1] << endl;
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    ll a[n], b[n];
    rep(i,n) cin >> a[i] >> b[i];
    ll p = 0;
    for(int i = n-1; i >= 0; i--){
        a[i] += p;
        p += (a[i]+b[i]-1)/b[i]*b[i] - a[i];
    }
    cout << p << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <stdio.h>
using namespace std;
int main()
{
    int H, N;
    cin >> H;
    cin >> N;
    vector<int> vec(N+1);
    for(int i=0; i<N; i++){
      cin >> vec.at(i);
    }
    int sum = accumulate(vec.begin(), vec.end(), 0);
      if (H <= sum){
          string s = "Yes";
        cout << "Yes";  
        //printf("%s\n", s);
      }else{
          string s = "No";
        cout << "No";  
        //printf("%s\n", s);
      }
    return 0;
}


Measured memory_bytes: 640
module Main where
main = interact $ printer . solver . parser
int = read :: String -> Int

printer = unlines . map (unwords . map show)
parser = map int . words

solver (h:w:n:cs) = v3
  where
    v1 = concat $ map (uncurry  replicate) $ zip cs [1..]
    v2 = map (take w) $ take h $ iterate (drop w) v1
    v3 = zipWith ($) (concat $ repeat [id , reverse]) v2


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

using ll = long long;

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

template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

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

    int N;
    string S;
    int Q;
    cin >> N >> S >> Q;
    vector<int> K(Q); cin >> K;

    vector<ll> sumd(N);
    vector<ll> summ(N);
    vector<ll> sumdm(N);
    for (int i = 0; i < N; i++) {
        sumd[i] = (i == 0 ? 0 : sumd[i-1]) + (S[i] == 'D' ? 1 : 0);
        summ[i] = (i == 0 ? 0 : summ[i-1]) + (S[i] == 'M' ? 1 : 0);
        sumdm[i] = (i == 0 ? 0 : sumdm[i-1]) + (S[i] == 'M' ? sumd[i] : 0);
    }

    for (int k : K) {
        ll ans = 0;
        for (int i = 0; i < N; i++) {
            if (S[i] == 'C') {
                ll dm = 0;
                if (i - 1  >= 0) {
                    dm = sumdm[i-1];
                    if (i - k >= 0) {
                        dm -= sumdm[i-k];
                        dm -= sumd[i-k] * (summ[i-1] - summ[i-k]);
                    }
                }
                ans += dm;
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 24860
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int n;cin>>n;
    set <char> s;
    rep(i,n){
        char c; cin>>c;
        s.insert(c);
    }
    cout<<((s.size() == 3)?"Three":"Four")<<endl; return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
double dp[301][301][301];
int a,b,c;

double solve(int th,int tw, int o)
{   
    if(o<0||tw<0||th<0) return 0;
    else if(th==0&&tw==0&&o==0) return 0;
    else if(dp[o][tw][th]){return dp[o][tw][th];}
    else{
        
        double nz= o+tw+th;
        dp[o][tw][th] += (double)(n/nz);  
        dp[o][tw][th] += (((1/nz)*th)*solve(th-1,tw+1,o)) 
                            + (((1/nz)*tw)*solve(th,tw-1,o+1))
                                + (((1/nz)*o)*solve(th,tw,o-1));
      
        return dp[o][tw][th];
    }
    
}
int main()
{
    
    cin>>n;
    vector<int> v(n);
    

    for(int i=0;i<n;++i)
        {
            cin>>v[i];
            a+= v[i]==1;
            b+= v[i]==2;
            c+= v[i]==3;
            //indx+=((int)(pow(10,v[i]-1)));
        }
   
   dp[0][0][0]=0;
   cout<<setprecision(16)<<solve(c,b,a)<<endl;
   
   
   
    
}


Measured memory_bytes: 213248
import math
n,p=map(int,input().split())
res = 1
if n ==1:
    res = p
    p = 1
for i in range(2,int(math.sqrt(p))+1):
    c = 0
    while p%i==0:
        p = p/i
        c +=1
    #print(i,c)
    if c//n > 0:
        for j in range(c//n) : res*=i
    if p < i:break
    #print(res)
print(res)
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 50 + 10;
int n, m;
vector<int> E[maxn];
int dep[maxn], fa[maxn], x[maxn], y[maxn], cnt[maxn];
void dfs(int x)
{
	dep[x] = dep[fa[x]] + 1;
	for(auto v : E[x])
		if(v != fa[x])
		{
			fa[v] = x;
			dfs(v);
		}
}
void add(int u, int v, int val)
{
	if(dep[u] < dep[v]) 	
		swap(u, v);
	while(dep[u] != dep[v])
	{
		cnt[u] += val;
		u = fa[u];
	}
	while(u != v)
	{
		cnt[u] += val;
		cnt[v] += val;
		u = fa[u];
		v = fa[v];
	}
}	
ll solve(int now)
{
	if(now == m + 1)
	{
		int tot = 0;
		for(int i = 2; i <= n; ++i)
			if(!cnt[i])
				++tot;
		return 1ll << tot;
	}
	ll ret = solve(now + 1);
	add(x[now], y[now], 1);
	ret -= solve(now + 1);
	add(x[now], y[now], -1);
	return ret;
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs(1);
	scanf("%d", &m);
	for(int i = 1; i <= m; ++i)
		scanf("%d%d", &x[i], &y[i]);
	cout << solve(1) << endl;
	return 0;
}

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

using namespace std;

class myclass
{
public:
  static int gcd(int a, int b);
};

int main()
{
  int N, count = 0, gcd;
  cin >> N >> gcd;

  for (int i = 1; i < N; i++)
  {
    int A;
    cin >> A;
    gcd = myclass::gcd(gcd, A);
  }

  while (gcd % 2 == 0)
  {
    gcd /= 2;
    count++;
  }

  cout << count << endl;
}

int myclass::gcd(int a, int b)
{
  if (a % b == 0)
  {
    return (b);
  }
  else
  {
    return (gcd(b, a % b));
  }
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int oturi;
	int count;
	
	while (1){
		scanf("%d", &oturi);
		if (oturi == 0){
			break;
		}
		oturi = 1000 - oturi;
		
		count = 0;
		while (oturi > 0){
			if (oturi >= 500){
				count++;
				oturi -= 500;
			}
			else if (oturi >= 100){
				count++;
				oturi -= 100;
			}
			else if (oturi >= 50){
				count++;
				oturi -= 50;
			}
			else if (oturi >= 10){
				count++;
				oturi -= 10;
			}
			else if (oturi >= 5){
				count++;
				oturi -= 5;
			}
			else if (oturi >= 1){
				count++;
				oturi -= 1;
			}
		}
		
		printf("%d\n", count);
	}
	
	return (0);
}

Measured memory_bytes: 600
#include <iostream>
#include <sstream>
#include <iterator>
#include <string>
#include <vector>
#include <algorithm>
#include <list>

#define YESNO(x) x ? printf("YES") : printf("NO")
#define YesNo(x) x ? printf("Yes") : printf("No")

using namespace std;

//ABC096C - Grid Repainting 2
int Main() {
	static const char EMPTY = '.';
	static const char BLACK = '#';
	int H = 0, W = 0;
	vector<string> src;
	bool ans = true;

	//input
	scanf("%d", &H);
	scanf("%d", &W);
	src.resize(H);
	for (auto &line : src) {
		cin >> line;
	}

	//check
#define BLACK_CHECK(y,x) (0 <= x && x < W && 0 <= y && y < H && '#' == src[y][x])
	for (int y = 0; y < H; y++)
		for (int x = 0; x < W; x++) {
			if ('#' == src[y][x]) {
				if (!(BLACK_CHECK(y - 1, x) ||
					BLACK_CHECK(y, x - 1) ||
					BLACK_CHECK(y + 1, x) ||
					BLACK_CHECK(y, x + 1)))
					ans = false;
			}
		}

	YesNo(ans);

	return 0;
}


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

Measured memory_bytes: 256
x, k, d = map(int, input().split())
x = abs(x)
ans = 0
if int(x/d) > k:
  ans = x - d*k
else:
  e = int(x/d)
  k -= e
  x -= e*d
  if k%2 == 1:
    x = abs(x-d)
  ans = x
print(ans)


Measured memory_bytes: 61812
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main(void){
    double x,h,S,H;
    while(cin >> x >> h){
        if(x==0 && h==0)    break;
        else{
            H=sqrt(h*h+(x/2)*(x/2));
            S=x*x+x*(H/2)*4;
            std::cout << std::fixed << std::setprecision(6) << S << endl;
        }
    }
}


Measured memory_bytes: 3260
#include <stdio.h>
int main() {
        int N;
        scanf("%d", &N);
        int c[10][10]; // saves first and last digit
        for (int i =0; i<10; i++)
                for (int j =0; j<10; j++)
                        c[i][j] = 0;

        for (int i =1; i <= N; i++ ){
                int x = i;
                while ( x >= 10) x /= 10;
                c[x][i%10]++;
        }
        int ans = 0;
        for (int i =0; i <=9; i++)
                for (int j =0; j<=9; j++)
                        ans += c[i][j] * c[j][i];
        printf("%d\n", ans);
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 29);
const ll LINF = 1e18;
const double PI = acos(-1);

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template <typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
    for(auto &e:t) fill_v(e,v);
}
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;
}

struct Edge
{
public:
    int from, to, cost;
    Edge() {}
    Edge(int _from, int _to, int _cost)
    {
        from = _from;
        to = _to;
        cost = _cost;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;



void floyd(int n, vector<vll>& WF)
{
    REP(k, n)
    REP(i, n)
    {
        if (WF[i][k] == LINF)
            continue;
        REP(j, n)
        {
            if (WF[k][j] == LINF)
                continue;
            chmin(WF[i][j], WF[i][k] + WF[k][j]);
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    ll L;
    cin >> N >> M >> L;
    auto WF = make_v<ll>(N,N);
    fill_v(WF,LINF);
    REP(i,M){
        int A,B,C;
        cin >> A >> B >> C;
        A--;B--;
        WF[A][B] = C;
        WF[B][A] = C;
    }
    floyd(N,WF);

    auto NWF = make_v<ll>(N,N);
    fill_v(NWF,LINF);
    REP(i,N){
        REP(j,N){
            if(i == j){
                NWF[i][j] = 0;
            }else if(WF[i][j] <= L){
                NWF[i][j] = 1;
            }
        }
    }
    floyd(N,NWF);
    int Q;
    cin >> Q;
    REP(i,Q){
        int s,t;
        cin >> s >> t;
        s--;t--;
        if(NWF[s][t] >= INF)cout << -1 << endl;
        else cout << NWF[s][t] - 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 2048
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
char S[150];
char S1[150];

void rotate(){
 for(int i=1; i<strlen(S1); i++){
  S1[i]=S[i-1];
 }
 S1[0]=S[strlen(S)-1];
 for(int i=0; i<=strlen(S1); i++)S[i]=S1[i];
}

int main(void){
 char T[150];
 int OK=0;

 cin>>S>>T;

 for(int i=0; i<=strlen(S);i++)S1[i]=S[i];
 for(int i=0; i<strlen(S); i++){
  if(strcmp(S1,T)==0){
   OK=1;
   break;
  }
  rotate();
 }
 if(OK)std::cout<<"Yes"<<std::endl;
 else std::cout<<"No"<<std::endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;
const double pi =  3.1415926;
int get(int x) {
    return (2000-(x+1))/200+1;
}
int main() {

    int m, p,n;
    int flag[110];
    double r;
    int t;
    while (scanf("%d",&t)!=EOF) {
        printf("%d\n",get(t));
    }
    return 0;
}


Measured memory_bytes: 3228
"use strict";
var input = require("fs").readFileSync("/dev/stdin", "utf8");
var cin = input.split(/ |\n/), cid = 0;

function next() { return +cin[cid++]; }// number一個取得
function nextstr() { return cin[cid++]; }// 文字列一個取得
function nextbig() { return BigInt(cin[cid++]); }// BigInteger一個取得
// 長さnの配列として取得。aは文字列フラグ
function nexts(n, a) { return a ? cin.slice(cid, cid += n) : cin.slice(cid, cid += n).map(a => +a); }
// 長さnのBigInt配列として取得。
function nextsbig(n) { return cin.slice(cid, cid += n).map(a => BigInt(a)); }
// w個ずつを組にして長さhの配列。aは文字列フラグ。
function nextm(h, w, a) {
    var r = [], i = 0;
    if (a) for (; i < h; i++)r.push(cin.slice(cid, cid += w));
    else for (; i < h; i++)r.push(cin.slice(cid, cid += w).map(a => +a));
    return r;
}
function xArray(v) { var a = arguments, l = a.length, r = "Array(a[" + --l + "]).fill().map(x=>{return " + v + ";})"; while (--l) r = "Array(a[" + l + "]).fill().map(x=>" + r + ")"; return eval(r); }


    console.log(main().toString());

    function main() {
        let S = nextstr();
        return S.substring(0,3);
    
    
    
    }

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

int main(){
  char n[4];
  for(int i=0;i<4;++i) cin >> n[i];
  map<char,bool> mp;
  for(int i=0;i<4;++i) mp[n[i]]=true;

  if(mp['1'] and mp['9'] and mp['7'] and mp['4']) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>

typedef long long ll;
ll n;
ll Sum;

int main(){
	scanf("%lld", &n);
	Sum = (1 + n) * n / 2;
	for(ll i = 1; ; i++){
		ll One = i * 3;
		ll Two = i * 5;
		if(One > n && Two > n) break;
		if(One <= n) Sum -= One;
		if(Two % 15 != 0 && Two <= n) Sum -= Two;
	}
	printf("%lld", Sum);
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3
#define MAX_V 800

struct edge{ int to,cap,rev; };
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void init(){
  rep(i,MAX_V){
    G[i].clear();
  }
}

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    int v=que.front(); que.pop();
    for(int i=0;i<G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[e.to]<0){
        level[e.to]=level[v]+1;
        que.push(e.to);
      }
    }
  }
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  for(int &i=iter[v];i<G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  while(1){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}

ll h,w,c,m,nw,nc,nm;

int main(){
	cin.sync_with_stdio(false);
  while(1){
    cin>>h>>w>>c>>m>>nw>>nc>>nm;
    if(h==-1)break;
    init();
    ll hst=0,wst=hst+h*2,cst=wst+w*2+nw*2,mst=cst+c*2+nc*2;
    ll source=mst+m*2+nm*2,sink=source+1;
    rep(i,h){
      add_edge(source,hst+i,1);
      add_edge(hst+i,hst+h+i,1);
      rep(j,nw)add_edge(hst+h+i,wst+w+j,1);
    }
    rep(i,w+nw){
      add_edge(wst+i,wst+w+nw+i,1);
      if(i<w){
        rep(j,nc)add_edge(wst+w+nw+i,cst+c+j,1);
      }else{
        rep(j,c)add_edge(wst+w+nw+i,cst+j,1);
      }
    }
    rep(i,c+nc){
      add_edge(cst+i,cst+c+nc+i,1);
      if(i<c){
        rep(j,nm)add_edge(cst+c+nc+i,mst+m+j,1);
      }else{
        rep(j,m)add_edge(cst+c+nc+i,mst+j,1);
      }
    }
    rep(i,m+nm){
      add_edge(mst+i,mst+m+nm+i,1);
      add_edge(mst+m+nm+i,sink,1);
    }
    rep(i,w){
      ll num;
      cin>>num;
      while(num--){
        ll p;
        cin>>p; p--;
        add_edge(hst+h+p,wst+i,1);
      }
    }
    rep(i,c){
      ll num;
      cin>>num;
      while(num--){
        ll p;
        cin>>p; p--;
        add_edge(wst+w+nw+p,cst+i,1);
      }
    }
    rep(i,m){
      ll num;
      cin>>num;
      while(num--){
        ll p;
        cin>>p; p--;
        add_edge(cst+c+nc+p,mst+i,1);
      }
    }
    cout<<max_flow(source,sink)<<endl;
  }
	return 0;
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }

template<typename T>
vector<T> makeVector(size_t a, T b) { return (vector<T>(a, b)); }
template<typename... Ts>
auto makeVector(size_t a, Ts... ts) { 
	return (vector<decltype(makeVector(ts...))>(a, makeVector(ts...)));
}

template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	if (v.size()) {
		os << v[0];
		for (int i = 1; i < v.size(); i++) os << " " << v[i];
	}
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}

ll N;
ll calc(vll &A) {
	vll divisor;
	for (ll i = 1; i*i <= A[0]; i++) {
		if (A[0] % i == 0) {
			divisor.push_back(i);
			if (i != A[0]/i) divisor.push_back(A[0]/i);
		}
	}
	sort(begin(divisor), end(divisor));
	ll ans = 0;
	for (auto &div : divisor) {
		int cnt = 0;
		for (int i = 1; i < N; i++) {
			if (A[i]%div == 0) {
				cnt++;
			}
		}
		if (cnt >= N-2) ans = div;
	}
	return (ans);
}

void Main() {
	cin >> N;
	vll A(N); cin >> A;
	ll ans = calc(A);
	swap(A[0], A[1]);
	chmax(ans, calc(A));
	cout << ans << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 3956
/*
AizuOnline A1045
Split Up!
*/
#include <stdio.h>




main()
{
  int i,j;
  long int sumdiff;
  long int minsumdiff;
  long int members[20]={1,2,3,4,80,100,2};
  int  n  = 7;

  
while(EOF != scanf("%d",&n) && n > 0)
    {
      
      i=0;
      for(i=0;i<n;i++)
        scanf(" %d",&(members[i]));
  
      minsumdiff = 1000000;
      for(i=0;i<(1<<n-1);i++)
        {  
          sumdiff=0;
          for(j=0;j<n;j++)
            { 
              sumdiff += ((i & (1<<j))?(-1):1) * members[j];
            }
          sumdiff = (sumdiff<0)?(-sumdiff):(sumdiff);
          
          if(sumdiff < minsumdiff)
            minsumdiff = sumdiff;
        }
  
      printf("%d\n",minsumdiff);
    }
return(0);
}

Measured memory_bytes: 408
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <functional>
#include <map>
using namespace std;

int N, A, B, C;

int main() {
	cin >> N >> A >> B >> C;
	cout << N - A - B + C << endl;
	return 0;
}


Measured memory_bytes: 3084
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    left, right = 0, 0
    for char in s:
        if char == '(':
            right += 1 
            # prefixが')'の可能性があるのでleftを削ることはできない
        elif char == ')':
            if right: 
                # rightがあるならこれより前に必ず'('が存在するのでrightの可能性を一つ削ってこれを代わりにその'('とペアにする
                right -= 1
            else: # rightがない場合はこれとペアになることのできる'('がこれ以前に出現していないということので追加
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
def readInt():
    return list(map(int,input().split()))
n = int(input())
l = []
for i in range(1,n):
    ans = 0
    j = i
    k = n-i
    while j>0:
        ans += int(j%10)
        j = int(j/10)
    while k>0:
        ans += int(k%10)
        k = int(k/10)
    l.append(ans)
# print(l)
print(min(l))

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

int main() {
  char c;
  cin >> c;
  
  if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;
using P3 = std::tuple<int,int,int>;

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

int N, M;
P3 ps[500];
int dp[350][350][350];

const ll MOD = 1e9 + 7;

inline bool isIn(int i, int l, int r){
    return l <= i && i <= r;
}

int rec(int r, int g, int b, int r_idx){
    int cur = max({r, g, b});
    
    if(dp[r][g][b] != -1){return dp[r][g][b];}
    while(r_idx < M && fst(ps[r_idx]) == cur){
        int l = snd(ps[r_idx]), ri = fst(ps[r_idx]), x = thd(ps[r_idx]);
        int cnt = isIn(r, l, ri) + isIn(g, l, ri) + isIn(b, l, ri);
        if(cnt != x){
            return 0ll;
        }
        r_idx++;
    }
    if(cur == N){return 1ll;}    

    int res = 0;
    res = (rec(cur + 1, g, b, r_idx) + rec(r, cur + 1, b, r_idx)) % MOD;
    res = (res + rec(r, g, cur + 1, r_idx)) % MOD;

    return dp[r][g][b] = res;
}

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

    for(int i=0;i<M;++i){
        int l, r, x;
        std::cin >> l >> r >> x;

        ps[i] = std::make_tuple(r, l, x);
    }

    sort(ps, ps+M);
    fill(&dp[0][0][0], &dp[0][0][0]+350*350*350, -1);

    ll res = rec(0, 0, 0, 0);
    std::cout << res << std::endl;
}


Measured memory_bytes: 167808
#include <iostream>
#include <vector>
#define REP(i,n) for(int i = 0; i < (n); i++)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second

using namespace std;
typedef pair<int, int> P;

int mp[600][600];
int main()
{
  int H, W; cin >> H >> W;
  REP(i, H) REP(j, W) cin >> mp[i][j];

  vector<pair<P, P>> insts;
  REP(i, H) {
    REP(j, W-1) {
      if (mp[i][j] > 0 && mp[i][j] % 2 == 1) {
        insts.PB(MP(MP(i+1,j+1),MP(i+1,j+2)));
        mp[i][j]--;
        mp[i][j+1]++;
      }
    }
  }

  REP(i, H-1) {
    if (mp[i][W-1] > 0 && mp[i][W-1] % 2 == 1) {
        insts.PB(MP(MP(i+1,W),MP(i+2,W)));
        mp[i][W-1]--;
        mp[i+1][W-1]++;
    }
  }

  cout << insts.size() << endl;
  for (auto e : insts) {
    cout << e.FI.FI << ' ' << e.FI.SE << ' ' << e.SE.FI << ' ' << e.SE.SE << endl;
  }

  return 0;
}


Measured memory_bytes: 5488
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pull = pair<ull, ll>;
#define INF 1000000000
#define LLINF 10000000000000000ll
#define MOD 1000000007LL

bool dbgflag = false;


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

  ll n;
  cin >> n;
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ll a;
    cin >> a;
    while (a % 2 == 0) {
      a /= 2;
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll, ll>;
#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 all(x) (x).begin(), (x).end()
const ll INF = ll(1e18)+1;

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

    ll n;
    cin >> n;

    vector<string> si(n);
    rep(i,n) cin >> si[i];

    ll ac=0,wa=0,tle=0,re=0;
    rep(i,n){
        if(si[i] == "AC"){
            ac++;
        }
        else if(si[i] == "WA"){
            wa++;
        }
        else if(si[i] == "TLE"){
            tle++;
        }
        else if(si[i] == "RE"){
            re++;
        }
    }
    cout << "AC x " << ac << "\n";
    cout << "WA x " << wa << "\n";
    cout << "TLE x " << tle << "\n";
    cout << "RE x " << re << "\n";
}

Measured memory_bytes: 6372
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef vector<vector<ll>> matrix;

ll l[1005];
int n, k;
void solve() {
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		cin >> l[i];
	}
	vector<ll> allS;
	for(int i = 0; i < n; i++) {
		ll curr = 0;
		for(int j = i; j < n; j++) {
			curr += l[j];
			allS.push_back(curr);
		}
	}
	ll ret = 0;
	for(int d = 40; d >= 0; d--) {
		ll cand = ret | (1LL << d);
		int match = 0;
		for(ll out: allS) {
			if((cand&out) == cand) match++;
		}
		if(match >= k) {
			ret = cand;
		}
	}
	cout << ret << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
	/*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
	*/
	solve();
}


Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
int main (){
    string s;
    cin >> s;
    if(s=="SUN"){
        cout << 7 << endl;
    }
    else if(s=="MON"){
        cout << 6 << endl;
    }
    else if(s=="TUE"){
        cout << 5 << endl;
    }
    else if(s=="WED"){
        cout << 4 << endl;
    }
    else if(s=="THU"){
        cout << 3 << endl;
    }
    else if(s=="FRI"){
        cout << 2 << endl;
    }
    else if(s=="SAT"){
        cout << 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int sum(int n) {
	int ans = 0;
	while (n) {
		ans += n % 10;
		n /= 10;
	}
	return ans;
}

int main() {
	int n, a, b, tmp, ans = 0;
	scanf("%d%d%d", &n, &a, &b);
	for (int i = 1; i <= n; i++){
		tmp = sum(i);
		if (a <= tmp && tmp <= b) ans += i;
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int graph[15][15];

int main() {
  int N;
  cin >> N;
  rep(i, N) rep(j, N) graph[i][j] = -1;
  rep(i, N) {
    int A;
    cin >> A;
    rep(j, A) {
      int x, y;
      cin >> x >> y;
      --x;
      graph[i][x] = y;
    } 
  }
  int ans = 0;  
  for (int bit = 0; bit < (1<<N); bit++) {
    //if (__builtin_popcount(bit) <= ans) continue;
    vector<int> temp(N);
    for (int i = 0; i < N; i++) {
      if ((bit>>i)&1) temp[i] = 1;
    }
    bool flag = true;
    rep(i, N) {
      if (temp[i] == 0) continue;
      rep(j, N) {
        if (graph[i][j] == -1) continue;
        if (graph[i][j] != temp[j]) {
          flag = false;
        }
      }
    }
    if (flag) ans = max(ans, __builtin_popcount(bit));
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3536
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define f first
#define s second 
using namespace std;
const LL INF = (LL) 1e9 + 5;
const LL MOD = (LL) 1e9 + 7;
const int MAXN = 105;

int n, m, col[MAXN][MAXN], dp[MAXN][MAXN];

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char ch;
			cin >> ch;
			col[i][j] = (ch == '#');
			
			if (i == 1 && j == 1) {
				dp[i][j] = col[i][j];
				continue;
			}
			
			dp[i][j] = INF;
			if (i != 1) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (col[i - 1][j] == 0 && col[i][j] == 1));
			if (j != 1) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (col[i][j - 1] == 0 && col[i][j] == 1));
//			cout << i << ' ' << j << " -> " << dp[i][j] << '\n';
		}
	}
	cout << dp[n][m] << '\n';

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define INF 1e12
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int a,b; cin>>a>>b;
	if((a*b)%2) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

Measured memory_bytes: 256
/*
    _____
  .'|||||'.
 /  >   <  \
|     ^     |
|  \     /  |
 \  '---'  /
  '._____.'
    |||||
*/

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
int n,ans,x[200],y[200];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
    scanf("%d",&x[i]);
    ans+=x[i];
}
if (ans%10!=0) printf("%d\n",ans); else
{
    sort(x+1,x+1+n);
    int o=0;
    for (int i=1;i<=n;i++)
        if (x[i]%10!=0)
    {
        o++;
        y[o]=x[i];
    }
    if (o==0) printf("0\n"); else
    {
        printf("%d\n",ans-y[1]);
    }

}
    return(0);
}


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

using namespace std;

using State = vector<int>;

pair<int, int> resolveOp(string op) {
    if (op == "AB") {
        return {0, 1};
    }
    if (op == "BC") {
        return {1, 2};
    }
    return {0, 2};
}

char pickRes(pair<int, int> op, int mul) {
    auto op1 = 'A' + op.first;
    auto op2 = 'A' + op.second;
    return mul == 1 ? op1 : op2;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
    State init(3);
    for (int i = 0; i < init.size(); i++) {
        int v;
        cin >> v;
        init[i] = min(v, 3);
    }
    vector<string> ops(n);
    for (int i = 0; i < n; i++) {
        cin >> ops[i];
    }

    map<pair<int, State>, pair<char, State>> mem;
    function<pair<char, State>(int i, State)> dp;
    dp = [&] (int i, State st) -> pair<char, State> {
        for (int v: st) {
            if (v < 0) {
                return {0, st};
            }
        }
        if (i == n) {
            return {'x', st};
        }
        pair<int, State> cur = {i, st};
        if (mem.count(cur) == 0) {
            auto op = resolveOp(ops[i]);
            pair<char, State> ans = {0, st};
            for (int mul = -1; mul <= 1; mul += 2) {
                auto nxtSt = st;
                nxtSt[op.first] += mul;
                nxtSt[op.second] -= mul;
                auto nxtRes = dp(i+1, nxtSt);
                if (nxtRes.first != 0) {
                    ans = { pickRes(op, mul), nxtSt };
                    break;
                }
            }
            mem[cur] = ans;
            return ans;
        }
        return mem[cur];
    };
    auto ans = dp(0, init);
    if (ans.first == 0) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        auto cur = ans;
        for (int i = 0; i < n; i++) {
            cout << cur.first << "\n";
            cur = dp(i+1, cur.second);
        }
    }
}



Measured memory_bytes: 65464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#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++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
	ll N, W;
	cin >> N >> W;
	vector<ll> w(N), v(N);
	rep(i, N) cin >> w[i] >> v[i];
	vector<vector<ll> > dp(N+1, vector<ll> (W+1));
	rep(i, N){
		rep(j, W+1) {
			if(j < w[i]) {
				dp[i+1][j] = dp[i][j];
			}
			else {
				dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
			}
		}
	}

	cout << dp[N][W] << endl;

}

Measured memory_bytes: 83072
#include<bits/stdc++.h>
#define intt long long 
using namespace std;
const int maxx = 2e6+1314;
const int M = 998244353;
intt read(){intt k;cin>>k;return k;}
intt n,k,Ans=0;
intt qsm(intt x){
	if(x==0)return 1;	
	intt s=x,ans=1;
	int k=M-2;
	while(k){
		if(k&1)ans=ans*s%M;
		k>>=1;s=s*s%M;
	}	
	return ans;
}	
intt ans=0;
intt times[maxx];
intt inv[maxx];
void pre(){	
	times[0]=1;
	for(int i=1;i<=maxx-2;i++)times[i]=times[i-1]*i%M;
}	
intt C(int a,int b){
if(b<0)return 0;
return times[a]*qsm(times[a-b])%M*qsm(times[b])%M;}
intt work1(int x,int y){
	ans+= C(x+y-1,y-1)-C(x+y-1,y-1-(x-n+1));
	ans%=M;
}	
intt work2(int x,int y){
	ans+=C(x+y,y)-C(x+y,y-(x-n+1));
	ans%=M;
}	
int main(){	
	pre();
	n=read();k=read();
	for(int i=n;i<=k;i++){	
		int x=i,y=k-i;
		if(x<y)continue;
		if(x==y)work1(x,y);
		else work2(x,y);
	}	
	cout<<ans<<endl;
	return 0;	
}	
	
	

Measured memory_bytes: 17280
# 君指先跃动の光は、私の一生不変の信仰に、唯私の超电磁炮永生き！
from sys import stdin, stdout
import math
import bisect
from collections import defaultdict
import datetime
import random

s = stdin.readline().strip()
cnt = 0
# s = ''
# for i in range(200000):
#     s += str(random.randint(1, 9))
    
# print('start')

d = defaultdict(int)
d[0] = 1
# starttime = datetime.datetime.now()
now = 0
mul = 1
for each in s[::-1]:
    now = (int(each) * mul + now) % 2019
    cnt += d[now]
    d[now] += 1
    mul = (mul * 10) % 2019
stdout.writelines(str(cnt) + '\n')
# stoptime = datetime.datetime.now()
# print(stoptime - starttime)

Measured memory_bytes: 78980
s = input()
k = int(input())

ss = set()
for i in range(len(s)):
    for j in range(i+1, min(i+6, len(s)+1)):
        ss.add(s[i:j])

for i, s in enumerate(sorted(ss), start=1):
    if i == k:
        print(s)
        break


Measured memory_bytes: 39920
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    A.sort()
    B.sort()
    
    if N % 2 == 0:
        a = A[N // 2 - 1] + A[N // 2]
        b = B[N // 2 - 1] + B[N // 2]
        ans = (b - a) + 1
    else:
        a = A[N // 2]
        b = B[N // 2]
        ans = b - a + 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 25364
N = int(input())
a = list(map(lambda x : int(x) // 400, input().split()))
over3200 = sum(list(map(lambda x: 1 if x >= 8 else 0, a)))

count = 0
for i in range(8):
    if i in a:
        count += 1
        
print(max(1, count), count+over3200)


Measured memory_bytes: 2940
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);++i)
#define rrep(i,n) for(int (i)=(n)-1;(i)>=0;--i)
#define rep1(i,n) for(int (i)=1;(i)<=(n);++i)
#define rrep1(i,n) for(int (i)=(n);(i)>=1;--i)
#define pb push_back
#define fr first
#define sc second
typedef long long ll;
typedef pair<int,int> P;
typedef pair<long long,long long> LP;
typedef double db;
using namespace std;

ll N,M;
ll A[100000],B[100000];
int X[100000];
vector<ll> vs[100000];
ll C[2];

bool dfs(int v,int p,int val){
  if(X[v] == -1){
    X[v]=val;
    C[val]++;
    rep(i,vs[v].size()){
      if(p == vs[v][i]) continue;
      if( dfs(vs[v][i], v, !val ) ) return 1;
    }
  }
  else if(X[v] != val){
    return 1;
  }
  return 0;
}

int main()
{
  cin>>N>>M;
  rep(i,M){
    cin>>A[i]>>B[i];
    A[i]--;
    B[i]--;
    vs[A[i]].pb(B[i]);
    vs[B[i]].pb(A[i]);
  }
  memset(X,-1,sizeof(X));
  if(dfs(0,-1,0)){
    cout << (N*(N-1)/2)-M<<endl;
  }
  else{
    cout<< C[0]*C[1]-M<<endl;
  }
}


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

int main()
{
  int a, b;
  cin >> a >> b;
  if (1 <= a && a <= 9 && 1 <= b && b <= 9) {
    cout << a * b << '\n';
  } else {
    cout << "-1\n";
  }
  return 0;
}


Measured memory_bytes: 256