akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<long,long>
#define INF 1000000000000000000
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<int, int> mp;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
class Union_Find {
private:
	vector<int> par;
	vector<int> rank;
public:
	Union_Find(int n) {
		rep(i, n) {
			par.push_back(i);
			rank.push_back(0);
		}
	}
	int find(int x) {
		if (par.at(x) == x) return x;
		else return par.at(x) = find(par.at(x));
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (rank.at(x) < rank.at(y)) {
			par.at(x) = y;
		}
		else {
			par.at(y) = x;
			if (rank.at(x) == rank.at(y)) rank.at(x)++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int>a(n);rep(i, n)cin >> a[i];
	int sum = abs(a[0]);
	for (int i = 0; i < n - 1; i++) {
		sum += abs(a[i] - a[i + 1]);
	}
	sum += abs(a[n - 1]);
	cout << sum + abs(a[1]) - (abs(a[0]) + abs(a[0] - a[1])) << endl;
	for (int i = 0; i < n - 2; i++) {
		cout << sum + abs(a[i] - a[i + 2]) - (abs(a[i] - a[i + 1]) + abs(a[i + 1] - a[i + 2])) << endl;
	}
	cout << sum + abs(a[n - 2]) - (abs(a[n - 2] - a[n - 1]) + abs(a[n - 1])) << endl;
	return 0;
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  if (A + B > C + D) {
    cout << "Left" << endl;
  } else if (A + B == C + D) {
    cout << "Balanced" << endl;
  } else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 3620
def main():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ab = []
    g = []
    for _ in range(n):
        g.append([])
    for _ in range(m):
        a, b = map(int, input().split())
        ab.append([a, b])
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    ans = 0
    for i in range(n):
        check = True
        for j in g[i]:
            if h[j] >= h[i]:
                check = False
        if check:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 45432
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using pii = pair<int, int>;
const int MOD = (int)1e9 + 7, INF = (1 << 27); const ll INFLL = (1LL << 55);
#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
template<typename T, typename U> inline void chmax(T &x, U y) { if (x < y) x = y; }
template<typename T, typename U> inline void chmin(T &x, U y) { if (x > y) x = y; }

int n, a, b;

bool f() {
    scanf("%d%d%d", &n, &a, &b);
    return (b - a) % 2 == 0;
}

int main() {
    puts(f() ? "Alice" : "Borys");
    return 0;
}


Measured memory_bytes: 764
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl = input.ReadLine().Split(' ');
        var h = int.Parse(spl[0]);
        var w = int.Parse(spl[1]);

        var aa = new int[h][];
        for (int i = 0; i < h; i++) {
            aa[i] = ToIntArray(input.ReadLine(), w);
        }

        int coin = 0;
        int count = 0;
        StringBuilder bu = new StringBuilder();

        int preY = -1;
        int preX = -1;

        for (int y = 0; y < h; y++) {
            for (int j = 0; j < w; j++) {
                var x = y % 2 == 0 ? j : (w - j - 1);

                if (coin == 1) {
                    count++;
                    bu.AppendLine($"{preY + 1} {preX + 1} {y + 1} {x + 1}");
                }

                if (aa[y][x] %2 == 1) {
                    if(coin == 0) {
                        coin = 1;
                    } else {
                        coin = 0;
                    }
                }
                preX = x;
                preY = y;
            }
        }

        return count + Environment.NewLine + bu;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 33068
def main():
    N = int(input()) 
    S = input() 
    maxv = 0
    for i in range(1,N-1):
        x = S[0:i]
        y = S[i:N]
        xl = list(set(x))
        yl = list(set(y))
        cnt = 0
        for xx in xl:
            cnt += yl.count(xx)
        maxv = max(maxv,cnt)
    
    print(maxv)






if __name__ == '__main__':
    main()


Measured memory_bytes: 39536
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <queue>
#include <numeric>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)

using namespace std;
using ll = long long;

int main() {

	int n, k, a, sum = 0;
	cin >> n >> k;
	vector<int>x(n);
	rep(i, n) {
		cin >> a;
		a--;
		x[a]++;
	}

	sort(x.begin(), x.end(), greater<>());

	for (int i = 0; i < n; i++) {
		if (i + 1 <= k) {
			sum += x[i];
		}
		else {
			break;
		}
	}

	cout << n - sum;


	return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

int main(){
  int n,p;
  cin>>n>>p;
  long odd=0, even=1;
  rep(i,n){
    int d;
    cin>>d;
    if(d%2==0){
      even = even*2;
      odd = odd*2;
    }
    else {
      long oo = odd, ee = even;
      even = oo+ee;
      odd = oo+ee;
    }
  }

  if(p==0) cout << even << endl;
  else cout << odd << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;
typedef pair<ll, ll> pint;


void yesno(bool b) {
    if (b) {
        cout << "Yes" << endl;
    }     else {
        cout << "No" << endl;
    }

}

int main(){
    int N, M;
    cin >> N >> M;
    int A[M];
    ll ans = 0;
    rep(i, M) {
        cin >> A[i];
        ans += A[i];
    }
    if (N - ans >= 0){
        cout << N - ans << endl;
    } else {
        cout << -1 << endl;
    }


}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vi as(n);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
    }

    vi dp(as);
    using ii = pair<i64, int>;
    for (int i = 0; i < k - 1; i++) {
        deque<ii> deq;
        vi dp2(n);
        for (int j = 0; j < n; j++) {
            // for (int d = 0; d < deq.size(); d++) {
            //     cout << "DEBUG " << deq[d].first << " " << deq[d].second << endl;
            // }

            if (j >= i + 1) {
                dp2[j] = (i + 2) * as[j] + deq.front().first;
            }

            if (deq.size() && deq.front().second <= j - m) {
                deq.pop_front();
            }
            while (deq.size()) {
                if (deq.back().first <= dp[j]) deq.pop_back();
                else break;
            }
            deq.push_back(ii(dp[j], j));
        }
        dp = vi(dp2);
    }
    i64 nax = -1;
    for (int i = 0; i < n; i++) {
        nax = max(nax, dp[i]);
    }
    cout << nax << endl;
}


Measured memory_bytes: 4236
s = input()
q = int(input())
r = 0
S = ['','']
for _ in range(q):
  d = input().split()
  if d[0]=='1':
    r ^= 1
  else:
    S[(int(d[1])+r)%2] += d[2]
s = S[1][::-1] + s + S[0]
if r:
  s = s[::-1]
print(s)

Measured memory_bytes: 10268
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
d = {
    'r': p,
    's': r,
    'p': s
}
point = [None for i in range(n)]
for i in range(len(t)):
    if point[i] == None:
        point[i] = d[t[i]]
        if i + k < len(t) and t[i] == t[i + k]:
            point[i + k] = 0
print(sum(point))

Measured memory_bytes: 4212
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  bool count = false;
  for(int i = 0; i <= N/4; ++i){
    for(int j = 0; j <= N/7; ++j){
      if(i*4 + j*7 == N) count = true;
    }
  }
  if(count) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
N,x=map(int,input().split())
A=sorted(list(map(int,input().split())))
ans=0
for i in range(len(A)):
  if x>=A[i]:
    x-=A[i]
    ans+=1
  else:
    break
else:
  if x>0:
    ans=max(ans-1,0)
print(ans)

Measured memory_bytes: 3060
import java.util.Scanner;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int D = sc.nextInt();
		int X[][] = new int[N][D];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < D; j++) {
				X[i][j] = sc.nextInt();
			}
		}
		
		int ans = 0;
		double t = 0;
		for(int i = 0; i < N; i++) {
			for(int j = i; j < N; j++) {
				t = 0;
				if(i == j) continue;
				for(int k = 0; k < D; k++) {
					t += Math.pow(X[i][k] - X[j][k], 2);
				}
				if(Math.sqrt(t) % 1 == 0) {
					ans++;
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21972
import numpy as np


A = list(map(int, input().split()))
K = A[0]
S = A[1]
counter = 0
for i in range(K+1):
	for j in range(K+1):
		sa = S - (i + j)
		if 0 <= sa and sa <= K:
			counter = counter + 1
			
			
print(counter)
print("\n")

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


int main() {
	long n,m,i,j,k,t,ans,cur,res;
	cin >> n;
	vector<long> a(n);
	for(i=0; i<n; i++){
		cin >> a[i];
	}
	
	vector<long> rhand(n,0),lhand(n,0);
	for(i=0; i<n; i++){
		if(i-a[i]>=0){
			lhand[i-a[i]]++;
		}
		if(i+a[i]<=n-1){
			rhand[i+a[i]]++;
		}
	}
	ans=0;
	
	for(i=0; i<n; i++){
		ans+=lhand[i]*rhand[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8012
#include<bits/stdc++.h>
using namespace std;
priority_queue <pair<long int,long int> > pp;
long int n,m,a,x[100010],t,lag[100010],ans,posi,le,lastans;

int main(){
    for(int i=0;i<100010;i++){
        lag[i]=0;
        x[i]=0;
    }

    cin >> n >> t;
    for(int i=1;i<=n;i++)cin >> x[i];
    for(int i=1;i<=n;i++){
        if(x[i]>x[i-1]&&x[i]>x[i+1]){
            pp.push(make_pair(-(t-x[i]),i));
            i++;
        }
    }
    //cout << pp.top().first << endl;

    while(!pp.empty()){
        posi=pp.top().second;
        le=x[posi];
        x[posi]=0;
        pp.pop();
        ans=t-(le-lag[posi]);
        lastans=max(ans,lastans);
        //cout << ans << endl;
        if(posi>1){
            if(x[posi-1]>x[posi-2]){
                pp.push(make_pair(-(t-x[posi-1]+ans),posi-1));
                lag[posi-1]=ans;
            }
        }
        if(x[posi+1]>x[posi+2]){
            pp.push(make_pair(-(t-x[posi+1]+ans),posi+1));
            lag[posi+1]=ans;
        }
    }

    cout << lastans << endl;

return 0;
}

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

int main() {
	long long n, k,ans;
	cin >> n >> k;
	if (n == 1) {
		cout << k << endl;
		return 0;
	}
	ans = k*pow((k - 1),(n-1));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <cstdlib>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}

vector<ll> fact, factinv, inv;
ll mod = 998244353;
void prenCkModp(ll n) {
	fact.resize(n + 5);
	factinv.resize(n + 5);
	inv.resize(n + 5);
	fact.at(0) = fact.at(1) = 1;
	factinv.at(0) = factinv.at(1) = 1;
	inv.at(1) = 1;
	for (ll i = 2; i < n + 5; i++) {
		fact.at(i) = (fact.at(i - 1) * i) % mod;
		inv.at(i) = mod - (inv.at(mod % i) * (mod / i)) % mod;
		factinv.at(i) = (factinv.at(i - 1) * inv.at(i)) % mod;
	}

}
ll nCk(ll n, ll k) {
	return (fact.at(n) * ((factinv.at(k) * factinv.at(n - k)) % mod)) % mod;
}
int modPow(long long a, long long n, long long p) {
	if (n == 0) return 1; // 0乗にも対応する場合
	if (n == 1) return a % p;
	if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
	long long t = modPow(a, n / 2, p);
	return (t * t) % p;
}

int main() {
	ll N;
	cin >> N;
	ll hu = 0, S = 0,m=1e9+7;
	rep(i, N) {
		ll A;
		cin >> A;
		S += abs(A);
		if (A < 0)hu++;
		m = min(m, abs(A));
	}
	if (hu % 2 == 0) {
		cout << S << endl;
	}
	else {
		cout << S - 2 * m << endl;
	}

}

Measured memory_bytes: 256
import sys
from collections import defaultdict
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

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

    def Unite(self, x, y):
        x_root = self.Find_Root(x)
        y_root = self.Find_Root(y)

        if(x_root == y_root):
            return
        # 違う木に属していた場合rankを見てくっつける方を決める
        if self.rank[x_root] >= self.rank[y_root]:
            self.root[x_root] += self.root[y_root]
            self.root[y_root] = x_root
        else:
            self.root[y_root] += self.root[x_root]
            self.root[x_root] = y_root

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return self.root[self.Find_Root(x)]

n, k, l = map(int, input().split())
pq = [list(map(int, input().split())) for _ in range(k)]
rs = [list(map(int, input().split())) for _ in range(l)]

uf1 = UnionFind(n)
uf2 = UnionFind(n)

for i in range(k):
    uf1.Unite(pq[i][0], pq[i][1])

for i in range(l):
    uf2.Unite(rs[i][0], rs[i][1])

pairs = []
d = defaultdict(int)

for i in range(1, n+1):
    name = "{} {}".format(uf1.Find_Root(i), uf2.Find_Root(i))
    pairs.append(name)
    d[name] += 1

ans = []
for i in range(n):
    ans.append(d[pairs[i]])

print(*ans)




Measured memory_bytes: 86028
import math as m

N,M=map(int,input().split())

if abs(N-M)>=2:
  print(0)
else:
  N,M=max(N,M),min(N,M)
  
  Pm=1
  for i in range(1,M+1):
    Pm*=i
    Pm%=10**9+7

  Pn=1
  for i in range(1,N+1):
    Pn*=i
    Pn%=10**9+7

    
  print((Pm*Pn*1)%(10**9+7) if M!=N else (Pm*Pn*2)%(10**9+7))
 

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
using namespace std;

int main(void) {
	int N, M, L, R, maxL, minR, answer;
	cin >> N >> M;
	cin >> maxL >> minR;
	for (int i = 1; i < M; i++) {
		cin >> L >> R;
		maxL = max(L, maxL);
		minR = min(R, minR);
	}
	answer = minR - maxL + 1;
	if (answer < 0) {
		answer = 0;
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9 + 7;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};
const double pi = acos(-1);
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<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}

ll getsum(vl v){
    ll sum = 0;
    ll ret = 0;
    ll n = v.size();
    REP(i,1,n) sum += v[0] - v[i];
    sum %= mod;
    ret += sum;
    rep(i,n-2){
        ll t = v[i]-v[i+1];
        sum = sum-t - t*(n-2-i);
        while(sum<0) sum += mod;
        ret += sum;
        ret %= mod;
    }
    return ret;
}

int main(){
    ll n,m; cin >> n >> m;
    vl x(n),y(m);
    rep(i,n) cin >> x[i];
    rep(i,m) cin >> y[i];
    reverse(all(x));
    reverse(all(y));
    ll X = getsum(x);
    ll Y = getsum(y);
    cout << X*Y%mod << endl;
}

Measured memory_bytes: 2560
def main():
    n = int(input())
    xyp = [list(map(int,input().split())) for i in range(n)]

    def caldp(a):
        n = len(a)
        a.sort()
        dp = [[float("INF")]*(n+1) for i in range(n+1)]
        dp[0][0] = 0
        for l in range(n):
            for r in range(l+1,n+1):
                now = float("INF")
                for k in range(l,r):
                    count = 0
                    for i in range(l,r):
                        count += abs(a[i][0]-a[k][0])*a[i][1]

                    now = min(now,count)
                for j in range(n):
                    dp[r][j+1] = min(dp[r][j+1],dp[l][j]+now)

                now = 0
                for i in range(l,r):
                    now += abs(a[i][0])*a[i][1]
                for j in range(n+1):
                    dp[r][j] = min(dp[r][j],dp[l][j]+now)

        res = [float("INF")]*(n+1)
        for i in range(n+1):
            res[i] = dp[-1][i]
        return res

    ans = [float("INF")]*(n+1)

    for s in range(1<<n):
        lx = []
        ly = []
        for i in range(n):
            if s >> i & 1:
                lx.append((xyp[i][0],xyp[i][2]))
            else:
                ly.append((xyp[i][1],xyp[i][2]))
        lx = caldp(lx)
        ly = caldp(ly)
        for i in range(len(lx)):
            for j in range(len(ly)):
                ans[i+j] = min(ans[i+j],lx[i]+ly[j])

    for i in ans:
        print(i)

if __name__ == "__main__":
    main()

Measured memory_bytes: 77880
import java.util.*;

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

        String a = sc.nextLine();
        String b = sc.nextLine();

        int[] array_a = new int[a.length()];
        int[] array_b = new int[b.length()];

        int count = 0;
        boolean flag = false;

        for(int i = 0;i < a.length();i++){
            array_a[i] = count;
            for(int j = 0;j < i;j++){
                if(a.charAt(j) == a.charAt(i)){
                    array_a[i] = array_a[j];
                    flag = true;
                    break;
                }
            }
            if (!flag){
                count++;
            }
            flag = false;
        }

        count = 0;
        for(int i = 0;i < b.length();i++){
            array_b[i] = count;
            for(int j = 0;j < i;j++){
                if(b.charAt(j) == b.charAt(i)){
                    array_b[i] = array_b[j];
                    flag = true;
                    break;
                }
            }
            if (!flag){
                count++;
            }
            flag = false;
        }

        for(int i = 0;i < a.length();i++){
            if(array_a[i] != array_b[i]){
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");

//        for(int i = 0;i<a.length();i++){
//            System.out.print(array_a[i]+" ");
//            if(i == a.length()-1)
//                System.out.println("");
//        }
    }
}


Measured memory_bytes: 32400
#include<bits/stdc++.h>
using namespace std;
struct po{
	int h, w, d;
	po(int a, int b, int c){
		h = a;
		w = b;
		d = c;
	}
};
int main(){
	int h, w;
	cin >> h >> w;
	string s[h];
	for(int i = 0; i < h; i++) cin >> s[i];
	int yo = 0;
	for(int i = 0; i < h; i++)for(int j = 0; j < w; j++)yo += (s[i][j] == '#' ? 1 : 0);
	queue<po> q;
	q.push(po(0, 0, 1));
	int dh[] = {1, 0, -1, 0};
	int dw[] = {0, 1, 0, -1};
	bool used[h][w];
	for(int i = 0; i < h; i++)for(int j = 0; j < w; j++)used[i][j] = (i + j > 0 ? 0 : 1);
	while(q.size()){
		po now = q.front();
		q.pop();
		if(now.h == h - 1 && now.w == w - 1){
			cout << h * w - yo - now.d << endl;
			return 0;
		}
		for(int i = 0; i < 4; i++){
			po next = po(now.h + dh[i], now.w + dw[i], now.d + 1);
			if(used[next.h][next.w]) continue;
			if(!(0 <= next.h && next.h < h && 0 <= next.w && next.w < w)) continue;
			if(s[next.h][next.w] == '#') continue;
			used[next.h][next.w] = 1;
			q.push(next);
		}
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb  push_back
using namespace std;
typedef long long ll;
int main(){
    int n; cin >> n;
    int a[n];
    for(int i=0;i<n;i++) cin >> a[i];
    
    vector<int> v;
    
    for(int i=0;i<n;i++){
       if(i%2 == 0){
       	 v.pb(a[i]);
	   }
	   else{
	   	 v.insert(v.begin(),a[i]);
	   }
	}
	
	if(n%2 == 0){
		for(auto i : v) cout << i <<" ";
	}
	else{
    	reverse(v.begin(),v.end());
		for(auto i : v) cout << i <<" ";
	}
	
	return 0;
}

Measured memory_bytes: 3828
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

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

ans=[0]
connect=0
uf=UnionFindVerSize(N)
for i in range(0,M):
    if uf.is_same_group(A[M-1-i]-1,B[M-1-i]-1):
        uf.unite(A[M-1-i]-1,B[M-1-i]-1)
        ans.append(connect)
    else:
        s=uf.get_size(A[M-1-i]-1)
        t=uf.get_size(B[M-1-i]-1)
        uf.unite(A[M-1-i]-1,B[M-1-i]-1)
        u=uf.get_size(A[M-1-i]-1)
        connect+=u*(u-1)//2-s*(s-1)//2-t*(t-1)//2
        ans.append(connect)

for i in range(0,M):
    print(N*(N-1)//2-ans[M-1-i])


Measured memory_bytes: 111852
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

int main() {
    int n, d, x;
    cin >> n >> d >> x;
    vector<vector<int>> p(d, vector<int>(n));
    REP(i, 0, d) {
        REP(j, 0, n) {
            cin >> p[i][j];
        }
    }
    int maxP = 100010;
    REP(i, 0, d - 1) {
        vector<vector<int>> dp(n + 1, vector<int>(maxP, -1));
        dp[0][x] = 0;
        REP(j, 0, n) {
            for (int k = maxP - 1; k >= 0; k--) {
                if (dp[j][k] == -1) continue;
                dp[j + 1][k] = max(dp[j + 1][k], dp[j][k]);
                if (k >= p[i][j]) {
                    dp[j][k - p[i][j]] = max(dp[j][k - p[i][j]], dp[j][k] + p[i + 1][j]);
                }
            }
        }
        int ans = 0;
        REP(k, 0, maxP) {
            if (dp[n][k] != -1) {
                ans = max(ans, dp[n][k] + k);
            }
        }
        x = ans;
    }
    cout << x << endl;
    return 0;
}


Measured memory_bytes: 7648
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] xs = new int[5];
        int ans = 0;
        for(int i=0; i<xs.length; i++) {
            xs[i] = scanner.nextInt();
            if(xs[i] == 0) {
                ans = i+1;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35492
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int k,m,n;
int main(){
	n=read();
	printf("%.6lf\n",(n+1)/2*1.0/n);
	return 0;
}

Measured memory_bytes: 256
S = input()
N = len(S)

odd = ["R", "U", "D"]
even = ["L", "U", "D"]

ans = "Yes"

for i in range(N):
    if (i+1) % 2:
        if S[i] in odd:
            pass
        else:
            ans = "No"
            break
    else:
        if S[i] in even:
            pass
        else:
            ans = "No"
            break

print(ans)

Measured memory_bytes: 3064
main :: IO ()
main = do
  [x1, y1, x2, y2] <- map read . words <$> getLine
  let x = x2 - x1
  let y = y2 - y1
  putStrLn . unwords $ map show [x2 - y, y2 + x, x1 - y, y1 + x]

Measured memory_bytes: 508
#include <iostream>
#include <queue>
#define pii pair<int,int>
#define ppi pair<pii,int>
#define fst first
#define snd second
const int dr[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
using namespace std;
queue<ppi> q;int n,m,mx=0;string mp[1001]={};bool bt[1001][1001]={};
bool isv(pii dt) {return dt.fst>=0&&dt.fst<n&&dt.snd>=0&&dt.snd<m;}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=0;i<n;i++) 
	{
		cin>>mp[i];
		for (int j=0;j<m;j++)
		{
			if (mp[i][j]=='#') {q.push({{i,j},0});}
		}
	}
	while (!q.empty())
	{
		ppi dt = q.front();q.pop();
		if (!bt[dt.fst.fst][dt.fst.snd])
		{
			bt[dt.fst.fst][dt.fst.snd] = 1;
			mx = dt.snd;
			for (int i=0;i<4;i++)
			{
				if (isv({dt.fst.fst+dr[i][0],dt.fst.snd+dr[i][1]})) {q.push({{dt.fst.fst+dr[i][0],dt.fst.snd+dr[i][1]},dt.snd+1});}
			}
		}
	}
	cout<<mx<<"\n";
	return 0;
}

Measured memory_bytes: 50632
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int		long long
#define mp		make_pair
#define pb		push_back
#define pf		push_front
#define fi 		first
#define se		second
#define sz(x)	((int)(x).size())
#define w(x)		int x; cin>>x; while(x--)
#define rep(i,a,n)		for (int i=a;i<n;i++)
#define per(i,a,n)		for (int i=n-1;i>=a;i--)
#define setbits(x)		__builtin_popcountll(x)
#define zrobits(x)		__builtin_ctzll(x)
#define mod		1000000007
#define inf		1e18
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

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

int32_t main(){
	c_p_c(); 
	int n; cin>>n;
	map<int,int> m;
	rep(i,1,n){
		int x; cin>>x;
		m[x]++;
	}
	rep(i,1,n+1){
		cout<<m[i]<<"\n";
	}
	
	return 0;
}


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

using namespace std;

int n, cnt = 0;
string s;
char c;

int main () {
	cin >> n;
	for(int i = 1; i <= 9; i++) {
		if(n % i == 0 && (n / i == 1 || n / i == 2 || n / i == 3 || n / i == 4 || n / i == 5 || n / i == 6 || n / i == 7 || n / i == 8 || n / i == 9)) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

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

int h,w,r,c;

enum DIR { L, U, R, D };
int di[] = { 0, -1, 0, 1 };
int dj[] = { -1, 0, 1, 0 };
char open[510][510][4];
char win[510][510];

bool inner(int i, int j){
    return i >= 0 && j >= 0 && i < h && j < w;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    while(cin >> h >> w >> r >> c && h){
        --r; --c;
        memset(win, 0, sizeof win);
        memset(open, 0, sizeof open);
        rep(i,h*2+1){
            if(i%2 == 0){
                rep(j,w){
                    int x;
                    cin >> x;
                    open[i/2][j][U] = !x;
                    if(i/2) open[i/2-1][j][D] = !x;
                }
            } else {
                rep(j,w+1){
                    int x;
                    cin >> x;
                    open[i/2][j][L] = !x;
                    if(j) open[i/2][j-1][R] = !x;
                }
            }
        }
        queue<pair<int,int>> q;
        rep(i,h)rep(j,w) if(i == 0 || j == 0 || i == h-1 || j == w-1) q.emplace(i,j);
        while(q.size()){
            int ci,cj;
            tie(ci,cj) = q.front();
            q.pop();
            int cnt[2] = {};
            if(win[ci][cj]) continue;
            rep(d,4){
                int ni = ci + di[d];
                int nj = cj + dj[d];
                if(!inner(ni,nj) || win[ni][nj]) ++cnt[open[ci][cj][d]];
            }
            if(cnt[0] && cnt[1]){
                win[ci][cj] = true;
                rep(d,4){
                    int ni = ci + di[d];
                    int nj = cj + dj[d];
                    if(inner(ni,nj) && !win[ni][nj]) q.emplace(ni,nj);
                }
            }
        }
        bool ok = win[r][c];
        rep(d,4){
            int ni = r + di[d];
            int nj = c + dj[d];
            if(open[r][c][d] && (!inner(ni,nj) || win[ni][nj])) ok = true;
        }
        cout << (ok ? "Yes" : "No") << '\n';
    }
}

Measured memory_bytes: 4276
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
int main(){
	while(true){
		int n,cnt=0;
		cin>>n;
		if(n==0) break;
		bool l=false,r=false;
		bool d=true;
		rep(i,n){
			string s;
			cin>>s;
			if(s=="lu") l=true;
			if(s=="ld") l=false;
			if(s=="ru") r=true;
			if(s=="rd") r=false;
			if(d&&l&&r){
				cnt++;
				d=false;
			}else if(!d&&!l&&!r){
				cnt++;
				d=true;
			}
		}
		cout<<cnt<<endl;
	}
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define PI  acos(-1)
#define pb  push_back
#define ins insert
#define INF 1000000000000000007 //1e18+7
#define mk  make_pair
#define lb(v,x) lower_bound(all(v),x)
#define ub(v,x)  upper_bound(all(v),x)
#define ff  first
#define ss  second
#define rev reverse
#define endl "\n"
#define max3(x,y,z)  max(x,max(y,z))
#define min3(x,y,z)  min(x,min(y,z))
#define sz(a) (ll)a.size()
#define double long double
#define minpq  priority_queue <ll,vector<ll>,greater<ll> > 
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define fill(x,y)  memset(x,y,sizeof(x))
#define all(x)   (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bp(n)  __builtin_popcountll(n)
#define mxt(a)  *(max_element(a.begin(),a.end()))
#define mnt(a)  *(min_element(a.begin(),a.end())
#define unique_sort(c) (sort(all(c)), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define trav(a, x) 	  for(auto &a : x)
#define re(i,n)       for(ll i=0;i<n;++i) 
const double eps=1e-7;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
int dx[8]={+1, +1, +1, 0, 0, -1, -1, -1};
int dy[8]={+1, 0, -1, +1, -1, +1, 0, -1};
ll power(ll x,ll y){ll res=1;x=x;while(y>0){if(y&1)res=(res*x);y=y>>1;x=(x*x);}return res;}
ll sqr(ll x) { return x * x;} 
template <typename T> T gcd(T a,T b){ if(a==0) return b; return gcd(b%a,a); }
template <class T> inline void chmax(T &x,T y){ x = max((x), (y));}
template <class T> inline void chmin(T &x,T y){ x = min((x), (y));}
template <class T> T abs(T x) { return x>0 ? x : -x;}
template <typename T> T powm(T a,T b, ll m){T cnt=1; while(b>0){ if(b%2==1) cnt=(cnt*a)%m; b/=2; a=(a*a)%m; }return cnt%m;}
typedef pair<ll,ll>  pii;
typedef vector<pii>  vpii;
typedef vector<ll>   vll;
typedef vector<int>  vii;
ll ncr(ll n,ll r){ll res=1;if(r>n)return 0;if(r>n-r)r=n-r;for(ll i=0;i<r;i++){res*=(n-i);res/=(i+1);}return res;}
const int mod = 998244353;	
const int N = 200005;
void prec(){
	
}
ll n,m,k;
ll ans;
void run(){
	cin>>n>>m>>k;
	vll a(n),b(m),prea(n),preb(m);
	re(i,n) cin>>a[i];
	re(i,m) cin>>b[i];
	prea[0]=a[0],preb[0]=b[0];
	for(int i=1; i<=n-1; ++i) prea[i]=prea[i-1]+a[i];
	for(int i=1; i<=m-1; ++i) preb[i]=preb[i-1]+b[i];
	for(ll i=0; i<=n-1; ++i){
		ll temp=prea[i];
		if(temp>k) continue;
		auto it=upper_bound(all(preb),k-temp);
		ll pos=it-preb.begin();
		chmax(ans,i+pos+1);
	}
	for(ll i=0; i<=m-1; ++i){
		ll temp=preb[i];
		if(temp>k) continue;
		auto it=upper_bound(all(prea),k-temp);
		ll pos=it-prea.begin();
		chmax(ans,i+pos+1);
	}
	cout<<ans<<endl;
}	
int main()
{
    cin.sync_with_stdio(0);cin.tie(0);
	cin.exceptions(cin.failbit);
    int tc=1;
    //cin>>tc;
    prec();
    re(i,tc)
    	run();
    return 0; 
}


Measured memory_bytes: 9512
#include<bits/stdc++.h>
using namespace std;
int n,k,num[200005],gg;
bool p=false;
int main()
{
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&num[i]);
		if(k<=num[i])p=true;
		if(i==1)gg=num[i];
		else gg=__gcd(gg,num[i]);
	}
	if(p&&k%gg==0)printf("POSSIBLE");
	else printf("IMPOSSIBLE");
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool solve(int R, int C){
    vector<vector<pair<int, int>>> gr(R), gc(C);
    int N; cin >> N;
    for(int i=0;i<N;i++){
        int r, c, a; cin >> r >> c >> a;
        gr[r-1].emplace_back(c-1, a);
        gc[c-1].emplace_back(r-1, a);
    }
    vector<long long> dif(R);
    vector<int> check(R, 0);
    for(int i=0;i<R;i++){
        if(check[i]) continue;
        dif[i] = 0;
        check[i] = 1;
        long long m = 1LL << 60;
        auto md = dif[i];
        queue<int> qu; qu.push(i);
        while(!qu.empty()){
            int p = qu.front(); qu.pop();
            for(auto c : gr[p]){
                int val = c.second;
                for(auto r : gc[c.first]){
                    auto d = r.second - c.second + dif[p];
                    if(!check[r.first]){
                        check[r.first] = 1;
                        dif[r.first] = d;
                        qu.push(r.first);
                    }
                    if(dif[r.first] != d) return false;
                    md = min(d, md);
                    m = min(m, r.second - d);
                }
            }
        }
        if(m + md < 0) return false;
    }
    return true;
}

int main(){
    int R, C;
    while(cin >> R >> C){
        cout << (solve(R, C) ? "Yes" : "No") << endl;
    }
}

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

using namespace std;

int main(){
  string S;
  cin >> S;
  
  vector<char> ACGT = {'A','C','G','T'};
  
  int cnt = 0;
  int max = 0;
  bool flg = false;
  
  for(int i = 0; i < S.length(); i++){
    for(char x : ACGT){
      if( S.at(i) == x ){
        cnt++;
        flg = true;
        break;
      }
    }
    if( flg == false || i == S.length() - 1 ){
      if( max < cnt ) max = cnt;
      cnt = 0;
    }else{
      flg = false;
    }
  }
  
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n, s;std::cin >> n >> s;
  ll ans = 1000000000000;
  if(n==s) ans = n+1;
  for(ll i=2;i<=400000;i++){
    ll t = n, k = 0;
    while(t>0){
      k += t % i;
      t /= i;
    }
    if(k==s) ans = min(ans, i);
  }

  for(ll i=1;i<=400000;i++){
    ll t = n / i;
    if(t==0) continue;
    ll p = n % t;
    if((s - i - p)%i==0){
      ll candi = t - (s - i - p)/i;
      if(candi>1&&n/candi==i&&n/candi<candi) ans = min(ans, candi);
    }
  }
  std::cout << (ans==1000000000000?-1:ans) << '\n';
  return 0;
}


Measured memory_bytes: 888
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main{
    static int n;
    static int[] A;
    static int q;
    static int m;
    static boolean ret = false;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        String [] temp = br.readLine().split(" ");
        int max = temp.length;
        A = new int[max];
        for(int i = 0; i < max ; i++){
            A[i] = Integer.parseInt(temp[i]);
        }
 
        q = Integer.parseInt(br.readLine());
 
        temp = br.readLine().split(" ");
        max = temp.length;
        for(int i = 0; i < max ; i++){
            m = Integer.parseInt(temp[i]);
            if(solve(0,m)){
                System.out.println("yes");
            }
            else{
                System.out.println("no");
            }
        }
 
    }
 
    public static boolean solve(int i,int m){
        if(m == 0) return true;
 
        if(i >= n || m < 0) return false;
 
        ret = solve(i+1,m) || solve(i+1,m-A[i]);
        return ret;
    }
 
}

Measured memory_bytes: 24820
using System;
using System.Collections.Generic;
class Solve{
    int N;
    long[] t;
    long[] a;
    public Solve(){}
    public static int Main(){
        new Solve().Calc();
        return 0;
    }
    void Calc(){
        getinput();
        bool[] c = new bool[N];
        long[] d = new long[N];
        long count = 1;
        for(int i=0;i<N;i++){
            c[i] = false;
        }
        d[0] = t[0];
        c[0] = true; 
        for(int i=1;i<N;i++){
            if(t[i] > t[i-1]){
                d[i] = t[i];
                c[i] = true;
            }
        }
        if(c[N-1]){
            if(d[N-1] != a[N-1]){
                Console.WriteLine(0);
                return;
            }
        }
        else{
            c[N-1] = true;
            d[N-1] = a[N-1];
        }
        for(int i=N-2;i>=0;i--){
            if(a[i] > a[i+1]){
                if(c[i]){
                    if(d[i] != a[i]){
                        Console.WriteLine(0);
                        return;
                    }
                }
                else{
                    c[i] = true;
                    d[i] = a[i];
                }
            }
            else if(d[i] > a[i]){
                Console.WriteLine(0);
                return;
            }
        }
        for(int i=0;i<N;i++){
            if(!c[i]){
                long min;
                if(a[i] > t[i]){
                    min = t[i];
                }
                else{
                    min = a[i];
                }
                count = (count*(min%Define.mod))%Define.mod;
            }
        }
        Console.WriteLine(count);
    }
    void getinput(){
        string[] str;
        N = int.Parse(Console.ReadLine());
        a = new long[N];
        t = new long[N];
        str = Console.ReadLine().Split(' ');
        for(int i=0;i<N;i++){
            t[i] = Int64.Parse(str[i]);
        }
        str = Console.ReadLine().Split(' ');
        for(int i=0;i<N;i++){
            a[i] = Int64.Parse(str[i]);
        }
    }    
}
public static class Define{
    public const long mod = 1000000007;
}

Measured memory_bytes: 24416
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define change(a,b) if(a > b) a = b

int dp[110][100100];
int weight[110],value[110];

signed main(){
    int n,w;
    cin >> n >> w;
    for(int i = 0; i < n; i++){
        cin >> weight[i] >> value[i];
    }
    for(int i = 0; i < 110; i++){
        for(int j = 0; j < 100100; j++){
            dp[i][j] = 1ll << 60;
        }
    }
    dp[0][0] = 0;

    for(int i = 0; i < n; i++){
        for(int sumv = 0; sumv < 100100; sumv++){
            if(sumv - value[i] >= 0){
                change(dp[i + 1][sumv], dp[i][sumv - value[i]] + weight[i]);
            }
            change(dp[i + 1][sumv],dp[i][sumv]);
        }
    }
    int res = 0;
    for(int sumv = 0; sumv < 100100; sumv++){
        if(dp[n][sumv] <= w) res = sumv;
    }
    cout << res << endl;
}

Measured memory_bytes: 86272
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int  MAXN = 100001;
typedef long long LL;

LL n, a[MAXN], s[MAXN], l, r, f[MAXN * 2 + 10], b[MAXN], c[MAXN * 2 + 10];

void add(LL x)
{
	while (x <= 2 * MAXN) f[x]++, x += x & -x;
}

LL query(LL x)
{
	LL tot = 0;
	while (x > 0) tot += f[x], x -= x & -x;
	return tot;
}

bool check(LL x)
{
	memset(f, 0, sizeof f);
	for (LL i = 1; i <= n; i++)
	{
		if (a[i] >= x) c[i] = 1;
		else c[i] = -1;
		c[i] += c[i - 1];
	}
	LL ans = 0;
	for (LL i = 0; i <= n; i++)
		ans += (query(c[i] + MAXN)), add(c[i] + MAXN);
	return ans >= n * (n + 1) / 4 ? true : false;
}

int main()
{
	cin >> n;
	for (LL i = 1; i <= n; i++) cin >> a[i], s[i] = a[i];
	sort(s + 1, s + n + 1);
	l = 1, r = n; LL mid;
	while (l <= r)
	{
		mid = l + r >> 1;
		if (check(s[mid])) l = mid + 1;
		else r = mid - 1;
	}
	cout << s[r];

	return 0;
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
//const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
const int dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,-1,0,1,-1,1,-1,1};

const int N=16;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(1){
		string s;
		cin>>s;
		if(s=="#") break;
		int res=inf;
		for(int i=0;i<3;i++) for(int j=i;j<3;j++){
			for(int k=0;k<2;k++){
				int x=i,y=j,tmp=0;
				bool b=k;
				for(int l=0;l<s.size();l++){
					int nx=s[l]-'0';
					if(nx==1) nx=0;
					else if(nx==2) nx=1;
					else if(nx==3) nx=2;
					else if(nx==4) nx=0;
					else if(nx==5) nx=1;
					else if(nx==6) nx=2;
					else if(nx==7) nx=0;
					else if(nx==8) nx=1;
					else if(nx==9) nx=2;
					if(b){
						if(nx>y){
							tmp++;
							y=nx;
						}
						else x=nx,b^=1;
					}
					else{
						if(nx<x){
							tmp++;
							x=nx;
						}
						else y=nx,b^=1;
					}
				}
//				if(s=="783") cout<<i<<' '<<j<<' '<<k<<' '<<tmp<<endl;
				res=min(res,tmp);
			}
		}
		cout<<res<<endl;
	}
}


Measured memory_bytes: 3324
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
int main(){
    long long N;
    cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    long long ans = 1;
    vector<long long> v(3, 0);
    for(int i = 0; i < N; i++){
        long long cnt = 0;
        int flag = 0;
        for(int j = 0; j < 3; j++){
            if(A[i] == v[j]) {
                cnt++;
                flag = j;
            }
        }
        ans = ans * cnt % MOD;
        v[flag]++;
    }
    cout << ans << endl;
}

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

using namespace std;

int a,b,c,x,cnt;

int main(void){
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> x;

    for(int h = 0; h < a+1; h++){
        if(h*500 > x){
                    break;
        }
        for(int i = 0; i < b+1; i++){
            if(h*500+i*100 > x){
                    break;
            }
            for(int j = 0; j < c+1; j++){
                if(h*500+i*100+j*50 == x){
                   // cout << h << i << j << endl;
                    cnt++;
                    break;
                }
            }
        }
    }

    cout << cnt << endl;

}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

ll H, W, K;
char S[1234][1234];

int main() {

	cin >> H >> W >> K;
	rep(i, H) cin >> S[i];

	int ans = 1123456789;

	rep(bit, 1ll << (H - 1)) {
		int bit_count = 0;
		rep(i, H - 1) if ((bit >> i) & 1) bit_count++;
		int cur_ans = bit_count;

		vector<int> counts(bit_count + 1);
		rep(j, W) {
			int t = 0;
			bool f = false;
			rep(i, H) {
				if (S[i][j] == '1') {
					counts[t]++;
					if (counts[t] > K) f = true;
				}
				if ((bit >> i) & 1) t++;
			}
			if (f) {
				cur_ans++;
				t = 0;
				for (auto& c : counts) c = 0;
				rep(i, H) {
					if (S[i][j] == '1') {
						counts[t]++;
						if (counts[t] > K)
							cur_ans = 1123456789;
					}
					if ((bit >> i) & 1) t++;
				}
			}
		}
		ans = min(ans, cur_ans);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384