akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

const int N = 3005;
const int oo = 1e9 + 5;

string s, t;

template <typename T> void max_self(T &a, T b) {
    a = max(a, b);
}

int main() {
    cin >> s >> t;
    vector<vector<pair<int, pair<int,int>>>> dp(s.length() + 1, 
    vector<pair<int, pair<int, int>>>(t.length() + 1, make_pair(-oo, make_pair(0, 0))));
    pair<int, pair<int, int> > ans = {0, {0, 0}};
    dp[0][0] = {0, {0, 0}};
    for (int i = 0; i < s.length(); ++i) {
        for (int j = 0; j < t.length(); ++j) {
            if (s[i] == t[j]) {
                max_self(dp[i + 1][j + 1], {1 + dp[i][j].first, {i, j}});
            }
            max_self(dp[i + 1][j], make_pair(dp[i][j].first, make_pair(i, j)));
            max_self(dp[i][j + 1], make_pair(dp[i][j].first, make_pair(i, j)));
        }
    }
    for (int i = 0; i <= s.length(); ++i) {
        for (int j = 0; j <= t.length(); ++j) {
            max_self(ans, make_pair(dp[i][j].first, make_pair(i, j)));
        }
    }
    pair<int, int> at = ans.second;
    string str = "";
    while(at.first != 0 && at.second != 0) {
        if (dp[at.first][at.second].second == make_pair(at.first - 1, at.second - 1)) {
            assert(s[at.first - 1] == t[at.second - 1]);
            str += s[at.first - 1];
        }
        at = dp[at.first][at.second].second;
    }
    reverse(str.begin(), str.end());
    cout << str << endl;
    return 0;
}

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

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

long long MOD = 10000000000 + 7;

template<typename T>
T gcd(T a, T b) {
  if(a < b) swap(a,b);
    
  if(b == 0) return a;
  return gcd(b, a % b);
}

// 約数列挙 O(√n)
vector<ll> divisor(ll n){
  vector<ll> res;
  for(ll i = 1; i * i <= n; i++){
    if(n % i == 0){
      res.push_back(i);
      if(i != n / i) res.push_back(n / i);
    }
  }
  return res;
}

int main(){
  cout << setprecision(10);
  ll A,B,K; cin >> A >> B >> K;

  ll C = gcd(A, B);
  auto D = divisor(C);
  sort(D.rbegin(), D.rend());
  cout << D[K-1] << endl;
}


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

using namespace std;

#define N 1000001

int main(int argc, char const *argv[])
{
	int a,d,n;

	bool pp[N];
	int cnt;

	pp[0]=true;
	pp[1]=true;

	int i1,i2;

	for(i1=2;i1<N;i1++){
		if(pp[i1]!=true){
			for(i2=2;i2*i1<N;i2++){
				pp[i2*i1]=true;
			}
		}
	}

	while(1){
		cin>>a>>d>>n;
		if(a+d+n==0) break;

		cnt=0;
		while(1){
			if(pp[a]!=true) cnt++;
			if(cnt==n) break;

			a+=d;
		}

		cout<<a<<endl;

	}
	return 0;
}

Measured memory_bytes: 2136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=1005;
int h,w;
char ans[max_n][max_n];
int a,b;
int main(){
    scanf("%d%d",&h,&w);
    scanf("%d%d",&a,&b);
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(i<=b&&j<=a)ans[i][j]='0';
            else if(i<=b&&j>a)ans[i][j]='1';
            else if(i>b&&j>a)ans[i][j]='0';
            else ans[i][j]='1';
        }
        ans[i][w+1]=0;
    }
    for(int i=1;i<=h;i++)printf("%s\n",ans[i]+1);
    return 0;
}

Measured memory_bytes: 2176
//** aman**/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define dl          double
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define lb lower_bound
#define ub upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
vector<ll> g[100005];
ll w[100005],b[100005];
void dfs(ll cu,ll pa){
	w[cu]=1LL;b[cu]=1LL;
	for(auto u:g[cu]){
		if(u==pa)continue;
		dfs(u,cu);
		w[cu]=w[cu]*((w[u]+b[u])%hell)%hell;
		b[cu]=(b[cu]*w[u])%hell;
	}
}
int main(){
	ll n;cin>>n;
	for(ll i=0;i<n-1;i++){
		ll x,y;cin>>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(1,0);
	cout<<(b[1]+w[1])%hell;
	//for(ll i=1;i<=n;i++)cout<<w[i]<<" ";cout<<endl;
	//for(ll i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;
}

Measured memory_bytes: 12800
import java.math.*;
import java.util.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int Y = sc.nextInt();
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    int[] p = new int[A];
    int[] q = new int[B];
    int[] r = new int[C];
    for (int i = 0; i < A; i++) p[i] = sc.nextInt();
    for (int i = 0; i < B; i++) q[i] = sc.nextInt();
    for (int i = 0; i < C; i++) r[i] = sc.nextInt();
    sc.close();

    long ans = IntStream.concat(IntStream.concat(
        Arrays.stream(p).sorted().skip(A - X),
        Arrays.stream(q).sorted().skip(B - Y)),
        Arrays.stream(r))
      .sorted().skip(C)
      .asLongStream()
      .sum();

    System.out.println(ans);
  }
}

Measured memory_bytes: 94788
#include <bits/stdc++.h>
 
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>
#define debug cout << "Ok" << endl;

using namespace std;

int resp[2050],n,x,y;
bitset<2050>verified;
queue<pair<int,int>>q;

void bfs(){
	while(q.empty()==false){
	
	int i = q.front().first;
	int val = q.front().second;
	q.pop();

		if(verified[i]==false){
			verified[i]=true;

			resp[val]++;

			if(i!=1) q.push(make_pair(i-1,val+1));
			if(i!=n) q.push(make_pair(i+1, val+1));
			if(i==x) q.push(make_pair(y,val+1));
			if(i==y) q.push(make_pair(x,val+1));

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

	
	for(int i=0;i<2019;i++){
		resp[i]=0;
	}

	cin >> n >> x >> y;

	for(int i=1;i<=n;i++){

		for(int j= 0;j<n+2;j++){
			verified[j] = false;
		}

		q.push(make_pair(i,0));
		bfs();

	}

	for(int k=1;k<n;k++){
			cout << resp[k]/2 << endl;
	}

	return 0;
}

Measured memory_bytes: 3620
from collections import defaultdict
import queue

def main():
    N,M = [int(x) for x in input().split()]
    vum = defaultdict(list)
    for i in range(M):
        a,b = [int(x) for x in input().split()]
        vum[a].append(b)
        vum[b].append(a)
        
    ### bfs ###
    q = queue.Queue()
    F = [-1]*N # 道標の先の部屋
    s = 1 # 始点
    step = 0
    while True:
        # print('s',str(s))
        for v in vum[s]:
            # print('v',str(v))
            if F[v-1] < 0:
                q.put(v)
                F[v-1] = s
        if q.empty():
            break
        # print(list(q.queue),V)
        s = q.get()

    if -1 in F[1:]:
        print('No')
    else:
        print('Yes')
        for d in F[1:]:
            print(d)

if __name__ == '__main__':
    main()


Measured memory_bytes: 39544
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A3 = list(map(int, input().split()))
bingo_num = []
judge = False
N = int(input())
for i in range(N):
  bingo_num.append(int(input()))
for i in bingo_num:
  for a in range(len(A1)):
    if A1[a] == i:
      A1[a] = -1
  for b in range(len(A2)):
    if A2[b] == i:
      A2[b] = -1
  for c in range(len(A3)):
    if A3[c] == i:
      A3[c] = -1
if sum(A1) == -3 or sum(A2) == -3 or sum(A3) == -3:
  judge = True
for i in range(len(A1)):
  if A1[i] + A2[i] + A3[i] == -3:
    judge = True
if A1[0] + A2[1] + A3[2] == -3 or A1[2] + A2[1] + A3[0] == -3:
  judge = True
if judge:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
using namespace std;
bool t[10000000];
bool sosu[10000000];
const int MA=8000000;
int table[1000000];
int use[500000];
void eratosu(){
  sosu[0]=1;//1?´???°????????????
  sosu[1]=1;

  int puls=1;
  for(int i=2;i<=MA;i++){
      if(sosu[i]==0){
        //cout<<i<<endl;
        for(int j=i*2;j<=MA;j+=i)sosu[j]=1;
      }
  }
  int cnt=0;
  //for(int i=0;i<100;i++)if(!sosu[i])table[cnt++]=i;
}
int main(){
  //eratosu();
  int n,m;
  while(cin>>m>>n,n||m){
    for(int i=0;i<MA;i++)sosu[i]=t[i]=0;
    for(int i=0;i<500000;i++)use[i]=0;

  int cnt=0;
  for(int i=m;i<MA;i++){
    if(cnt>=n)break;
    if(sosu[i]==0){
        use[cnt++]=i;
        sosu[i]=1;
      for(int j=i*2;j<MA;j+=i)sosu[j]=1;
    }
  }


  for(int i=0;i<cnt;i++){
    for(int j=1;j*use[i]<MA;j++)t[use[i]*j]=1;

  }

  int i=0;
  while(t[i]==0)i++;
  for(;i<MA;i++){
    if(t[i]==0){
      cout<<i<<endl;
      break;
    }
  }
}
  return 0;
}

Measured memory_bytes: 20656
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
res=[0 for i in range(n)]
cnt=0

def ch():
    global res,cnt,p,a
    my_cnt=0
    for i in range(m):
        pre=0
        for j in range(len(a[i])):
            if j==0: continue
            pre+=res[a[i][j]-1]
        if p[i]==0:
            if pre%2==0:
                my_cnt+=1
        else:
            if pre%2==1:
                my_cnt+=1
    if my_cnt==m:
        #print(res)
        cnt+=1
        
def abc(i):
    global res
    if i==n:
        ch()
    else:
        res[i]=0
        abc(i+1)
        res[i]=1
        abc(i+1)

abc(0)
print(cnt)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);

    for(int i=0; i<N; i++) cin >> A[i];
    B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());

    if (A.size() == B.size()) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 4724
// 解き直し.
// ABC 134解説.
// https://img.atcoder.jp/abc134/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    vector<LL> A(N);
    vector<LL> dp;
    // 解説通りだが, LIS使う必要があるため, 後ろ側から値を保存.
    for(int i = 0; i < N; i++) scanf("%lld", &A[N - i - 1]);
    // for(int i = 0; i < N; i++) printf("%lld ", A[i]);
    
    // 2. 解説通り.
    // -> LIS で 解く必要があるとのこと.
    // -> "広義"単調減少列 との 記載から, lower_bound を upper_bound に 変更.
    dp.push_back(A[0]);
    for(int i = 1; i < N; i++){
        // 2-1. dpテーブル末尾 の 要素(last)以上 の 値(A[i])であれば, dpテーブル に 追加.
        int last = dp.back();
        // if(last < A[i]) dp.push_back(A[i]);
        if(last <= A[i]) dp.push_back(A[i]);    // "広義"用.
        // 2-2. dpテーブル末尾 の 要素(last) より小さな値(A[i])であれば, 
        // dpテーブル上 の 更新場所 を 探索後, dpテーブル を 更新.
        if(last > A[i]){
            // auto it = lower_bound(dp.begin(), dp.end(), A[i]);
            auto it = upper_bound(dp.begin(), dp.end(), A[i]);    // "広義"用.
            int dist = it - dp.begin();
            dp[dist] = A[i];
            // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
            // cout << endl;
        }
    }
    // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
    // cout << endl;
    
    // 3. 出力 ～ 後処理.
    printf("%d\n", dp.size());
    return 0;
    
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

ll mod(ll a, ll b){
  ll ret=a%b;
  if(ret<0) ret+=b;
  return ret;
}

ll modpow(ll a,ll b,ll c){
  ll res=1;
  while(b>0){
    if(b&1) res=mod(res*a,c);
    a=mod(a*a,c);
    b>>=1;
  }
  return res;
}

int main() {
  int n;
  cin>>n;
  if(n%1000==0) cout<<0<<endl;
  else cout<<1000-n%1000<<endl;
  return 0;
}


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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef long long ll;
typedef long double ld;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second

template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

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

    int n, k;
    cin >> n >> k;
    vi p(n), c(n);
    for(auto &z : p)
        cin >> z, --z;
    for(auto &z : c)
        cin >> z;

    ll ans = -1e18;

    for(int i = 0; i < n; ++i)
    {
        int brCik = 0;
        ll sumCik = 0;

        int tren = i;

        while(1)
        {
            ++brCik;
            sumCik += c[tren];
            tren = p[tren];
            if(i == tren)
                break;
        }

        int br = 0;
        ll suma = 0;

        while(1)
        {
            ++br;
            suma += c[tren];

            if(br > k)
                break;

            ll temp = (k - br) / brCik;
            ll temp2 = suma + max(0LL, sumCik) * temp;
            ckmax(ans, temp2);

            tren = p[tren];
            if(tren == i)
                break;
        }
    }

    cout << ans << "\n";
}


Measured memory_bytes: 3676
import java.util.*;

public class Main {
    public static void main(String[] args){
        // Your code here!
        Scanner sc = new Scanner(System.in);
        
        Long a = sc.nextLong();
        Long b = sc.nextLong();
        Long c = sc.nextLong();
        Long d = sc.nextLong();
        
        Long max = Math.max(Math.max(a*c,a*d),Math.max(c*b,d*b));
        System.out.println(max);
    }
}

Measured memory_bytes: 35844
#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
  if(y==0) return x;
  else return gcd(y, x%y);
}
int main() {
  int a,b,c; cin>>a>>b>>c;  
  if(gcd(a,b)==0) cout<<"NO"<<endl;
  else{
    if(c%gcd(a,b)==0)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define MAX 10000003
#define pb push_back
// #define mp make_pair
#define mem(x,y) memset(x,y,sizeof(x))
#define lcm(a,b) (a*b)/__gcd(a,b)
#define set_bit_count(x) __builtin_popcount(x)
#define str_rev(str) reverse(str.begin(),str.end())
#define loop(i,x,y) for(ll i=x;i<y;i++)
#define rloop(i,x,y) for(ll i=x-1;i>=y;i--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    fastio;
    float n;
    cin>>n;
    float ans=n*3.14*2;
    cout << ans << endl;
    return 0;
}

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

const int maxn=5e5+10;

int n,m,d[maxn],pre[maxn],suf[maxn];

int main()
{
#ifdef h10
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	int i,x;
	scanf("%d%d",&n,&pre[0]);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&d[i]);
		pre[i]=min(pre[i-1],abs(pre[i-1]-d[i]));
	}
	suf[n+1]=0;
	for (i=n;i>=1;i--)
		suf[i]=suf[i+1]+(suf[i+1]>=d[i]>>1?d[i]:0);
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d",&x);
		puts(pre[x-1]<=suf[x+1]?"NO":"YES");
	}
}


Measured memory_bytes: 7808
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    K = int(input())

    G = [[0]*(K+1) for _ in range(K+1)]
    for a in range(K+1):
        for b in range(K+1):
            G[a][b] = gcd(a,b)

    res = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                res += G[i][G[j][k]]
    
    print(res)


if __name__ == '__main__':
    main()

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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;
typedef std::queue<long> QI;
#define rep(i,n) for(long i = 0; i < (long)n; ++i)
const double pi = M_PI;
const long mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      long n, a, b; scan(n, a, b);
      LI xs(n); for(long &x : xs) scan(x);
      long res = 0;
      for(long i = 1; i < n; ++i) {
         long x = xs[i-1];
         long y = xs[i];
         res += std::min((y-x)*a, b);
      }
      printf("%ld\n", res);
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}



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

using namespace std;

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,m;
int x[125252];

// key = %m
struct da{
  int sum;
  int bulk;
  map<int,int> sames;
};
da data[125252];

int main(){
  scanf("%d%d",&n,&m);
  REP(i,n)scanf("%d",x+i);
  REP(i,n){
    int v = x[i];
    int key = v%m;
    data[key].sum += 1;
    data[key].sames[v]++;
  }
  REP(i,m){
    map<int,int>::iterator iter = data[i].sames.begin();
    while(iter != data[i].sames.end()){
      int key = iter->first;
      if(iter->second % 2 == 1){
        data[i].sames[key]--;
        data[i].bulk++;
      }
      iter++;
    }
  }
  int ans = 0;
  REP(i,m/2+1){
    if(i == m-i || i == 0){
      // same
      ans += data[i].sum/2;
    }else{
      // different
      int p = i;
      int q = m-i;
      int add = min(data[p].sum, data[q].sum);
      ans += add;
      {
        int y = p;
        int rest = add;
        rest -= min(rest,data[y].bulk);
        for(auto P:data[y].sames){
          int num = P.second;
          int mn = min(rest,num);
          num -= mn;
          rest -= mn;
          ans += num/2;
        }
      }
      {
        int y = q;
        int rest = add;
        rest -= min(rest,data[y].bulk);
        for(auto P:data[y].sames){
          int num = P.second;
          int mn = min(rest,num);
          num -= mn;
          rest -= mn;
          ans += num/2;
        }
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 12160
section = (1, 2, 3, 4)
book = {sec:[[0 for i in range(10)] for j in range(3)] for sec in section}
n = int(input())
for i in range(n):
    b, f, r, v = map(int, input().split())
    book[b][f - 1][r - 1] += v
for sec in section:
    for rl in book[sec]:
        print(' ' + ' '.join(map(str, rl)))
    if sec != 4:
        print('####################')


Measured memory_bytes: 5604
/**
 *    author:  Daredevil666
 *    institution: IIT Patna
**/
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define nl cout<<"\n";
#define ll long long int
#define IOS  ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
ll mod=1e9+7;
char a[7][7],b[7][7];
ll n,m,k;
void copymatrix()
{
    for(ll i=0;i<n;i++)
        for(ll j=0;j<m;j++)
        b[i][j]=a[i][j];
}
void convert(ll p,ll q)
{
    for(ll i=0;i<n;i++)
    {
        if(p&(1<<i))
        {
            for(ll j=0;j<m;j++)
                b[i][j]='$';
        }
    }
    for(ll i=0;i<m;i++)
    {
        if(q&(1<<i))
        {
            for(ll j=0;j<n;j++)
                b[j][i]='$';
        }
    }
}
bool check()
{
    ll cnt=0;
    for(ll i=0;i<n;i++)
{
    for(ll j=0;j<m;j++)
    {
      if(b[i][j]=='#')
        cnt++;
    }
}
if(cnt==k)return true;
else
    return false;
}
int main()
{
IOS
cin>>n>>m>>k;
for(ll i=0;i<n;i++)
{
    for(ll j=0;j<m;j++)
    {
        cin>>a[i][j];
    }
}
ll cnt=0;
for(ll i=0;i<(1<<n);i++)
{
    for(ll j=0;j<(1<<m);j++)
    {
        copymatrix();
        convert(i,j);
        if(check())
            cnt++;
    }
}
cout<<cnt;
return 0;
}


Measured memory_bytes: 3640
#include <iostream>
using namespace std;
int main()
{
  string letter;
  cin >> letter;
  int i = 0;
  int flag = 0;
  int existence = 0;
  for(int i = 0; i < letter.length(); i++){
    if(flag == 0 && letter[i] == 'A'){
      flag = 1;
    }
    if(flag == 1 && letter[i] == 'Z'){
      flag = 0;
      existence = 1;
      cout << "AZ";
    }
  }
  if(existence == 0){
    cout << -1 << endl;
  } else {
    cout << "" << endl;
  }
  return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using namespace std ;
#define mod 1000000007
int main(){
    long long int W, H ;
    cin >> H >> W ;
    vector<vector<char>> Grid( H , vector<char>(W,'.') ) ;
    for( int i = 0 ; i < H ; i++ ){
        for( int j = 0 ; j < W ; j++ ){
            cin >> Grid[i][j] ;
        }
    }
    long long int dp[H][W] ;
    memset( dp, 0, sizeof(dp) ) ;
    for( int i = 0 ; i < W ; i++ ){
        if( Grid[0][i] == '.' ){
            dp[0][i] = 1 ;
        }
        else break ;
    }
    for( int i = 0 ; i < H ; i++ ){
        if( Grid[i][0] == '.' ){
            dp[i][0] = 1 ;
        }
        else break ;
    }
    for( int i = 1 ; i < H ; i++ ){
        for( int j = 1 ; j < W ; j++ ){
            if( Grid[i][j] == '.' ){
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod  ;
            }
        }
    }
    cout << dp[H-1][W-1] ;
    return 0 ;
}

Measured memory_bytes: 9088
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
//const ll MOD=1000000007;
const ll MOD=998244353;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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

//https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

ll mod_pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % MOD;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

int main()
{
  ll N; cin>>N;
  vector<ll> D(N); rep(i,N) cin>>D[i];
  if(D[0]!=0) {cout<<0<<endl; return 0;}
  
  //最大距離の点求める
  ll max_D=-INF;
  rep(i,N) chmax(max_D,D[i]);
  
  //街道
  vector<ll> vec(max_D+1,0); rep(i,N) vec[D[i]]++;
  if(vec[0]!=1) {cout<<0<<endl; return 0;}
  
  ll ans=1; rep(i,max_D) ans=ans*mod_pow(vec[i],vec[i+1])%MOD;
  
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 4768
#include <bits/stdc++.h>
	#include <ext/pb_ds/assoc_container.hpp>
	#include <ext/pb_ds/tree_policy.hpp>
	#define PI 				acos(-1)
	#define mp				make_pair
	#define pb				push_back
	#define all(a)			(a).begin(), (a).end()
	#define sz(a)			a.size()
	#define srt(a)			sort(all(a))
	#define mem(a, h)		memset(a, (h), sizeof(a))
	#define f 				first
	#define s 				second
	#define MOD1			998244353
	#define fore(i, b, e)	for(int i = b; i < e; i++)
	#define forg(i, b, e, m)	for(int i = b; i < e; i+=m)
	int in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

	using namespace std;
	using namespace __gnu_pbds;

	typedef long long 		ll;
	typedef unsigned long long 		ull;
	typedef pair<int, int>  ii;
	typedef vector<int>     vi;
	typedef vector<ii>      vii;
	typedef vector<ll>      vll;
	typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
	//find_by_order kth largest  order_of_key <
	const int tam = 100010;
	const int MOD = 1e9+7;
	const double EPS = 1e-9;

	int main()
	{
		ios::sync_with_stdio(0); cin.tie(0);
		//freopen("qwe.txt", "r", stdin);
		int n;
		cin>>n;
		int ar[n+2];
		ar[0] = ar[n+1] = 0;
		fore(i, 0, n) cin>>ar[i+1];
		int costot = 0;
		fore(i, 0, n+1)
			costot += abs(ar[i] - ar[i+1]);
		fore(i, 1, n+1)
		{
			cout<<costot - abs(ar[i] - ar[i-1]) - abs(ar[i] - ar[i+1]) + abs(ar[i-1] - ar[i+1])<<'\n';
		}
		return 0;
	}

	// read the question correctly (is y a vowel? what are the exact constraints?)
	// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS2

Measured memory_bytes: 1664
for$y(<>=~/ .* /..$`){@_[glob<>]=map[$y,$_],1..$&}$s[$_+$']=$s[$_]+abs((@b=@{$_[$_+$']})[1]-(@a=@{$_[$_]})[1])+abs"@b"-"@a"for 1..9e4;<>;/ /,print$s[$']-$s[$`],$/for<>

Measured memory_bytes: 35072
n = int(input())
a = [list(map(int, input().split())) for _ in range(n-1)]
*a, = zip(*a)
c, s, f = a[0], a[1], a[2]

for l in range(n):
    t = 0
    for k in range(n-1-l):
        t = s[l+k]+(max(0, t-s[l+k])+f[l+k]-1)//f[l+k]*f[l+k]+c[l+k]
    print(t)


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    string s, p;
    cin >> s >> p;
    s += s;

    if (s.find(p) != string::npos)
    {
        OP("Yes")
    }
    else
    {
        OP("No")
    }

    return 0;
}


Measured memory_bytes: 3176
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {
  
  string S,T,U;
  int A,B;
  cin >> S >> T >> A >> B >> U;

  if(S == U) cout << A-1 << " " << B << endl;
  else cout << A << " " << B-1 << endl;
 
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    A, B = map(int, input().split())
    range_min = int(max((A) / 0.08, (B) / 0.1))
    range_max = int(min((A + 1) / 0.08, (B + 1) / 0.1))

    for i in range(range_min, range_max + 1):
        if int(i * 0.08) == A and int(i * 0.1) == B:
            print(i)
            exit(0)
    print(-1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n, r = map(int, input().split())

for i in range(1, r+1):
  if n-r+1 < i:
    print(0)
  else:
    print(cmb(n-r+1,i)*cmb(r-1,i-1)%(10**9+7))

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define endl "\n"
#define pi 3.14159265358979323846264338327950288
#define MODD 1000000000000000000
#define INF -100000000000000
#define ordered_set tree<pair< ll int ,ll  int>, null_type,less<pair<ll int, ll int>>, rb_tree_tag,tree_order_statistics_node_update> 
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
using namespace std;
#define lld long double
using namespace __gnu_pbds;
map<ll int,ll int> mp; 
void primeFactors(ll int n)  
{  
    // Print the number of 2s that divide n  
    while (n % 2 == 0)  
    {  
        mp[2]++;//cout << 2 << " ";  
        n = n/2;  
    }  
  
    // n must be odd at this point. So we can skip  
    // one element (Note i = i +2)  
    for (int i = 3; i <= sqrt(n); i = i + 2)  
    {  
        // While i divides n, print i and divide n  
        while (n % i == 0)  
        {  
            mp[i]++;//cout << i << " ";  
            n = n/i;  
        }  
    }  
  
    // This condition is to handle the case when n  
    // is a prime number greater than 2  
    if (n > 2)  
        mp[n]++;  
}  
int main()
{
    fast;
   // #ifndef ONLINE_JUDGE
   // freopen("input.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);
   // #endif
    ll int n;
    cin>>n;
    primeFactors(n);
    ll int s=0,z,ans=0,i;
    vector<ll int> v;
    for(i=1;i<=100;i++)
    {
        s=s+i;
        v.PB(s);
    }
    for(auto i=mp.begin();i!=mp.end();i++)
    {
        z=i->S;
        ll int q=lower_bound(v.begin(),v.end(),z)-v.begin();
        if(v[q]>z)
        {
            ans+=q;
        }
        else
        {
            ans+=q+1;
        }

    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
using namespace std;
int main()
{
	long n;
	cin>>n;
	long long sum=0;
	for(long int i=1;i<=n;++i)
	{
		if(i%15==0)
		{
			;
		}
		else if(i%3==0)
		{
			;
		}
		else if(i%5==0)
		{
			;
		}
		else
			sum+=i;
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	int h, w; cin >> h >> w;

	vector<vector<char>> a(h + 2, vector<char>(w + 2, 'e'));

	int whiteCount = 0;
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
		cin >> a[i][j];
		if (a[i][j] == '.') {
			whiteCount++;
		}
	}

	// BFS のためのデータ構造
	vector<vector<int>> dist(h + 2, vector<int>(w + 2, -1)); // 全頂点を「未訪問」に初期化
	queue<pair<int, int>> que;

	// 初期条件
	const int sy = 1;
	const int sx = 1;
	dist[sy][sx] = 0;
	que.push({ sy,sx });

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

	// BFS 開始 (キューが空になるまで探索を行う)
	while (!que.empty()) {

		pair<int, int> p = que.front(); // キューから先頭頂点を取り出す
		que.pop();

		// p から辿れるマスをすべて調べる
		for (int i = 0; i < 4; i++) {

			int y_next = p.first + dy[i];
			int x_next = p.second + dx[i];

			if (dist[y_next][x_next] != -1) continue;
			if (a[y_next][x_next] == 'e' || a[y_next][x_next] == '#') continue;

			// 新たなマス { y_next, x_next } について距離情報を更新してキューに追加する
			dist[y_next][x_next] = dist[p.first][p.second] + 1;
			que.push({ y_next, x_next });

		}

	}

	int ans = whiteCount - (dist[h][w] + 1);

	if (dist[h][w] == -1) ans = -1;	

	cout << ans << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
#define LEN(x) ll(x.length()) //lengthをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB emplace_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

int main(){
    string s;
    cin >> s;
    ll ans = 0, cnt = 0;
    REP(i, 3){
        if(s[i] == 'R') cnt++;
        else{
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    ans = max(ans, cnt);
    cout << ans;
    return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <array>
#include <tuple>
#include <random>

using namespace std;
typedef long long int ll;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()

#define INF 10000000000

ll a, b, c, n, m, x, y, z, w, h, ans = 0, cnt = 0, mx = 0, mn = INF;
string s;

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

    cin >> n >> y;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n - i; j++){
            if(10000 * i + 5000 * j + 1000 * (n - i - j) == y){
                cout << i << ' ' << j << ' ' << n - i - j << endl;
                return 0;
            }
        }
    }
    cout << -1 << ' ' << -1 << ' ' << -1 << endl;
}



Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
  a,b = map(int, input().split())
  uf.union(a-1,b-1)
res=-1
for i in range(N):
  res = max(res,uf.size(i))
print(res)
  
  

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


#define INF 1000000000000


signed main()
 {
   int n;
   cin>>n;
   vector<int>a(n);
   vector<int>s(n+1);
   rep(i,n){
     cin>>a.at(i);
     s[a.at(i)]++;
   }
   int sum=0;
   rep(i,n+1){
     sum+=s[i]*(s[i]-1)/2;
   }
   rep(i,n){
     cout<<sum-(s[a[i]]*(s[a[i]]-1)/2)+((s[a[i]]-1)*(s[a[i]]-2)/2)<<endl;
   }
 }


Measured memory_bytes: 5760
#include <stdio.h>

int main(void) {
	char input[3][3];
	char search_c;
	int i, j;
	int flag;

	while(1) {
		flag = 0;
		for(i = 0; i < 3; i++) {
			for(j = 0; j < 3; j++) {
				if(scanf("%c", &input[i][j]) == EOF)
					return 0;
			}
		}

		while(getchar() != '\n');

		for(i = 0; i < 3; i++) {
			search_c = input[i][0];
			if(search_c == 's')
				continue;
			for(j = 1; j < 3; j++) {
				if(search_c != input[i][j])
					break;
			}

			if(j == 3) {
				flag = (int)search_c;
				break;
			}
		}

		if(!flag) {
			for(i = 0; i < 3; i++) {
				search_c = input[0][i];
				if(search_c == 's')
					continue;
				for(j = 1; j < 3; j++) {
					if(search_c != input[j][i])
						break;
				}

				if(j == 3) {
					flag = (int)search_c;
					break;
				}
			}

			if(!flag) {
				search_c = input[0][0];
				if(search_c != 's') {
					for(i = 1; i < 3; i++) {
						if(search_c != input[i][i])
							break;
					}

					if(i == 3) {
						flag = (int)search_c;
					}
				}

				search_c = input[0][2];
				if(search_c != 's') {
					for(i = 1; i < 3; i++) {
						if(search_c != input[i][2 - i])
							break;
					}

					if(i == 3)
						flag = (int)search_c;
				}
			}
		}

		if(flag)
			putchar(flag);
		else
			putchar('d');
		putchar('\n');
	}

	return 0;
}

Measured memory_bytes: 524
#pragma region _head

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<iomanip>
#include<queue>
#include<stack>
#include<numeric>
#include<utility>
#include<regex>

#pragma region _define

#define int LL
#define f(i,a,b) for(LL i=a;i<b;i++)
#define f_vI(v,n) f(i,0,n)cin>>v[i]
#define f_v2I(v1,v2,n) f(i,0,n)cin>>v1[i]>>v2[i]
#define f_v3I(v1,v2,v3,n) f(i,0,n)cin>>v1[i]>>v2[i]>>v3[i]
#define f_vO(v,n) f(i,0,n)cout<<v[i]<<endl
#define ei else if
#define all(a) a.begin(),a.end()
#define size(s) ((LL)s.size())
#define F first
#define S second
#define check() cout<<"! ! !"
#define endl "\n"
#define _y() cout<<"Yes"<<endl
#define _Y() cout<<"YES"<<endl
#define _n() cout<<"No"<<endl
#define _N() cout<<"NO"<<endl
#define int_INF 1<<29
#define ll_INF 1LL<<60
#define MOD 1000000007

#pragma endregion

#pragma region _using

using namespace std;

using LL = long long;
using st = string;
using vi = vector<LL>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<st>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using qi = queue<LL>;
using qc = queue<char>;
using qs = queue<st>;
using si = stack<LL>;
using sc = stack<char>;
using ss = stack<st>;
using pi = pair<LL, LL>;
using mll = map<LL, LL>;
using mcl = map<char, LL>;
using vpi = vector<pi>;

#pragma endregion

void y_n(bool p) {
	p ? _y() : _n();
}

void Y_N(bool p) {
	p ? _Y() : _N();
}

LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b) * b);
}

//素数判定
bool is_prime(int n) {
	for (int i = 2; i*i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

//階乗計算
LL factorial(LL n) {
	LL a = 1, ret = 1;
	while (a < n) {
		a++;
		ret *= a;
		ret %= MOD;
	}
	return ret;
}

#pragma endregion 




/*****************************************************************************/
signed main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	
	int h, w;
	cin >> h >> w;
	vs a(h);
	f(i, 0, h) {
		cin >> a[i];
	}
	vvi dp(h, vi(w, 0));
	dp[0][0] = 1;
	f(i, 0, h) {
		f(j, 0, w) {
			if (i + 1 < h&&a[i + 1][j] == '.') {
				dp[i + 1][j] += dp[i][j];
				dp[i + 1][j] %= MOD;
			}
			if (j + 1 < w&&a[i][j + 1] == '.') {
				dp[i][j + 1] += dp[i][j];
				dp[i][j + 1] %= MOD;
			}
		}
	}
	cout << dp[h - 1][w - 1];
	return 0;
}

Measured memory_bytes: 9216
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define frw(i, a, b) for(int i = a; i < b; i++)
#define fi first
#define se second
#define pb push_back
#define in insert
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) int(a.size())
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define vpii vector<pii>
#define vpiii vector<piii>
#define vpll vector<pll>
#define vplll vector<plll>
#define mo 1000000007
#define mems(a,x) memset(a,x,sizeof(a))
inline ll modpow(ll x,ll n){if(n==0)return 1;if(n==1)return(x%mo);ll u=(modpow(x,n/2));u=(u*u)%mo;if(n%2!=0)u=(u*x%mo)%mo;return u;}
inline ll modinv(ll x){return modpow(x,mo-2);}
inline ll madd(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a+b>=mo)return(a+b)%mo;return(a+b);}
inline ll msub(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;return(((a-b)%mo+mo)%mo);}
inline ll mmul(ll a,ll b){    if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}
inline ll mdiv(ll a,ll bb){if(a>=mo)a=a%mo;ll b=modinv(bb);if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}


int main() {
	ll l,q;
	cin>>l>>q;
	string s;
	cin>>s;
	ll j=0,k=0;
	ll o[l+1];
	ll z[l+1];
	ll i=0;
	while(i<l)
	{
		ll n=0;
		
		while(s[i]=='1'&&i<l)
			{
			n++;
			i++;
			}
			o[j]=n;
			
			j++;
			n=0;

			while(s[i]=='0'&&i<l)
			{
				n++;
				i++;
			}
				z[k]=n;
				
				k++;
				n=0;
				
		
	
			

	
	}
	ll sum=0;
	ll
	 ans=0;
	//cout<<o[0]<<endl;
	for(int i=0;i<k;i++)
	{
		if(i<q)
		{
			if(i==0)
				sum+=o[i];
			//cout<<sum<<" ";
			sum+=z[i];
			//cout<<sum<<" ";
			if(i+1<j)
			sum+=o[i+1];
			ans=max(ans,sum);//cout<<sum<<" ";
		}
		else
		{
			sum+=z[i];
			sum-=z[i-q];
			if(i+1<j)
			sum+=o[i+1];
			sum-=o[i-q];
			ans=max(ans,sum);
			//cout<<sum<<" ";
		}
	}
	cout<<ans;


}


Measured memory_bytes: 1280
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int nn = int.Parse(Console.ReadLine());
            int[] dd = new int[nn];
            for (int i = 0; i<nn; i++)
            {
                dd[i] = int.Parse(Console.ReadLine());
            }

            int[] ddist = dd.Distinct().ToArray();

            Console.WriteLine(ddist.Length);

        }
    }
 }


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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<long long> a(3*n);
    for(int i=0;i<3*n;i++){
        cin >> a[i];
    }

    priority_queue<long long, vector<long long>, greater<long long>> pq1;
    multiset<long long, greater<long long>> ss;


    long long sum_diff = 0;
    long long sum_all = 0;
    long long sum_second_diff = 0;
    long long sum_second_all = 0;

    vector<long long> temp;
    for(int i=0;i<n;i++){
        pq1.push(a[i]);
        sum_all += a[i];
    }
    for(int i=n;i<3*n;i++){
        temp.push_back(a[i]);
        sum_second_all += a[i];
    }
    sort(temp.begin(), temp.end(), greater<long long>());
    for(int i=0;i<n;i++){
        sum_second_diff += temp[i];
        ss.insert(temp[i]);
    }

    long long maxx = sum_all - sum_diff - sum_second_all + sum_second_diff;
    for(int i=n;i<2*n;i++){
        pq1.push(a[i]);
        sum_all += a[i];
        sum_diff += pq1.top();
        pq1.pop();

        long long primary = sum_all - sum_diff;
        
        sum_second_all -= a[i];
        if(!ss.count(a[i])){
            auto poss = ss.end();
            poss--;
            sum_second_diff -= *(poss);
            ss.erase(poss);
        }
        else{
            auto pos = ss.find(a[i]);
            assert(pos != ss.end());
            sum_second_diff -= *pos;
            ss.erase(pos);
        }
        long long second = sum_second_all - sum_second_diff;
        //printf("%lld,%lld,%lld,%lld\n", sum_all, sum_diff, sum_second_all,sum_second_diff);
        maxx = max(maxx, primary - second);

    }
    cout << maxx << endl;

    return 0;
}


Measured memory_bytes: 9584
#include<bits/stdc++.h>
#define mo 998244353
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
int n,m,m1,v,i,j,k,x,a[400005],b[25],bz1[400005][25],bz2[400005][25];
int r[400005][25],l[400005][25],f[400005],g[400005],book[400005],flag;
int minn(int u,int v){
	return u<v?u:v;
}
int maxx(int u,int v){
	return u>v?u:v;
}
int main(){
	n=read();v=read();
	x=v;
	for(i=0;x!=0;i++){
		b[i]=x;
		x>>=1;
	}
	m=i;
	for(i=1;i<=n;i++)
		a[i]=read();
	for(i=1;i<n;i++)
		bz1[i][0]=a[i+1]-a[i];
	for(i=2;i<=n;i++)
		bz2[i][0]=a[i]-a[i-1];
	for(j=1;(1<<j)<n;j++)
		for(i=1;i+(1<<j)<=n;i++)
			bz1[i][j]=maxx(bz1[i][j-1],bz1[i+(1<<(j-1))][j-1]);
	m1=j-1;
	for(j=1;(1<<j)<n;j++)
		for(i=(1<<j)+1;i<=n;i++)
			bz2[i][j]=maxx(bz2[i][j-1],bz2[i-(1<<(j-1))][j-1]);

	for(i=1;i<=n;i++){
		for(j=0;j<m;j++){
			x=i;
			for(k=m1;k>=0;k--)
				if(x+(1<<k)<=n){
					if(bz1[x][k]<=b[j])
						x+=(1<<k);
				}
			r[i][j]=x;
			
			x=i;
			for(k=m1;k>=0;k--)
				if(x-(1<<k)>=1){
					if(bz2[x][k]<=b[j])
						x-=(1<<k);
				}
			l[i][j]=x;
		}
	}
	f[0]=0;
	g[0]=n+1;
	for(i=1;i<(1<<m);i++){
		f[i]=0;
		g[i]=n+1;
		for(j=0;j<m;j++)
			if(i&(1<<j)){
				if(f[i^(1<<j)]==n)
					f[i]=n;
				else
					f[i]=maxx(f[i],j!=0?r[f[i^(1<<j)]+1][j]:f[i^(1<<j)]+1);
				if(g[i^(1<<j)]==1)
					g[i]=1;
				else
					g[i]=minn(g[i],j!=0?l[g[i^(1<<j)]-1][j]:g[i^(1<<j)]-1);
			}
	}
	x=1;
	i=0;
	while(x<=n){
		i++;
		if(i>=30){
			for(i=1;i<=n;i++)
				printf("Impossible\n");
			return 0;
		}
		flag=0;
		for(j=0;j<(1<<m);j++)
			if(f[j]+1>=x&&g[((1<<m)-1)^j]-1<=r[x][0])
				flag=1;
		for(j=x;j<=r[x][0];j++)
			book[j]=flag;
		x=r[x][0]+1;
	}
	for(i=1;i<=n;i++)
		if(book[i]==1)
			printf("Possible\n");
		else
			printf("Impossible\n");
	return 0;
}

Measured memory_bytes: 91776
N = int(input())
H = list(map(int, input().split()))
 
ans = 0
m=0
for i in range(N-1):
  if H[i] >= H[i+1]:
    m+=1
    ans = max(ans, m)
    
  else:
    ans = max(ans, m)
    m=0
    
print(ans)

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

using namespace std;

vector<vector<int> > DpCount;

int main() {
	int sizeT, sizeB;
	string t, b;

	cin >> t >> b;
	sizeT = t.size();
	sizeB = b.size();

	DpCount.clear();
	DpCount.resize(sizeT+1);
	for (int i = 0; i <= sizeT; ++i) {
		DpCount[i].resize(sizeB+1);
		DpCount[i][0] = 1;
	}

	for (int i = 1; i <= sizeT; ++i) {
		for (int j = 1; j <= sizeB; ++j) {
			DpCount[i][j] = DpCount[i - 1][j];
			if (t[i-1] == b[j-1]) {
				DpCount[i][j] += DpCount[i - 1][j - 1];
				DpCount[i][j] %= 1000000007;
			}
		}
	}
	cout << DpCount[sizeT][sizeB] << endl;

	return 0;
}



Measured memory_bytes: 6904
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <numeric>
#include <set>
#include <list>
#include <bitset>
#include <cstdlib>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    vector<int> ans;
    for (int i = *min_element(A.begin(), A.end()); i <= *max_element(A.begin(), A.end()); i++)
    {
        int tmp = 0;
        for (int j = 0; j < N; j++)
        {
            tmp += pow((i - A[j]), 2);
        }
        ans.push_back(tmp);
    }
    cout << *min_element(ans.begin(), ans.end()) << endl;
    return 0;
}

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

using namespace std;

int main(void) {
    double X, Y;
    cin >> X >> Y;
    double a, b;

    b = Y / 2 - X;
    a = X - b;
    //cout << b << " "<< a << " "<< floor(b) << endl;
    if(a < 0 || (floor(b) != b) || b < 0){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
    return 0;
}

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


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


void solve() {
	int n, k; cin >> n >> k;
	string s; cin >> s;
	char previous = '1';
	int ans = 0;
	int ansbuf = 0;
	auto p = s.begin();
	rep(i, s.size()) {
		if (s[i] != previous) {
			if (s[i] == '0') {
				if (k > 0) k--;
				else {
					while (*p == '1') { p++; ansbuf--; }
					while (*p == '0') { p++; ansbuf--; }
				}
			}
			previous = s[i];
		}
		ansbuf++;
		ans = max(ans, ansbuf);
	}

	cout << ans << endl;
}

int main() {


	solve();


	return 0;
}

Measured memory_bytes: 512