akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define mp make_pair
#define pb push_back
#define FF first
#define SS second

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

const int N = 100005;
const int BSZ = 320;
int X[N];

void _put(int l, int r) {
  if(l > r) return;
  X[r+1]--;
  X[l]++;
}

int main() {
  int n,m;
  S2(n,m);
  while(n--) {
    int l,r;
    S2(l,r);
    int x = r - l + 1;
    if(x >= l) {
      _put(1, r);
      continue;
    }
    _put(1,x);
    _put(l,r);
    rep(i,x+1,BSZ) {
      if(i >= l) break;
      int tmp = (l + i - 1) / i;
      tmp *= i;
      if(tmp >= l && tmp <= r) _put(i,i);
    }
    int hi = l - 1;
    int lo = max(BSZ,x+1);
    rep(i,2,BSZ) {
      if(lo > hi) break;
      int e = r / i;
      int b = (l + i - 1) / i;
      e = min(e, hi);
      b = max(b, lo);
      _put(b, e);
      hi = b - 1;
    }
  }
  rep(i,1,m+1) {
    X[i] += X[i-1];
    P(X[i]);
  }
  return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

long long cnt;
int n, A[1000000];
vector<int> G;

void insertion_sort(int A[], int n, int g) {
    int v, j;

    for (int i = g; i < n; i++) {
        v = A[i];
        j = i - g;
        while (j >= 0 && A[j] > v) {
            A[j + g] = A[j];
            cnt++;
            j -= g;
        }
        A[j + g] = v;
    }
}

void shell_sort(int A[], int n) {

    for (int h = 1; h <= n; h = 3 * h + 1) {
        G.push_back(h);
    }

    for (int i = G.size() - 1; i >= 0; i--) {
        insertion_sort(A, n, G[i]);
    }
}

int main () {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    cnt = 0;

    shell_sort(A, n);
    
    printf("%d\n", G.size());
    for (int i = G.size() - 1; i >= 0; i--) {
        printf("%d", G[i]);
        if(i) printf(" ");
    }
    printf("\n");
    printf("%d\n", cnt);
    for (int i = 0; i < n; i++) printf("%d\n", A[i]);

    return 0;
}


Measured memory_bytes: 7100
#include <bits/stdc++.h>
#define X first
#define Y second
#define LL long long
#define MP make_pair
#define PB push_back
#define SZ(a) (int)(a.size())
const int INF = 1000 * 1000 * 1000 + 47;
using namespace std;

int main() 
{
	string s , t;
	cin >> s >> t;
	int cor = 0;
	for(int i = 0; i < SZ(s); i++)
		cor += s[i] == t[i];
	cout << cor << endl;
}


Measured memory_bytes: 256
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

s = input()
if s[1] == 'R':
    print('ABC')
else:
    print('ARC')

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

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

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

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

signed main(){
	int N,K;
	cin>>N>>K;
	string S;cin>>S;

	vint R;
	if(S[0]=='0')R.pb(0);
	int cur=0;
	while(cur<N){
		int nex=cur;
		while(nex<N&&S[cur]==S[nex])nex++;
		R.pb(nex-cur);
		cur=nex;
	}
	if(S.back()=='0')R.pb(0);

	vint acc(R.size()+1);
	rep(i,R.size())acc[i+1]=acc[i]+R[i];
	if(R.size()<=2*K+1){
		cout<<N<<endl;
		return 0;
	}
	int ans=0;
	for(int i=0;i+2*K+1<=R.size();i+=2)chmax(ans,acc[i+2*K+1]-acc[i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2164
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// 入力値の取得
		String alpha = sc.next();
		
		// 結果の出力
		System.out.println(Character.isUpperCase(alpha.charAt(0))? "A" : "a");
		
		sc.close();
	}
}


Measured memory_bytes: 26860
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using vi = vector<int>;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define show(x) cout << #x << " = " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define YesNo {cout<<"Yes";}else{cout<<"No";}
#define YESNO {cout<<"YES";}else{cout<<"NO";}
#define v(T) vector<T>

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> bool lcmp(const pair<T, T>& l, const pair<T, T>& r) {
  return l.first < r.first;
}
template<class T> istream& operator>>(istream& i, v(T)& v) {
  F0R(j, sz(v)) i >> v[j];
  return i;
}
template<class T> ostream& operator<<(ostream& o, const vector<T>& v) {
  F0R(i, v.size()) {
    o << v[i] << ' ';
  }
  o << newl;
  return o;
}
template<class T1, class T2> ostream& operator<<(ostream& o, const map<T1, T2>& m) {
  for (auto& p : m) {
    o << p.first << ": " << p.second << newl;
  }
  o << newl;
  return o;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, T, A;
  cin >> N >> T >> A;
  T *= 1000;
  A *= 1000;

  int b = 2000000000, c;
  F0R(i, N) {
    int h;
    cin >> h;

    int d = abs(T - h * 6 - A);
    if (d < b) {
      b = d;
      c = i + 1;
    }
  }
  cout << c;
}
#endif


Measured memory_bytes: 3660
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://arc081.contest.atcoder.jp/tasks/arc081_a>
問題文============================================================
 太さが無視できる棒が N 本あります． i 番目の棒の長さは Ai です．
 
 すぬけ君は，これらの棒から 4 本の異なる棒を選び，それらの棒を辺として長方形（正方形を含む）を作りたいです．
 作ることができる最大の長方形の面積を求めてください．
 
=================================================================

解説=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    map<ll,ll> mp;
    for(int i = 0; i < N;i++){
        ll A; cin >> A; mp[A]++;
    }
    vector<pll> ps(mp.begin(),mp.end());
    sort(ps.begin(),ps.end());
    reverse(ps.begin(),ps.end());
    
    ll h = 0,w = 0;
    for(int i = 0; i < (int)ps.size();i++){
        if(ps[i].second >= 4){
            if(h == 0) h = w = ps[i].first;
            else w = ps[i].first;
            break;
        }else if(ps[i].second >= 2){
            if(h == 0){
                h = ps[i].first;
                continue;
            }
            if(w == 0){
                w = ps[i].first;
                break;
            }
        }
    }
    cout << h * w << endl;
	return 0;
}


Measured memory_bytes: 8064
use std::io;

fn contain(num: &usize) -> usize {
        let g1: Vec<usize> = vec![1,3,5,7,8,10,12];
        let g2: Vec<usize> = vec![4,6,9,11];
        if g1.contains(num) {
                0
        } else if g2.contains(num) {
                1
        } else {
                2
        }
}

fn main() {
        let stdin = io::stdin();
        let mut buf = String::new();

        stdin.read_line(&mut buf).unwrap();

        let xy: Vec<usize> = buf.split_whitespace().map(|n| n.parse().unwrap()).collect();

        let a = contain(&xy[0]);
        let b = contain(&xy[1]);

        if a == b {
                println!("Yes");
        } else {
                println!("No");
        }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> P;
typedef pair<ll, ll> PL;
const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}
 

ll n,xx;
const int SIZE = 1e5+10;
ll x[SIZE];
ll mem[SIZE];
vector<ll> sosu;
int main(){
    cin >> n >> xx;
    for(int i = 0; i < n; i++)  cin >> x[i];


    for(int i = 2; i < SIZE-1; i++){
        if(mem[i] == 0){
            sosu.push_back(i);
            for(int j = i; j < SIZE-1; j+=i)   mem[j] = 1;
        }
    }
    
    ll ans = abs(xx-x[0]);
    for(int i = 1; i < n; i++){
        ll big,sma;
        big = max(ans,abs(xx-x[i]));
        sma = min(ans,abs(xx-x[i]));
        ll mod = big%sma;
        while(mod != 0){
            big = sma;
            sma = mod;
            mod = big%sma;
        }
        ans = sma;
    }

    cout << ans << endl;
}

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

int main()
{
    char a[110], b[110], c[110];
    char ans[3] = {'A','B','C'};
    int x = 0, y = 0, z = 0;
    int flag = 0;
    int p=0;
    int mm = 0;
    cin >> a >> b >> c;

    while (1) {
        if (flag == 0) {
            flag = 1;
            x = -1;
            y = -1;
            z = -1;
        }
        if (mm == 0) {
            x++;
            if (a[x] == 'a')mm = 0;
            else if (a[x] == 'b')mm = 1;
            else if (a[x] == 'c')mm = 2;
            if (a[x] == '\0') {
                p = 0;
                break;
            }
        }
        else if (mm == 1) {
            y++;
            if (b[y] == 'a')mm = 0;
            else if (b[y] == 'b')mm = 1;
            else if (b[y] == 'c')mm = 2;
            if (b[y] == '\0') {
                p = 1;
                break;
            }

        }else if (mm == 2) {
            z++;
            if (c[z] == 'a')mm = 0;
            else if (c[z] == 'b')mm = 1;
            else if (c[z] == 'c')mm = 2;
            if (c[z] == '\0') {
                p = 2;
                break;
            }
     
        }
    }

    cout << ans[p] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	char c;
	cin >> c;

	string ret;
	const string str("aiueo");
	if(str.find(c) == string::npos)
		ret = "consonant";
	else
		ret = "vowel";

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
#define INF (1LL<<62)
ll x[2000], y[2000], z[2000], N, M, dp[2000][2000] = {}, res = 0;
ll p[][3] = {
	{ -1, -1, -1 }, { -1, -1,  1 },
	{ -1,  1, -1 }, { -1,  1,  1 },
	{  1, -1, -1 }, {  1, -1,  1 },
	{  1,  1, -1 }, {  1,  1,  1 }
};
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
		cin >> x[i] >> y[i] >> z[i];
	for (int a = 0; a < 8; ++a) {
		for (int w = 0; w <= M; ++w)
			for(int i=0; i<N; ++i)
				dp[i][w] = -INF;
		dp[0][0] = 0;
		for (int i = 0; i < N; ++i) 
			for (int w = 0; w <= M; ++w) 
				dp[i + 1][w] = w
					? max(dp[i][w - 1] + p[a][0] * x[i] + p[a][1] * y[i] + p[a][2] * z[i], dp[i][w])
					: dp[i][w];
		res = max(res, dp[N][M]);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 16128
from collections import deque

N, M = map(int, input().split())
AB = [map(int, input().split()) for _ in range(M)]

# [[], [], [],,,]
links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)
#print('links : ' + str(links))

# [-1, -1,,,,]
result = [-1] * (N + 1)
q = deque([1])

while q:
    i = q.popleft() # 1回目は　i = 1
    #print('links[' + str(i) + '] : ' + str(links[i]))
    for j in links[i]: # j は 部屋j のことで、1回目は部屋1の隣接部屋を示す（links[1]）
        if result[j] == -1:
            result[j] = i	# つまり、1回目は部屋5,6がi=1、つまり部屋1を示す（最短）
            q.append(j)
            #print(q)
print('Yes')
#print('result : ' + str(result))
print('\n'.join(str(i) for i in result[2:]))

Measured memory_bytes: 106360
#include<algorithm>
#include<climits>
#include<functional>
#include<vector>
template<typename T = int, T  LOWEST = INT_MAX, typename F = std::function<T(T, T)>>
class SegmentTree {
public:
  explicit SegmentTree(int n, const F& op = (const int&(*)(const int&, const int&))std::min) : NIL(-1), op_(op) {initialize(n);}
  explicit SegmentTree(const std::vector<T>& list, const F& op = (const int&(*)(const int&, const int&))std::min) : NIL(-1), op_(op) {
    initialize(list.size());
    for(int i = 0; i < list.size(); ++i) update(i, list.at(i));
  }
  const T find(int left, int right) const {return query(left, right + 1, 0, 0, size_);}
  void update(int index, const T& value) {
    int i = index + size_ - 1;
    node_.at(i) = value;
    while((i = parent(i)) != NIL) node_.at(i) = op_(node_.at(left_child(i)), node_.at(right_child(i)));
  }
private:
  void initialize(int n) {
    size_ = 1;
    while(size_ < n) size_ <<= 1;
    node_.assign((size_ << 1) - 1, LOWEST);
  }
  int parent(int node) const {return node == 0 ? NIL : (node - 1) >> 1;}
  int left_child(int node) const {return (node << 1) + 1;}
  int right_child(int node) const {return (node << 1) + 2;}
  const T query(int a, int b, int k, int l, int r) const {
    if(b <= l || r <= a) return  LOWEST;
    if(a <= l && r <= b) return node_.at(k);
    auto vl = query(a, b, left_child(k), l, (l + r) / 2);
    auto vr = query(a, b, right_child(k), (l + r) / 2, r);
    return op_(vl, vr);
  }
  const int NIL;
  int size_;
  std::vector<T> node_;
  F op_;
};

#include<iostream>
using namespace std;
int main() {
  int n, q;
  cin >> n >> q;
  SegmentTree<int> RMQ(n);
  for(int i = 0; i < q; ++i) {
    int com, x, y;
    cin >> com >> x >> y;
    if(com) cout << RMQ.find(x, y) << endl;
    else    RMQ.update(x, y);
  }
}

Measured memory_bytes: 2056
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i<x;i++)
int a[10005],b[10005],c[10005],d[10005];
int main()
{
int n,m;
while(1)
{
	vector<P>y;
	vector<P>z;
	scanf("%d %d",&n,&m); if(!n) return 0;
	int lim=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
		lim=max(lim,d[i]-1);
	}
	int ret=0,ret2=0;
	int prev=INF;
	vector<P>prev2(0);
	for(int i=0;i<=lim;i++)
	{
		y.clear();
		for(int j=0;j<n;j++)
		{
			if(b[j]<=i && i<d[j]) y.pb(mp(a[j],c[j]));
		}
		if(y.empty()) continue;
		sort(y.begin(),y.end());
		int beg=y[0].first;
		int en=y[0].second;
		y.pb(mp(INF,INF));
		z.clear();
		for(int j=1;j<y.size();j++)
		{

			if(en<y[j].first)
			{//cout << beg << " " << en << endl;

				z.pb(mp(beg,en));
				ret+=(en-beg); ret2+=2; //cout << 2 << "HB" <<endl;
				if(i==lim) ret2+=(en-beg);
				if(prev!=i-1)
				{
					ret2+=(en-beg); //cout << en-beg << "HB" <<endl;
				}
				else
				{
					ret2+=(en-beg);
					for(int cur=0;cur<prev2.size();cur++)
					{
//cout << prev2[cur].first << " " << prev2[cur].second << endl;
						ret2-=(max(0,min(en,prev2[cur].second)-max(beg,prev2[cur].first))*2);
//cout << -(max(0,min(en,prev2[cur].second)-max(beg,prev2[cur].first))*2) << "HB" <<endl;
					}
				}
				beg=y[j].first;
				en=y[j].second;
				
			}
			else
			{
				if(y[j].second<=en)
				{
					en=max(en,y[j].second);
				}
				else
				{
					en=max(en,y[j].second);
				}
			}
		}
		for(int cur=0;cur<prev2.size();cur++)
		{//if(i==lim) cout << (prev2[cur].second-prev2[cur].first) << "HB" <<endl;
			ret2+=(prev2[cur].second-prev2[cur].first);

		}
//printf("%d\n",ret2);
		prev=i;
		prev2=z;
	}
	printf("%d\n",ret);
	if(m==2) printf("%d\n",ret2);
}
}

Measured memory_bytes: 1452
#include <bits/stdc++.h>
#include <cstring>
#include <limits>
using namespace std;
#define ll long long int
#define lli long long int
#define fw(i, s, e) for (ll i = s; i < e; ++i)
#define fe(i, s, e) for (ll i = s; i <= e; ++i)
#define fb(i, e, s) for (ll i = e; i >= s; --i)
#define L(T)  \
    ll T;     \
    cin >> T; \
    while (T--)
#define FASTIO                   \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define mem(a, i) memset(a, i, sizeof(a))
#define ld long double
#define endl "\n"
#define in(P) \
    ll P;     \
    cin >> P;
int main()
{
    FASTIO
    // L(T)
    {
        ll ans = 0;
        in(n);
        in(p);
        string s;
        cin >> s;
        vector<ll> cnt(p + 90);
        ll l = s.length();

        if (p == 2)
        {
            fw(i, 0, n)
            {
                if ((s[i] - '0') % 2 == 0)
                {
                    ans += i + 1;
                }
            }
        }
        else if (p == 5)
        {
            fw(i, 0, n)
            {
                if ((s[i] - '0') % 5 == 0)
                    ans += i + 1;
            }
        }
        else
        {
            ll suf = 0;
            // cnt[suf]++;
            ll pot = 1;
            // fb(i, l - 1, 0)
            // {
            //     ll dig = s[i] - '0';
            //     suf += (dig * pot) % p;
            //     pot = 10 * pot % p;
            //     ans += cnt[suf];
            //     cnt[suf]++;
            // }
            map<ll, ll> mp;
            mp[suf]++;
            fb(i, n - 1, 0)
            {
                suf = (suf + (s[i] - '0') * pot) % p;
                ans += mp[suf];
                mp[suf]++;
                pot = 10 * pot % p;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4232
#include<iostream>
using namespace std;
int prime[10000];
int main(){
	int count=0;
	int i=2;
	while(true){
		bool t=true;
		for(int j=0;j<count;j++){
			if(i%prime[j]==0)
				t=false;
		}
		if(t==true){
			prime[count]=i;
			count++;
		}
		i++;
		if(i==10000)
			break;
	}
	int n;
	while(true){
	cin>>n;
	if(n==0)break;
	int bef,aft;
	bef=n;
	while(true){
		bool t=true;
		for(int i=0;i<count;i++){
			if(bef%prime[i]==0&&bef!=prime[i])
				t=false;
		}
		if(t==true)
			break;
		bef--;
	}
	aft=n;
	while(true){
		bool t=true;
		for(int i=0;i<count;i++){
			if(aft%prime[i]==0&&aft!=prime[i])
				t=false;
		}
		if(t==true)
			break;
		aft++;
	}
	cout<<aft-bef<<endl;
	}
	return 0;
}

Measured memory_bytes: 1168
using System;
using System.Collections.Generic;
using System.Linq;

class C
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var r = new int[n].Select(_ => Read()).ToArray();
		var b = new int[n].Select(_ => Read()).ToArray();

		int sv = 2 * n, ev = sv + 1;
		var dag = new List<long[]>();
		dag.AddRange(Enumerable.Range(0, n).Select(i => new[] { sv, i, 1L }));
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (r[i][0] < b[j][0] && r[i][1] < b[j][1])
					dag.Add(new[] { i, n + j, 1L });
		dag.AddRange(Enumerable.Range(n, n).Select(j => new[] { j, ev, 1L }));

		Console.WriteLine(MaxFlow(ev, sv, ev, dag.ToArray()));
	}

	static long MaxFlow(int n, int sv, int ev, long[][] dag)
	{
		var map = Array.ConvertAll(new int[n + 1], _ => new List<long[]>());
		foreach (var e in dag)
		{
			map[e[0]].Add(new[] { e[0], e[1], e[2], map[e[1]].Count });
			map[e[1]].Add(new[] { e[1], e[0], 0, map[e[0]].Count - 1 });
		}

		long Bfs()
		{
			var from = new long[n + 1][];
			var minFlow = new long[n + 1];
			Array.Fill(minFlow, long.MaxValue);
			var q = new Queue<long>();
			q.Enqueue(sv);

			while (q.TryDequeue(out var v))
			{
				if (v == ev) break;
				foreach (var e in map[v])
				{
					if (from[e[1]] != null || e[2] == 0) continue;
					from[e[1]] = e;
					minFlow[e[1]] = Math.Min(minFlow[v], e[2]);
					q.Enqueue(e[1]);
				}
			}

			if (from[ev] == null) return 0;
			for (long v = ev; v != sv; v = from[v][0])
			{
				var e = from[v];
				e[2] -= minFlow[ev];
				map[e[1]][(int)e[3]][2] += minFlow[ev];
			}
			return minFlow[ev];
		}

		long M = 0, t;
		while ((t = Bfs()) > 0) M += t;
		return M;
	}
}


Measured memory_bytes: 29736
#include <bits/stdc++.h>
using namespace std;
signed main(void){
	int n,k=0;
	cin>>n;
	int a[n][2];
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1];
		if(a[i][0]==a[i][1]) k++;
		else k=0;
		if(k==3){
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORT_ALL(v) sort(ALL(v))
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define DMP(x)  cerr << #x << " = " << (x) << endl;
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define CLR(a) memset((a), 0 ,sizeof(a))
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<std::string> vs;
struct aaa{
    aaa(){
        std::cin.tie(0); std::ios::sync_with_stdio(0); std::cout<<std::fixed<<std::setprecision(20);
    };
}aaaaaaa;

class UnionFind {
private:
    vll _par;
    vll _rank;
public:
    UnionFind(const ll n);
    ll root(const ll n);
    bool unite(ll x, ll y);
    bool same(const ll x, const ll y);
};

UnionFind::UnionFind(const ll n) : _par(n), _rank(n, 1LL) {
    REP(i,n) {
        _par[i] = i;
    }
}

ll UnionFind::root(const ll x) {
    if(_par[x] == x) return x;
    else return _par[x] = root(_par[x]);
}

bool UnionFind::unite(ll x, ll y) {
    x = root(x);
    y = root(y);
    if(x == y) return false;
    if(_rank[x] < _rank[y]) _par[x] = y;
    else {
        _par[y] = x;
        if(_rank[x] == _rank[y]) _rank[x]++;
    }
    return true;
}

bool UnionFind::same(const ll x, const ll y) {
    return root(x) == root(y);
}

int main() {
    int n, k, l;
    cin >> n >> k >> l;
    UnionFind ufr(n), ufl(n);
    REP(i, k) {
        int p, q;
        cin >> p >> q;
        ufr.unite(p - 1, q - 1);
    }
    vi a(n,1);
    REP(i, l) {
        int r, s;
        cin >> r >> s;
        ufl.unite(r - 1, s - 1);
    }

    map<pair<int, int>, int> ans;
    vector<pair<int, int>> p(n);
    REP(i, n) {
        p[i].first = ufr.root(i);
        p[i].second = ufl.root(i);
        ans[p[i]]++;
    }
    REP(i, n) {
        if(i != n - 1) cout << ans[p[i]] << " ";
        else cout << ans[p[i]] << "\n";
    }

    return 0;
}


Measured memory_bytes: 20352
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
			String[] spl = br.readLine().split(" ");
			int a = Integer.parseInt(spl[0]);
			int b = Integer.parseInt(spl[1]);
			int c = Integer.parseInt(spl[2]);
			Set<Integer> set = new HashSet<>();
			set.add(a);
			set.add(b);
			set.add(c);
			System.out.println(set.size());
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 20692
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;

signed main(){
	int n; cin >> n;
	string s; cin >> s;
	int q; cin >> q;
	vector<set<int> > SET(26, set<int> {INF});
	for(int i = 0; i < n; i++) SET[s[i] - 'a'].insert(i);
	for(int i = 0; i < q; i++){
		int type; cin >> type;
		if(type == 1){
			int l; cin >> l; char c; cin >> c; --l;
			if(s[l] != c){
			  SET[s[l] - 'a'].erase(l);
			  SET[c - 'a'].insert(l);
			  s[l] = c;
			}
		}
		if(type == 2){
			int l, r; cin >> l >> r; --l;
			int c = 0;
			for(int j = 0; j < 26; j++){
				if(SET[j].empty()) continue;
				if(*SET[j].lower_bound(l) < r) c++;
			}
			cout << c << endl;
		}
	}
}


Measured memory_bytes: 24196
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
// using namespace std;

int main(){
    using std:: string;

    int a,b;
    std::cin >> a >> b;

    string s;

    std::cin >> s;

    if(s[a] == '-'){
        if(std::all_of(s.begin(), s.begin()+a-1, isdigit)){
            if(std::all_of(s.begin()+a+1, s.end(), isdigit)) std::cout << "Yes" << std::endl;
            else std::cout  <<"No" << std::endl;
        }
        else std::cout  <<"No" << std::endl;
    }
    else std::cout  <<"No" << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
 int w[100001];
 int fd(int a){
 	if(w[a]!=a)w[a]=fd(w[a]);
 	return w[a];
 	
 }
 void uin(int x,int y){
w[fd(x)]=fd(y);
 }
 int main(){
 int i,j,k,l,m,n,p[100001];
 scanf("%d%d",&n,&m);
 for(i=1;i<=n;i++){scanf("%d",&p[i]);w[i]=i;}
 while(m--){
scanf("%d%d",&j,&k);
uin(j,k);
 }
 int ans=0;
 for(i=1;i<=n;i++){
 	if(fd(i)==fd(p[i])){ans++;
 	
	 }
 }
 printf("%d",ans);
 return 0;
}
 	
 	
 	
 	
 	
 	
 	
 

Measured memory_bytes: 896
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    s =input()
    if  "AC" in s:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 3828
#include <iostream>
using namespace std;
#define MOD 1000000007
int main(){
  int n;cin>>n;
  char A[2][n];
  for(int i = 0; 2 > i; i++){
    for(int j = 0; n > j; j++){
      cin>>A[i][j];
    }
  }
  long long ans = 1;
  bool nw = true;
  for(int i = 0; n > i; i++){
    if(A[0][i] != A[1][i]){
      if(!i){
        ans = 6;
      }else{
        if(nw){
          ans = (ans*3)%MOD;
        }else{
          ans = (ans*2)%MOD;
        }
      }
      i++;
      nw = true;
    }else{
      if(!i){
        ans = 3;
      }else{
        if(!nw)ans = (ans*2)%MOD;
      }
      nw = false;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

// https://atcoder.jp/contests/abc160/tasks/abc1160_c
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int n = sc.nextInt();
		int[] array = new int[n];
		for(int i=0;i<n;i++) {
			array[i] = sc.nextInt();
		}
		sc.close();

		int ans = Math.min(k, k - array[0]);
		//時計回り
		for(int i=1;i<array.length;i++) {
			ans = Math.min(ans, k-array[i]+array[i-1]);
		}

		ans = Math.min(ans, array[n-1] - array[0]);
		//反時計回り
		for(int i=0;i<array.length-1;i++) {
			ans = Math.min(ans, array[i]+k-array[i+1]);
		}

		System.out.println(ans);

	}
}


Measured memory_bytes: 64748
#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 TOSTRING(x) #x
#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;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 2e18;
const double PI = acos(-1);

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


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

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] march = new long[5];
		String s;
		for(int i = 0; i < n; i++) {
			s = sc.next();
			if(s.charAt(0) == 'M') march[0]++;
			if(s.charAt(0) == 'A') march[1]++;
			if(s.charAt(0) == 'R') march[2]++;
			if(s.charAt(0) == 'C') march[3]++;
			if(s.charAt(0) == 'H') march[4]++;
		}
		int[][] num = {{0,1,2},{0,1,3},{0,1,4},{0,2,3},{0,2,4},{0,3,4},{1,2,3},{1,3,4},{1,2,4},{2,3,4}};
		
		long ans = 0;
		for(int i = 0; i < 10; i++) {
			ans += march[num[i][0]]*march[num[i][1]]*march[num[i][2]];
		}
		System.out.println(ans);
		
		sc.close();
	}
	

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	long combination(int n, int r, int m) { //nCr mod m
		long[][] Combination = new long[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Combination[i][0] = 1;
			for (int j = 1; j <= i; j++) {
				Combination[i][j] = (Combination[i - 1][j - 1] + Combination[i - 1][j]) % m;
			}
		}
		return Combination[n][r];
	}

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

	public static void main(String[] args) {
		new Main().run();
	}
}


Measured memory_bytes: 47092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair < ll, ll > PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll MOD = 1e9+7;
int main() {
    string s;
    cin >> s;
    int l = 0;
    int r = s.length()-1;
    bool ok = true;
    int cnt = 0;
    while (l <= r) {
        if ( s[l] == s[r] ) {
            ++l;
            --r;
            continue;
        }
        else if ( s[l] == 'x' ) {
            ++l;
            ++cnt;
            continue;
        }
        else if ( s[r] == 'x' ) {
            --r;
            ++cnt;
            continue;
        }
        else {
            ok = false;
            break;
        }
    }
    if ( !ok ) cout << -1 << endl;
    else       cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 512
n = int(input())
a = list(map(int,input().split()))
to = abs(a[0]) + abs(a[-1])

for i in range(n-1):
    to += abs(a[i] - a[i+1])

print(to - abs(a[0]) - abs(a[0]-a[1]) + abs(a[1]))
for i in range(1,n-1):
    print(to - abs(a[i-1] - a[i]) - abs(a[i] - a[i+1]) + abs(a[i-1] - a[i+1]))
print(to - abs(a[-2]-a[-1]) - abs(a[-1]) + abs(a[-2]))

Measured memory_bytes: 14176
package main

import "fmt"

func main() {
	m := make(map[int]int)
	var t int
	for i := 0; i < 4; i++ {
		fmt.Scan(&t)
		m[t]++
	}
	if m[1] >= 1 && m[9] >= 1 && m[7] >= 1 && m[4] >= 1 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

bool check(ll b, ll n, ll s) {
	ll res = 0;
	ll tmp_n = n;
	while(tmp_n > 0) {
		res += tmp_n % b;
		tmp_n /= b;
	}

	return res == s;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll n, s;
	cin >> n >> s;
	if(n == s) {
		cout << n + 1 << endl;
		return 0;
	}
	for(int b = 2; b <= sqrt(n); b++) {
		if(check(b, n, s)) {
			cout << b << endl;
			return 0;
		}
	}

	ll res = INF;
	for(int p = 1; p < sqrt(n); p++) {
		ll b = (n - s) / p + 1;
		if(b <= sqrt(n)) continue;
		if(check(b, n, s)) {
			res = min(res, b);
		}
	}

	if(res != INF) cout << res << endl;
	else cout << -1 << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct card{
  int x;
  char ch;
  int idx;
  bool operator <= (card a)const{
    if(x<a.x) return 1;
    if(x == a.x) return idx<=a.idx;
    return 0;
  }
};


int partition(card A[],int p,int r){
  card x = A[r];
  int i = p - 1;
  for(int j=p; j<r; j++)
    if(A[j] <= x) swap(A[++i],A[j]);
  swap(A[i+1],A[r]);
  return i+1;
}

void quickSort(card A[],int p,int r){
  if(p>=r)return;
  int q = partition(A,p,r);
  quickSort(A,p,q-1);
  quickSort(A,q+1,r);
  
}

bool same(card A[],card B[],int n){
  for(int i=0;i<n;i++)if(A[i].ch!=B[i].ch) return 0;
  return 1;
}

int main(){

  int n;
  cin>>n;
  card A[100010],B[100010];
  for(int i=0;i<n;i++)cin>>A[i].ch>>A[i].x,A[i].idx = 0;
  for(int i=0;i<n;i++)B[i] = A[i],B[i].idx = i;
  quickSort(A,0,n-1);
  quickSort(B,0,n-1);
  cout<<(same(A,B,n)? "Stable":"Not stable")<<endl;
  for(int i=0;i<n;i++)cout<<A[i].ch<<" "<<A[i].x<<endl;


  return 0;
}

Measured memory_bytes: 5404
import Control.Applicative
import Data.List

getIntList = fmap read . words <$> getLine

getIntCont = fmap read . lines <$> getContents

main = print =<< sol <$> getIntList <*> getIntCont

sol :: [Int] -> [Int] -> Int
sol [_, a, b] = foldl' (\s t -> if t < a || t >= b then s+1 else s) 0 


Measured memory_bytes: 1020
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int n,q;

vector<int> cnt;
vector<vector<int> > to;
vector<bool> done;

void dfs(int id,int bef_cnt)
{
	done[id]=true;
	cnt[id]+=bef_cnt;

	for(int i=0;i<to[id].size();i++)
	{
		if(done[to[id][i]]!=true)
			dfs(to[id][i],cnt[id]);
	}
}


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

	cnt=vector<int>(n,0);
	to=vector<vector<int> >(n);
	done=vector<bool>(n,false);

	for(int i=0;i<n-1;i++)
	{
		int a,b;
		cin >> a >> b;
		a--;b--;
		to[a].push_back(b);
		to[b].push_back(a);
	}


	for(int i=0;i<q;i++)
	{
		int p,x;
		cin >> p >> x;
		p--;
		cnt[p]+=x;
	}


	dfs(0,0);


	for(int i=0;i<n;i++)
		cout << cnt[i] << (i==n-1 ? "":" ");
	cout << endl;




}


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

int main() {
  int N, K;
  scanf("%d%d", &N, &K);
  vector<int> l(N, 0);
  for (int i = 0; i < N; i++) cin >> l.at(i);

  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());

  int ans = 0;
  for (int i = 0; i < K; i++) ans += l.at(i);
  printf("%d", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+7;
const int mod = 1e9+7;

int n;
char ch[maxn];

int a1[maxn],a2[maxn];
int main()
{
    
    scanf("%d",&n);
    scanf("%s",ch+1);
    memset(a1,0,sizeof(a1));
    memset(a2,0,sizeof(a2));
    for(int i=1;i<=n;i++){
        a1[i] = a1[i-1] + (ch[i]=='#');
    }
    for(int i=n;i>0;i--){
        a2[i] = a2[i+1] + (ch[i]=='.');
    }
    //for(int i=1;i<=n;i++)cout<<a1[i]<<" ";cout<<endl;
    //for(int i=1;i<=n;i++)cout<<a2[i]<<" ";cout<<endl;
    int ans=n;
    for(int i=0;i<=n;i++){
        ans = min(ans, a1[i]+a2[i+1]);
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int h,l;
int sumn;
int x,y;
int answer[200][200];

int main()
{
    cin>>h>>l>>sumn;
    x=1,y=1;
    for(int i=1; i<=sumn; i++)
    {
        int count;
        cin>>count;
        while(count--)
        {
            answer[x][y]=i;
            if(y==l&&x%2==1)
                {y=l;x++;}
            else if(y==1&&x%2==0)
                {y=1;x++;}
            else if(x&1)
                y++;
            else
                y--;
        }
    }
    for(int i=1; i<=h; i++)
        for(int j=1; j<=l; j++)
            {
			 printf("%d%c",answer[i][j],j==l?'\n':' ');
        	}
    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        System.out.println(((a + b) * c) / 2);
    }
}

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

void run(void){
  int n,k;
  scanf("%d%d",&n,&k);
  int *a=(int *)calloc(n,sizeof(int));
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  int *cnt=(int *)calloc(100000+1,sizeof(int));
  int min=n+1;
  int sum=0,j=0;
  for(i=0;i<n;i++){
    while(j<n && sum<k){
      if(cnt[a[j]]==0 && a[j]<=k) sum++;
      cnt[a[j++]]++;
    }
    if(sum==k && j-i<min) min=j-i;
    if(cnt[a[i]]==1 && a[i]<=k) sum--;
    cnt[a[i]]--;
  }
  printf("%d\n",min==n+1?0:min);
}

int main(void){
  run();
  return 0;
}



Measured memory_bytes: 2576
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct Mat {
  int a, b, c, d;
  Mat(int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {}
};
Mat mul(Mat x, Mat y) {
  return Mat(
    (1LL*x.a*y.a + 1LL*x.b*y.c) % MOD,
    (1LL*x.a*y.b + 1LL*x.b*y.d) % MOD,
    (1LL*x.c*y.a + 1LL*x.d*y.c) % MOD,
    (1LL*x.c*y.b + 1LL*x.d*y.d) % MOD
  );
}
Mat pow(Mat x, long long k) {
  Mat a(1, 0, 0, 1);
  while (k) {
    if (k&1) a = mul(a, x);
    x = mul(x, x);
    k >>= 1;
  }
  return a;
}

int modpow(int x, long long k) {
  int a = 1;
  while (k) {
    if (k&1) a = (1LL*a*x) % MOD;
    x = (1LL*x*x) % MOD;
    k >>= 1;
  }
  return a;
}

int H, W;
long long K;
char A[1000][1000];
char swp[1000][1000];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> H >> W >> K;
  if (K == 0) {
    cout << 1 << "\n";
    return 0;
  }
  rep(y, H) rep(x, W) cin >> A[x][y];
  int black = 0;
  rep(x, W) rep(y, H) black += A[x][y]=='#';

  bool yoko = false, tate = false;
  rep(y, H) if (A[0][y]=='#' && A[W-1][y]=='#') yoko = true;
  rep(x, W) if (A[x][0]=='#' && A[x][H-1]=='#') tate = true;
  if (yoko && tate) {
    cout << 1 << "\n";
  }
  else if (!yoko && !tate) {
    cout << modpow(black, K-1) << "\n";
  }
  else {
    if (tate) {
      rep(y, H) rep(x, W) swp[y][x] = A[x][y];
      swap(W, H);
      swap(swp, A);
    }
    int adj = 0, side = 0;
    rep(x, W-1) rep(y, H) adj += A[x][y]=='#'&&A[x+1][y]=='#';
    rep(y, H) if (A[0][y]=='#' && A[W-1][y]=='#') side++;
    Mat mt = pow(Mat(black, (MOD-adj)%MOD, 0, side), K-1);
    int s = (mt.a+mt.b) % MOD;
    cout << s << "\n";
  }
  return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define db(x) cout<<x<<" "
#define db1(x) cout<<x<<'\n'
#define db2(x,y) cout<<x<<" "<<y<<'\n'
#define db3(x,y,z) cout<<x<<" "<<y<<" "<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define pair(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define ll  long long int
#define vi vector<ll>
#define pi pair<ll,ll>
#define vpi vector<pair<ll,ll>>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mod 1000000007
#define MAX_N 100000
using namespace std;
// int dx[4] = {1,-1,0,0};
// int dy[4] = {0,0,1,-1};


void solve(){

   ll n,k;
   cin>>n>>k;



   vector<ll>arr(n);
   rep(i,n)
   cin>>arr[i];

   vector<vector<ll>>dp(n+1,vector<ll>(k+1));
   repA(i,1,k)
   dp[0][i]=0;

   
   repA(i,0,n)
   dp[i][0]=1;
   //int mod = 1e9+7;

   repA(i,1,n){
    repA(j,1,k){
        dp[i][j] = (dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;;
        if(j-1-arr[i-1]>=0)
        dp[i][j] = (dp[i][j]-dp[i-1][j-1-arr[i-1]]+mod)%mod;
    }
   }
   db1(dp[n][k]);
}
int main(){ 

int t=1;
//cin>>t;
while(t--){
 solve();
}
  return 0; 
}


Measured memory_bytes: 80256
#include <iostream>
using namespace std;
#define MAX 1000000000000000000
typedef long long ll;

int main() {
  ll A;
  string b;
  cin >> A >> b;
  
  ll B = (int)(b[0]-'0') * 100 + (int)(b[2]-'0') * 10 + (int)(b[3]-'0');
  
  cout << A * B / 100 << endl;
  return 0;
}

Measured memory_bytes: 3620
read N; echo 400 599 600 799 800 999 1000 1199 1200 1399 1400 1599 1600 1799 1800 1999 | xargs -n2 | tac | cat -n | sed -E 's/(.+)\t(.+) (.+)/seq \2 \3 | paste - <(yes \1 | head -n200)/g' | bash | grep -P "^$N" | awk '{print $2}'

Measured memory_bytes: 6336
//header{{{
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/math/common_factor_rt.hpp>
  
using namespace std;
//using namespace boost::multiprecision;  
//using namespace boost::math;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

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


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

    int n;
    cin >> n;

    reps(i,n){
        int res = 0;
        for(int j = 1; j * j <= i; ++j){
            for(int k = 1; k * k + j * k <= i; ++k){
                int low = 1, high = n;
                while(high - low > 1){
                    int mid = (high + low) / 2;
                    if(j * j + k * k + mid * mid + j * k + k * mid + mid * j <= i){
                        low = mid;
                    }else{
                        high = mid;
                    }
                }
                if(j * j + k * k + low * low + j * k + k * low + low * j == i){
                    ++res;
                }
            }
        }        
        cout << res << '\n';
    }


    return 0;
}


Measured memory_bytes: 3568
n = int(input())
s = input()

S = set()
cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            dig = 1
            t = str(i)+str(j)+str(k)

            for r in range(n):
                if dig == 1 and t[0] == s[r]:
                    dig +=1

                elif dig == 2 and t[1] == s[r]:
                    dig +=1
                    
                elif dig == 3 and t[2] == s[r]:
                    S.add(t)

print(len(S))

Measured memory_bytes: 74284
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;


int main() {
  ll n; cin >> n;
  vi vec(n);
  
  rep(i,n){
    ll x; cin >> x;
    vec.at(i) = x;
  }
  
  bool flag = true;
  
  rep(i,n){
    if(vec.at(i)%2 == 0&&vec.at(i)%3 !=0&&vec.at(i)%5 != 0){
      cout << "DENIED" << endl;
      flag = false;
      break;
    }
  }
  
  if(flag) cout << "APPROVED" << endl;
}
      

Measured memory_bytes: 256
#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>
#include <climits>

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

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void input() {

    }

    void solve() {
        input();
        int n;
        cin >> n;
        vector<ll> h(n);
        rep(i,0,n) cin >> h[i];
        vector<ll> dp(n + 1, INFl);

        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            ll tmp1 = abs(h[i + 1] - h[i]) + dp[i];
            ll tmp2 = abs(h[i + 2] - h[i]) + dp[i];

            chmin(dp[i + 1], tmp1);
            chmin(dp[i + 2], tmp2);
        }

        cout << dp[n - 1] << endl;


    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 1792