akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

//1-indexであることに注意
template <typename T>
struct BIT {
    int n;
    vector<T> data;
    int n_msb;

    BIT(int n) : n(n), data(n + 1, 0) {
        n_msb = 1;
        while (n_msb <= n) n_msb <<= 1;
        n_msb >>= 1;
    }

    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += data[i];
            i -= i & -i;
        }
        return s;
    }

    void add(int i, T x) {
        while (i <= n) {
            data[i] += x;
            i += i & -i;
        }
    }

    // sum(i) >= val となる最小のiを返す
    // ただし、sum(i)は広義単調増加すると仮定
    int lower_bound(T val) {
        if (val <= 0) return 0;

        int res = 0;
        for (int k = n_msb; k > 0; k >>= 1) {
            if (res + k <= n && data[res + k] < val) {
                val -= data[res + k];
                res += k;
            }
        }
        return res + 1;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, q;
    string s;
    cin >> n >> s >> q;
    vector< BIT<int> > bs(26, BIT<int>(n));
    for (int i = 0; i < n; ++i) {
        bs[s[i] - 'a'].add(i + 1, 1);
    }

    for (int i = 0; i < q; ++i) {
        int com;
        cin >> com;
        if (com == 1) {
            int j;
            char c;
            cin >> j >> c;
            --j;
            bs[s[j] - 'a'].add(j + 1, -1);
            bs[c - 'a'].add(j + 1, 1);
            s[j] = c;
        } else {
            int l, r;
            cin >> l >> r;
            --l;

            int ans = 0;
            for (int j = 0; j < 26; ++j) {
                ans += (bs[j].sum(r) > bs[j].sum(l));
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

Measured memory_bytes: 53660
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PLL = pair<ll, ll>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repn(i,n) for(int i = 0; i <= (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define srepn(i,l,n) for(int i = l; i <= (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define drepn(i,n) for(int i = (int)(n); i >= 0; i--)
#define size(s) (int)s.size()
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T = int> using V = vector<T>;
template<class T = int> using VV = vector<V<T>>;
bool isIn(int i, int j, int h, int w) {return i >= 0 && i < h && j >= 0 && j < w;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ep emplace_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};

struct edge {
    int from, to, cost;
};

int f(int n) {
    int ret = 1;
    rep(i, n) ret *= 2;
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int r;
    cin >> r;
    int ll = r;
    int cnt = 0;
    while(ll/2) {
        ll /= 2;
        cnt++;
    }
    V<edge> ans;
    rep(i, cnt) {
        ans.push_back((edge){i+1, i+2, 0});
        ans.push_back((edge){i+1, i+2, f(i)});
    }
    int l = f(cnt);
    r--;
    // 右から攻めるver
    // [l, r] を作る　-> r - l + 1個作る必要がある
    drep(i, cnt) {
        // r - l + 1　は作らないといけない辺の種類,  f(i)の時に作るとf(i)種類追加できる
        if(r - l + 1 >= f(i)) ans.push_back((edge){i + 1, cnt + 1, r - f(i) + 1}), r -= f(i);
    }
    cout << cnt+1 << " " << size(ans) << endl;
    for(auto e : ans) {
        cout << e.from << " " << e.to <<  " " << e.cost << endl;
    }
}

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

int main(){
    int N,K;
    cin >> N >> K;
    long long p = 1;
    for(int i = 1; i <= N; i++){
        if(i==1){
            p *= K;
        }else{
            p *= (K - 1);
        }
        if(p>INT32_MAX){
            p = INT32_MAX;
            break;
        }
    }
    cout << p;
    return 0;
}

Measured memory_bytes: 3604
/*
ID: computerbox --> Huseyn Hajiyev
LANG: C++
TASK: target_mode_on
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define _CRT_SECURE_NO_WARNINGS
//#include <boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;
#define FAST_READ ios_base::sync_with_stdio(0);
#define in freopen("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define COUT(n, a) cout<< fixed << setprecision(a) << n<<endl
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
#define MAXN 2000
//cin.ignore (7777, '\n');

using namespace std;
using namespace __gnu_pbds;

#define debug(args...)(Debugger()) , args
class Debugger
{
  public:
  Debugger(const std::string& _separator=", ") :
  first(true),separator(_separator){}
  template<typename ObjectType>
  Debugger& operator,(const ObjectType& v)
  {
        if(!first)cerr<<separator;
        cerr<<v;
        first=false;
        return *this;
  }
  ~Debugger() {cerr<<endl;}      
  private:
    bool first;
    string separator;
};
 
template <typename T1, typename T2>
inline ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
   return os<<"("<<p.first<<", "<<p.second<<")";
}
template<typename T>
inline ostream &operator<<(ostream & os,const vector<T>& v)
{
    bool first=true;
    os<<"[";
    for(unsigned ll i=0;i<v.size();i++)
    {
        if(!first)os<<", ";
        os<<v[i];
        first=false;
    }
        return os<<"]";
}
template<typename T>
inline ostream &operator<<(ostream & os,const set<T>&v)
{
    bool first=true;
    os<<"[";
    for(typename set<T>::const_iterator ii=v.begin();ii!=v.end();++ii)
    {
        if(!first)os<<", ";
        os<<*ii;
        first=false;
    }
    return os<<"]";
}
template<typename T1, typename T2>
inline ostream &operator<<(ostream & os,const map<T1, T2>&v)
{
        bool first=true;
        os<<"[";
        for(typename map<T1,T2>::const_iterator ii=v.begin(); ii!=v.end();++ii)
        {
            if(!first)os<<", ";
            os<<*ii;
            first=false;
        }
        return os<<"]";
}
ll n,a,b;

int main(){
FAST_READ;
cin>>n>>a>>b;
cout<<min(n*a,b)<<endl;






return 0;
} 


Measured memory_bytes: 256
N = input()
M = int(N)

A = 9**M
a = int(A)
B = 9**M
b = int(B)
C = 8**M
c = int(C)
D = a+b-c
d = int(D)
E = 10**M
e = int(E)
F = e-d
f = int(F)

if M==0:
    print(0)

elif M==1:
    print(0)

elif M==2:
    print(2)

elif M>=3:
    print(f%(10**9+7))


Measured memory_bytes: 12204
import java.util.Scanner;

public class Main {

	static int n, s;
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(true){
			s = cin.nextInt();
			n = cin.nextInt();
			if(s+n==0){
				break;
			}
			System.out.println(saiki(0,0,-1));
		}
	}
	static int saiki(int hukasa, int sum, int before){
		int res = 0;
		if(hukasa==s){
			if(sum == n){
				return 1;
			}
			else{
				return 0;
			}
		}
		for(int i = before+1; i < 10; i++){
			res += saiki(hukasa+1, sum+i, i);
		}
		return res;
	}
}

Measured memory_bytes: 12000
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
  cin>>s;
  if(s[0]=='A')cout<<"T"<<endl;
  if(s[0]=='T')cout<<"A"<<endl;
  if(s[0]=='C')cout<<"G"<<endl;
  if(s[0]=='G')cout<<"C"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
#define CO cout<<
#define EN <<endl
#define CI cin>>
using namespace std;

int main() {
	int a; CI a;
	vector<string> blue;
	REP(i, a) { string tmp; CI tmp; blue.push_back(tmp); }
	int b; CI b;
	vector<string> red;
	REP(i, b) { string tmp; CI tmp; red.push_back(tmp); }

	sort(blue.begin(), blue.end());
	sort(red.begin(), red.end());

	vector<string> sred=red;
	sred.erase(unique(sred.begin(), sred.end()), sred.end());

	vector<string> sblue = blue;
	sblue.erase(unique(sblue.begin(), sblue.end()), sblue.end());

	int ans = 0;
	int ablue;
	int ared;

	vector<string> mincard;
	if (sred.size() < sblue.size())mincard = sblue;
	else mincard = sred;

	REP(i, sblue.size()) {
		ablue=count(blue.begin(), blue.end(), sblue[i]);
		ared=count(red.begin(), red.end(), sblue[i]);
		if (ablue > ared&&ablue - ared>ans)ans = ablue - ared;

	}
	CO ans EN;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

struct point {
	int x,y;
	point(){}
	point(int a, int b) : x(a), y(b) {}
}P[11111];

struct data {
	int a1,a2,t;
	data(){}
	data(int a, int b, int c) : a1(a), a2(b), t(c) {}
};

char B[111][111];
int a[111][111],b[111][111];
int n,m,sz;

vector<data> H,V;
vector<int> adj[11111];
bool seen[11111];
int R[11111];

bool bpm(int u) {
	for(int i=0;i<adj[u].size();++i) {
		int v = adj[u][i];
		if(seen[v]) continue;
		seen[v] = 1;
		if(R[v]==-1 || bpm(R[v])) {
			R[v] = u;
			return 1;
		}
	} return 0;
}

int match() {
	memset(R,-1,sizeof(R));
	int ret = 0;
	for(int u=0;u<H.size();++u) {
		for(int v=0;v<V.size();++v) seen[v]=0;
		if(bpm(u)) ret++;
	} return ret;
}

int main() {
#ifdef LOCAL
	freopen("input.txt","r",stdin);
#endif
	while(1) {
		scanf("%d%d",&n,&m),sz=0;
		if(n==0&&m==0) break;
		memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
		H.clear(),V.clear();
		for(int i=1;i<=n;++i) scanf("%s",B[i]+1);
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
			a[i][j] = a[i][j-1] + (B[i][j]=='#'),
			b[i][j] = b[i-1][j] + (B[i][j]=='#');
		for(int i=1;i<n;++i) for(int j=1;j<m;++j) {
			int cnt = 0;
			for(int di=0;di<2;++di) for(int dj=0;dj<2;++dj)
				cnt += (B[i+di][j+dj] == '#');
			if(cnt == 3) P[sz++] = point(i,j);
		}

		for(int i=0;i<sz;++i) for(int j=i+1;j<sz;++j) {
			if(P[i].x == P[j].x && a[P[i].x][P[j].y]-a[P[i].x][P[i].y]==P[j].y-P[i].y
				&& a[P[i].x+1][P[j].y]-a[P[i].x+1][P[i].y]==P[j].y-P[i].y)
				H.push_back(data(P[i].y,P[j].y,P[i].x));
			if(P[i].y == P[j].y && b[P[j].x][P[i].y]-b[P[i].x][P[i].y]==P[j].x-P[i].x
				&& b[P[j].x][P[i].y+1]-b[P[i].x][P[i].y+1]==P[j].x-P[i].x)
				V.push_back(data(P[i].x,P[j].x,P[i].y));
		}

		for(int i=0;i<H.size();++i) for(int j=0;j<V.size();++j) {
			int x=H[i].t,y=V[j].t;
			int x1=V[j].a1,x2=V[j].a2;
			int y1=H[i].a1,y2=H[i].a2;
			if(x1<=x&&x<=x2&&y1<=y&&y<=y2) adj[i].push_back(j);
		} printf("%d\n",1+sz-(H.size()+V.size()-match()));

		for(int i=0;i<H.size();++i) adj[i].clear();
	}
}

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

int main(){
  int c,ans;
  ans=0;
  int N;
  cin>>N;
  for(int i=1;i<=N;i+=2){
    c=0;
    for(int j=1;j<=i;j++){
      if(i%j==0)c++;
    }
    if(c==8)ans++;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define _for(i,j,k) for(int i=j;i<=k;i++)
#define for_(i,j,k) for(int i=j;i>=k;i--)
#define lowbit(x) (x&-x)
#define ls(x) x<<1
#define rs(x) x<<1|1
#define inf 0x3f3f3f3f
//#pragma comment(linker, "/STACK:10240000000,10240000000")
using namespace std;
template<class T>
inline void read(T& x){
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    x=x*f;
}
template<class T>
inline void write(T x){
    if(x<0){putchar('-'); x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}
const int maxn = 1e5 + 5;
int a[maxn],n,k,q,u;
int main(){
#ifdef ICPC
freopen("C:\\Users\\Administrator\\Desktop\\ACM\\input.txt","r",stdin);
//freopen("C:\\Users\\Administrator\\Desktop\\ACM\\output.txt","w",stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>q;
	_for(i,1,n){
		a[i]=k-q;
	}
	_for(i,1,q){
		cin>>u;
		a[u]++;
	}
	_for(i,1,n){
		if(a[i]>0){
			cout<<"Yes\n";
		}
		else cout<<"No\n";
	}

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string s;
  cin >> s;
  int q;
  cin >> q;
  int size = s.size();
  vector<char> data(50 * q + 50 * size);
  int left = 25 * q + 25 * size;
  int right = left + size - 1;
  rep(i,size) {
    data[left + i] = s[i];
  }
  rep(i,q) {
    int a;
    cin >> a;
    if(a == 1) {
      int n,m;
      n = right;
      m = left;
      right = m;
      left = n;
    }
    else {
      size++;
      int b;
      char c;
      cin >> b >> c;
      if(b == 1) {
        if(left <= right) {
          data[left - 1] = c;
          left--;
        }
        else {
          data[left + 1] = c;
          left++;
        }
      }
      else {
        if(left <= right) {
          data[right + 1] = c;
          right++;
        }
        else {
          data[right - 1] = c;
          right--;
        }
      }
    }
  }
  if(left <= right) {
    rep(i,size) {
      cout << data[left + i];
    }
  }
  else {
    rep(i,size) {
      cout << data[left - i];
    }
  }
  cout << endl;
}


Measured memory_bytes: 15360
def rev(a):
    L = []
    for i in range(N):
        L.append(a % 3)
        a //= 3
    return int("".join(map(str, L)), 3)
    
def salsa():
    lazy[0] *= -1

def rumba():
    i = 0
    for k in range(N):
        if lazy[i] < 0:
            lazy[3*i+1] *= -1
            lazy[3*i+2] *= -1
            lazy[3*i+3] *= -1
            lazy[i] = 1
            value[3*i+1] ^= 3
            value[3*i+2] ^= 3
            value[3*i+3] ^= 3
        value[3*i+1] += 1
        value[3*i+2] += 1
        value[3*i+3] += 1
        value[3*i+1] %= 3
        value[3*i+2] %= 3
        value[3*i+3] %= 3
        i = 3 * i + (1 if value[3*i+1] == 0 else 2 if value[3*i+2] == 0 else 3)

def calcall():
    a = 1
    i = 0
    for k in range(1, N + 1):
        for _ in range(3 ** k):
            i += 1
            if lazy[(i-1)//3] < 0:
                lazy[i] *= -1
                if value[i]: value[i] ^= 3
            value[i] = value[i] * a + value[(i-1) // 3]
        a *= 3
        
N = int(input())
NN = 3 ** (N + 1) // 2
value = [(i-1) % 3 if i else 0 for i in range(NN)]
lazy = [1 for i in range(NN)]

for t in input():
    if t == "R":
        rumba()
    else:
        salsa()

calcall()

ANS = [0] * (3 ** N)
for i in range(3 ** N):
    ANS[rev(i)] = value[i + (NN - 1) // 3]

print(*ANS)

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

int main()
{
	int i,temp;
	string S,T;
	char tem;
	cin>>S>>T;
	for(i=0;i<S.size();i++){
		if(S==T){
			cout<<"Yes";
			break;
		}
		tem=S.at(0);
		S.erase(S.begin());
		S.push_back(tem);
	}
	if(i==S.size()){
		cout<<"No";
	}
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();

		Dice[] ds = new Dice[n];

		for (int i=0; i < n; i++) {
			 String[] label = sc.nextLine().split(" ");
			 ds[i] = new Dice(label);
		}

//		char[] order = "RRRR_SEEE_LSSS_LWWW_LNNN_WLLL".toCharArray();

		boolean flag = true; // flag :all dices are different ?
		loop:
		for (int i=0; i < n; i++) {
			for (int j=i+1; j < n; j++) {

				if ( ds[i].equiv(ds[j]) ) {
					flag = false;
					break loop;
				}

			}
		}

		if (flag) System.out.println("Yes");
		else System.out.println("No");

	}

	static class Dice {
		String top, front, right, left, back, bottom;

		Dice(String[] label) {
			top = label[0];
			front = label[1];
			right = label[2];
			left = label[3];
			back = label[4];
			bottom = label[5];
		}

		Dice move(char c) {
			String temp;
			switch (c) {
			case 'N': // top <- front <- bottom <- back <- top
				temp = top;
				top = front;
				front = bottom;
				bottom = back;
				back = temp;
				break;
			case 'E': // top <- left <- bottom <- right <- top
				temp = top;
				top = left;
				left = bottom;
				bottom = right;
				right = temp;
				break;
			case 'S': // top <- back <- bottom <- front <- top
				temp = top;
				top = back;
				back = bottom;
				bottom = front;
				front = temp;
				break;
			case 'W': // top <- right <- bottom <- left <- top
				temp = top;
				top = right;
				right = bottom;
				bottom = left;
				left = temp;
				break;
			case 'R': // front <- right <- back <- left <- front
				temp = front;
				front = right;
				right = back;
				back = left;
				left = temp;
				break;
			case 'L': // front <- left <- back <- right <- front
				temp = front;
				front = left;
				left = back;
				back = right;
				right = temp;
				break;
			}
			return this;
		}

		boolean match(Dice that) {
			boolean b0 = this.top.equals(that.top);
			boolean b1 = this.front.equals(that.front);
			boolean b2 = this.right.equals(that.right);
			boolean b3 = this.left.equals(that.left);
			boolean b4 = this.back.equals(that.back);
			boolean b5 = this.bottom.equals(that.bottom);

			if (b0 && b1 && b2 && b3 && b4 && b5) return true;
			else return false;
		}

		boolean equiv(Dice that) {

			/* ????????¢??????????????????????????¢???top,front,right,left,back,bottom???
			 * ????????????????????????????????¶?????????????????????????????????????????????????????????
			 * ?????¢??????????????????????????????????????¨?????????????????????6*4???24??????????????????
			 * initial state(top) -> S(front) -> L(right) -> L(back) -> L(left) -> W(bottom)
			 */
			char[] order = ("RRRR" + "SEEE" + "LSSS" + "LWWW" + "LNNN" + "WLLL").toCharArray();

			boolean flag = false;
			for (int i=0; i < order.length; i++) {
				that.move(order[i]);
				if (  this.match(that)  ) {
					flag = true;
					break;
				}
			}

			return flag;
		}
	}

}

Measured memory_bytes: 27932
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int INF = 1 << 30;
int N, K;
int x[100010];
vector<int> pos, neg;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    cin >> x[i];
    if (x[i] < 0) neg.emplace_back(-x[i]);
    else pos.emplace_back(x[i]);
  }
  int ans = (K <= pos.size() ? pos[K-1] : INF);
  if (!neg.empty()) {
    reverse(neg.begin(), neg.end());
    if (K <= neg.size()) {
      ans = min(ans, neg[K-1]);
    }
    for (int i = 0; i < min(K, (int)pos.size()); i++) {
      int rem = K - i - 1;
      if (rem <= neg.size()) {
        ans = min({ans, pos[i]*2+neg[rem-1], pos[i]+neg[rem-1]*2});
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1404
import java.util.Scanner;
class Main{
public static void main(String[]args){

Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int M=sc.nextInt();

int num=0;

for(int n=0;n<M;n++){
int An=sc.nextInt();
N=N-An;
}
if(N>=0){
System.out.println(N);
}else if(N<0){
System.out.println(-1);
}
}
}

Measured memory_bytes: 46376
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
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; }
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    int n;
    cin >> n;
    vector<string> s(n);
    REP(i, n) cin >> s[i];
    
    set<string> st;
    REP(i, n) {
        st.insert(s[i]);
    }

    cout << st.size() << endl;

    return 0;
}

Measured memory_bytes: 25084
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define pp pop_back
#define mp make_pair
#define pb push_back
#define rep(x, a, b) for(int x=a; x<=b; x++)
#define drp(x, a, b) for(int x=a; x>=b; x--)
typedef long long ll;
const int mod=924844033;
const int N=200200;
const int G=5;
int ans[N], n, m, l, rev[N<<2], fac[N], inv[N], f[N<<2], u[N], v[N], g[N<<2], head[N], cnt, siz[N], c[N];
ll read(){
	ll x=0; char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
	return x;
}
void write(ll x){
	if(x<10)
	{
		putchar(x+'0');
		return;
	}
	write(x/10);
	putchar(x%10+'0');
}
struct Edge{
	int to, next;
}edge[N<<1];
void AddEdge(int u, int v){
	edge[++cnt]=(Edge){ v, head[u] }, head[u]=cnt;
	edge[++cnt]=(Edge){ u, head[v] }, head[v]=cnt;
}
void dfs(int u, int fa){
	siz[u]=1;
	for(int i=head[u]; i; i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v, u);
		c[n-siz[v]]--;
		siz[u]+=siz[v];
	}
	c[siz[u]]--;
}
int power(int a, int k){
	int ret=1;
	while(k)
	{
		if(k&1) ret=1ll*ret*a%mod;
		a=1ll*a*a%mod; k>>=1;
	}
	return ret;
}
void DFT(int *a, int n, int f){
	rep(i, 0, n-1) if(i<rev[i]) swap(a[i], a[rev[i]]);
	for(int i=1, t=1; i<n; i<<=1, t++)
	{
		int wn=power(G, f?(mod-1-((mod-1)>>t)):((mod-1)>>t));
		for(int j=0; j<n; j+=i<<1)
		{
			int w=1;
			for(int k=0; k<i; k++, w=1ll*w*wn%mod)
			{
				int u=a[j+k], v=1ll*w*a[j+k+i]%mod;
				a[j+k]=(u+v)%mod; a[j+k+i]=(u+mod-v)%mod;
			}
		}
	}
	if(f)
	{
		int v=power(n, mod-2);
		rep(i, 0, n-1) a[i]=1ll*a[i]*v%mod;
	}
}
int main(){
	n=read();
	fac[0]=1;
	rep(i, 1, n) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=power(fac[n], mod-2);
	drp(i, n, 1) inv[i-1]=1ll*inv[i]*i%mod;
	rep(i, 1, n-1){ u[i]=read(), v[i]=read(); AddEdge(u[i], v[i]); }
	rep(i, 1, n-1) c[i]=mod;
	dfs(1, 0);
	c[n]=n;
	rep(i, 1, n) f[i]=1ll*c[i]*fac[i]%mod;
	rep(i, 0, n) g[n-i]=inv[i];
	for(m=1; m<=((n<<1)|1); m<<=1) l++;
	rep(i, 0, m-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	DFT(f, m, 0); DFT(g, m, 0);
	rep(i, 0, m-1) f[i]=1ll*f[i]*g[i]%mod;
	DFT(f, m, 1);
	rep(k, 1, n) ans[k]=1ll*inv[k]*f[n+k]%mod;
	rep(i, 1, n) write(ans[i]), puts("");
}

Measured memory_bytes: 28928
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
using namespace std;

int main()
{
    string s;
    cin >> s;
    
    int n = s.size();
    int max_len = 0;
    int tmp_len = 0;
    for(int i=0;i<n;++i)
    {
        if(s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C')
        {
            tmp_len++;
            if(tmp_len > max_len)
                max_len = tmp_len;
        }
        else
        {
            tmp_len = 0;
        }        
    }

    cout << max_len << endl;
    return 0;
}

Measured memory_bytes: 256
module Main where

import Control.Applicative
import Control.Monad
import Data.List

f n x | (q, 0) <- n `divMod` x
      , q == x    = True
      | otherwise = False

main :: IO ()
main = do
    n <- read . concat . words <$> getLine :: IO Int
    if any (f n) [1 .. floor (sqrt $ fromIntegral n)]
        then putStrLn "Yes"
        else putStrLn "No"

Measured memory_bytes: 508
import sys
import math
import itertools
import collections

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
def solve(A,V,B,W,T):
    diff = abs(A - B)
    time = (V - W) * T
    return "YES" if(diff <= time) else "NO"
def main():
    A,V = map(int,input().split())
    B,W = map(int,input().split())
    T = int(input())
    # solve()
    print(solve(A,V,B,W,T))

if __name__ == "__main__":
    main()


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

using ll  = long long;
using vl  = vector<ll>;
using pll = pair<ll,ll>;
using vll = vector<pll>;
using vvll = vector<vll>;
#define rng(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define BIT(X,i) ((X>>i)&1)
#define POW2(x) (1LL<<x)

ll N, M, ans;
vvll edges;
vl bits;

bool usePath(int v, int pre, int dst, int m) {
    if (v == dst) return true;
    for (auto e : edges[v]) {
        ll to = e.first, idx = e.second;
        if (to == pre) continue;
        if (usePath(to, v, dst, m)) {
            bits[idx] |= (1LL << m);
            return true;
        }
    }
    return false;
}

void dfs(int m, int bit, ll sign) {
    if (m == M) return;
    dfs(m+1, bit, sign);

    bit |= (1 << m);
    int cnt = 0;
    rep(i,N-1) cnt += (bit & bits[i]) != 0;
    ans += sign * POW2(N-1-cnt);
    dfs(m+1, bit, -sign);
}

int main() {
    cin >> N;
    edges.resize(N);
    bits.assign(N-1, 0);
    rep(i,N-1) {
        int a, b; cin >> a >> b;
        a--; b--;
        edges[a].push_back(make_pair(b, i));
        edges[b].push_back(make_pair(a, i));
    }
    cin >> M;
    rep(m,M) {
        int u, v; cin >> u >> v;
        u--; v--;
        usePath(u, -1, v, m);
    }

    ans = POW2(N-1);
    dfs(0, 0, -1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
use {
    proconio::{input, marker::Usize1},
    std::{
        collections::{BTreeSet, BTreeMap},
        ops::Bound::Included,
    },
};

const M: usize = usize::max_value();

fn main() {
    input! {
        h: usize,
        w: usize,
        ab: [(Usize1, Usize1); h],
    }

    let mut es = BTreeSet::new();
    let mut dc = BTreeMap::new();
    for j in 0..w {
        es.insert((j, j));
    }
    dc.insert(0, w);

    for i in 0..h {
        let (a, b) = ab[i];
        let rng = es.range((Included(&(a, 0)), Included(&(b, w))));
        let add = if let Some(&(_, s)) = rng.clone().last() {
            let e = if b == w - 1 { M } else { b + 1 };
            Some((e, s))
        } else {
            None
        };

        let mut rm = vec![];
        for &(e, s) in rng {
            rm.push((e, s));
        }

        for (e, s) in rm {
            es.remove(&(e, s));

            let d = e - s;
            if let Some(v) = dc.get_mut(&d) {
                if *v <= 1 {
                    dc.remove(&d);
                } else {
                    *v -= 1;
                }
            }
        }

        if let Some((e, s)) = add {
            es.insert((e, s));
            *dc.entry(e - s).or_insert(0) += 1;
        }

        let d = if let Some(f) = dc.iter().next() { *f.0 } else { M };
        if d >= w {
            println!("-1");
        } else {
            println!("{}", d + i + 1);
        }
    }
}


Measured memory_bytes: 14972
/*    Don’t Quit
    
    When things go wrong as they sometimes will;
        When the road you’re trudging seems all uphill;
            When the funds are low, and the debts are high;
                And you want to smile, but you have to sigh;
                    When care is pressing you down a bit
                        Rest if you must, but don’t you quit.
*/
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0)
#define pb push_back
//#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define int long long
const int MOD=1e9+7;
const int N=2e5+5;
int gcd(int n,int m)
{
    if(n==0)
        return m;
    else
        return gcd(m%n,n);
}
int a[N];
int32_t main()
{
    IOS;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int k=a[n]/2;
    int mn=MOD;
    int ind;
    int mx=0;
    for(int i=1;i<n;i++)
    {
        if(mn>=abs(a[i]-k))
        {
            mn=abs(a[i]-k);
            mx=max(mx,a[i]);
        }
    }
    cout<<a[n]<<" "<<mx<<endl;


    
    

    
    
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define drep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define Maxe(x) *max_element(all(x))
#define Mine(x) *min_element(all(x))
#define Size(x) ((ll)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
#define Fi first
#define Se second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

    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;
    }

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo
//mint,dijkstra,gyakugen

    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll a,b,v,w,t;
        cin>>a>>v>>b>>w>>t;
        if(b<a){
            if(b-w*t<a-v*t){
                cout<<"NO"<<endl;
            }else{
                cout<<"YES"<<endl;
            }
        }else{
            if(b+w*t>a+v*t){
                cout<<"NO"<<endl;
            }else{
                cout<<"YES"<<endl;
            }
        }
    }

Measured memory_bytes: 3648
def solve(a, b, c, d):
  a, c = sorted([a, c])
  b, d = sorted([b, d])
  for k in range(30, 0, -1):
    block_size = 3**k
    box_size = block_size // 3
    x1, y1, x2, y2 = map(lambda x:x//box_size, (a, b, c, d))
    if x1 != x2 and y1 != y2:
      return c-a + d-b
    elif x1 == x2 and x1%3 == 1 and (y1+1)//3*3+1 < y2:
      shifted = (a+c) % (2*block_size)
      return min(shifted-2*box_size+2, 4*box_size-shifted) + d-b
    elif y1 == y2 and y1%3 == 1 and (x1+1)//3*3+1 < x2:
      shifted = (b+d) % (2*block_size)
      return min(shifted-2*box_size+2, 4*box_size-shifted) + c-a
  return c-a + d-b

for i in range(int(input())):
  print(solve(*map(lambda x:int(x)-1, input().split())))


Measured memory_bytes: 3316
#include <stdio.h>
#include <algorithm>
typedef long long ll;

int main(void) {
  ll i, j, n, m = 1000001, ans = 0;
  scanf("%lld", &n);
  ll a[n + 1];
  bool flg[m];
  for(i = 0; i < m; ++i) flg[i] = false;
  for(i = 0; i < n; ++i) scanf("%lld", &a[i]);
  std::sort(a, a + n);
  a[n] = 1e9;
  for(i = 0; i < n; ++i) {
    if(a[i] == a[i + 1]) {
      flg[a[i]] = true;
      continue;
    }
    ++ans;
    for(j = 1; j < 1001; ++j) if(!(a[i] % j) && (flg[a[i] / j] || flg[j])) {
      --ans;
      break;
    }
    flg[a[i]] = true;
  }
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 4244
S = input()
res = [0] * len(S)

childlen = 0
for i in range(len(S)):
    if S[i] == "R":
        childlen += 1
    else:
        tmp = (childlen + int(childlen % 2 == 1)) // 2
        res[i - 1] += tmp
        res[i] += childlen - tmp
        # print(i, tmp, childlen, res[i - 1], res[i])
        childlen = 0

for i in reversed(range(len(S))):
    if S[i] == "L":
        childlen += 1
    else:
        tmp = (childlen + int(childlen % 2 == 1)) // 2
        res[i + 1] += tmp
        res[i] += childlen - tmp
        childlen = 0

print(*res)

Measured memory_bytes: 10652
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	class Vertex {
		int id;
		int[] vertices;
		int visited = -1;
		int completed = -1;
	}
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		Vertex[] vertices = new Vertex[n];
		for (int i = 0; i < n; i++) {
			vertices[i] = new Vertex();
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int id = Integer.parseInt(st.nextToken());
			vertices[i].id = id;
			int cnt = Integer.parseInt(st.nextToken());
			vertices[i].vertices = new int[cnt];
			for (int j = 0; j < cnt; j++) {
				vertices[i].vertices[j] = Integer.parseInt(st.nextToken());
			}
		}
		reader.close();
		
		DFS(vertices, n);
		
		for (int i = 0; i < n; i++) {
			Vertex vertex = vertices[i];
			System.out.println(vertex.id + " " + vertex.visited + " " + vertex.completed);
		}
	}

	private void DFS(Vertex[] vertices, int n) {
		int time = 0;
		for (int i = 0; i < n; i++) {
			Vertex vertex = vertices[i];
			Stack<Integer> stack = new Stack<Integer>();
			if (vertex.visited == -1) {
				stack.push(vertex.id);
			}
			while (!stack.isEmpty()) {
				vertex = vertices[stack.peek()-1];
				if (vertex.visited == -1) {
					vertex.visited = ++time;
				}
				int childId = next(vertices, vertex.vertices);
				if (childId != -1) {
					vertices[childId-1].visited = ++time;
					stack.push(childId);
				} else {
					vertex.completed = ++time;
					stack.pop();
				}
			}
		}
	}

	private int next(Vertex[] vertices, int[] childIds) {
		for (int i = 0; i < childIds.length; i++) {
			if (vertices[childIds[i] - 1].visited == -1) return childIds[i];
		}
		return -1;
	}
}



Measured memory_bytes: 24612
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int N;
  cin >> N;
  char S[N][N];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> S[i][j];
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    bool sym = true;
    char T[N][N];
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        T[j][k] = S[(j+i)%N][k];
      }
    }
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < N; k++) {
        if (T[j][k] != T[k][j]) {
          sym = false;
        }
      }
    }

    if (sym) {
      ans += N;
    }
  }

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

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807

int n,k,a[200000],z,memo[200001];
vector<int> v[200001];
vector<int> ANS;
bool f;

signed main() {
    cin >> n >> k;
    rep(i,n) {
        cin >> a[i];
        v[a[i]].pb(i);
        if (!memo[a[i]]) memo[a[i]] = i+1;
    }
    while(n) {
        if (z>=n-1) f=true;
        repo(i,z,n) {
            auto itr = upper_bound(all(v[a[i]]), i);
            if (itr != v[a[i]].end()) {
                i = *itr;
                if (i==n-1) f=true;
            }
            else {
                ANS.pb(i+1);
                z = memo[a[i]];
                break;
            }
        }
        if (f) {
            int hoge = k%(ANS.size()+1);
            if (hoge==0) {
                cout << endl;
                return 0;
            }
            hoge--;
            z = ANS[hoge];
            z--;
            repo(i,z,n) {
                auto itr = upper_bound(all(v[a[i]]), i);
                if (itr != v[a[i]].end()) i = *itr;
                else cout << a[i] << " ";
            }
            cout << endl;
            return 0;
        }
    }
}



Measured memory_bytes: 17268
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n, m, t1, t2, a[11], c[] = {999999,2,5,5,4,5,6,3,7,6};
int dp[10005], dp2[10005];

int f(int x) {
    if(x < 0)
        return -999999;

    if(x == 0)
        return 0;

    if(dp[x] != -1)
        return dp[x];

    int mx = -1, tz = -1;
    for(int i = 9; i >= 1; --i)
        if(a[i])
            if(f(x - c[i]) + 1 > mx) {
                mx = f(x - c[i]) + 1;
                tz = i;    
            }
    dp2[x] = tz;
    return dp[x] = mx;
}

void f2(int x) {
    if(!x)
        return;
    cout << dp2[x];
    f2(x - c[dp2[x]]);
}

int main() {
    memset(dp, -1, sizeof dp);
    cin >> n >> m;
    for(int i = 0; i < m; ++i)
        cin >> t1, a[t1] = 1;
    f(n);
    f2(n);
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#define N 1000101

using namespace std;

int main(){
   long n, p;

   int prime[N] = {1,1};

   cin >> n >> p;

   if( n == 1){
      cout << p << endl;
      return 0;
   }

   for(int i=2;i<N;i++){
      if(prime[i] == 0){
         for(int j=2*i;j<N;j+=i){
            prime[j] = 1;
         }
      }
   }

   long ans = 1;
   for(long i=2;i<N;i++){
      if(p < i){
         break;
      }
      if(prime[i]==1){
         continue;
      }
      int count =0;
      while(p%i == 0){p/=i;count++;}
      if(count >= n){
         for(int j=0;j<(count/n);j++)
            ans *= i;
      }
   }

   cout << ans << endl;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
  int64_t n;
  cin >> n;
  
  vector<int64_t> p(n);
  
  for (auto&& pp : p) {
    cin >> pp;
    --pp;
  }

  int64_t ans = 0;
  int64_t num = 0;
  for (auto i : irange(0L, n)) {
    if (p[i] == i) {
      ++num;
    } else {
      ans += (num + 1) / 2;
      num = 0;
    }
  }
  ans += (num + 1) / 2;
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  long a,b,max = 0,point;
  cin >> n;
  for(int i = 0;i <n;i++){
    cin >> a >> b;
    if(max < a)max = a,point = b;
  }
  cout << max + point << endl;
}

Measured memory_bytes: 256
N = int(input())
D, X = map(int, input().split())
mass = 0

for n in range(N):
  A = int(input())
  i = 0
  day = 1
  while day <= D:
    day = i*A + 1
    i += 1

  mass += (i-1)


result = mass + X
print(result)

Measured memory_bytes: 9132
#include<cstdio>
using namespace std;
typedef long long ll;

ll n, x[200], dp[2][201][201], mod = 1000000007;

int main() {
  scanf("%lld", &n);
  char s[10]; ll m = 0;
  for (ll i = 0; i < n; i++) {
    scanf("%s", s);
    if (s[0] == 'U') x[m++] = 1;
    else if (s[0] == 'D') x[m++] = 0;
  }
  if (m == 0) {
    printf("1\n");
    return 0;
  }
  if (x[0] == 0) {
    printf("0\n");
    return 0;
  }
  dp[0][1][1] = 1;
  for (ll i = 1; i < m; i++) {
    if (x[i] == 1) {
      for (ll j = 1; j <= i+1; j++) {
        for (ll k = 1; k <= i+1; k++) {
          dp[i&1][j][k] = (dp[!(i&1)][j-1][k-1] + dp[!(i&1)][j][k] * k) % mod;
        }
      }
    } else {
      for (ll j = 0; j < i+1; j++) {
        for (ll k = 0; k < i+1; k++) {
          dp[i&1][j][k] = (dp[!(i&1)][j][k] * j + dp[!(i&1)][j+1][k+1] * (j + 1) * (k + 1)) % mod;
        }
      }
    }
    for (ll j = 0; j <= m; j++) {
      for (ll k = 0; k <= m; k++) {
        dp[!(i&1)][j][k] = 0;
      }
    }
  }
  printf("%lld\n", dp[!(m&1)][0][0]);
}



Measured memory_bytes: 3320
module Main where

import Control.Applicative
import Text.Printf

main :: IO ()
main = loop 

loop :: IO()
loop = do
  { [x,y]<- getInts
  ; if x == 0 && y == 0 then return ()
    else do
      {putInts(if x > y then [y,x] else [x,y])
      ; loop
      }
  }

--

getInts :: IO[Int]
getInts = map read . words <$> getLine

putInts :: [Int] -> IO ()
putInts = putStrLn . unwords . map show




Measured memory_bytes: 4104
/**
 *COYG, 14 FA Cups we are back baby
 */
#include <bits/stdc++.h>
using namespace std;
#define ll 		long long
#define mp 		make_pair
#define pb 		push_back
#define forn(i,n) 	for(int i=0;i<n;i++)
#define for1(i,n) 	for(int i=1;i<n;i++)
#define ford(i,n) 	for(int i=n-1;i>=0;i--)
#define vi 		vector<int>
#define vl 		vector<ll>
#define pii 		pair<int,int>
#define pll 		pair<ll,ll>
#define vpi 		vector<pair<int,int> >
#define vpl		vector<pair<ll,ll> >
#define vvi 		vector<vector<int> >
#define vvl 		vector<vector<ll> >
#define ull 		unsigned long long
#define IOS 		ios_base::sync_with_stdio(false);
#define PI 		3.1415926535897932384626
#define ff 		first
#define ss 		second
#define char2Int(c) 	(c-'0')
#define FOREACH(i,t) 	for (auto i=t.begin(); i!=t.end(); i++)
#define clr(a,x) 	memset(a,x,sizeof(a)) //set elements of array to some value
#define all(x)		(x).begin(),(x).end()//cout<<"Case #"<<zzz<<": ";
#define plll pair<ll,pll >
const int mod=1e9+7;
void solve()
{
    ll n;cin>>n;string s;cin>>s;
    vector<ll> dp(1,0);ll sz=2;dp.pb(1);dp.pb(1);
    for(int i=(int)s.size()-1;i>=0;--i,++sz)
    {
        vector<ll> curr;curr.pb(0);ll sum=0;
        for(int which=1;which<=sz;which++)
        {
            if(s[i]=='>')
            {
                sum=(sum+dp[which-1])%mod;
            }
            else
            {
                ll toadd=(dp[sz]-dp[which-1]+mod)%mod;
                sum=(sum+toadd)%mod;
            }
            curr.pb(sum);
        }
        curr.pb(sum);
        dp=curr;
    }
    cout<<dp[(int)dp.size()-1]<<endl;
}
int main()
{
    IOS;cin.tie(NULL);
    ll zz;zz=1;
    //cin>>zz;
    for(int zzz=1;zzz<=zz;zzz++)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3796
#include <stdio.h>

int dp[50];

int fib (int n) {
	if ( n == 0 || n == 1) return dp[n] = 1;
	if ( dp[n] != -1) return dp[n];
	return dp[n] = fib(n - 1) + fib(n-2);
}

int main () {
	int n, i;
	for ( i = 0; i < 50; i++) dp[i] = -1;

	scanf("%d",&n);
	printf("%d\n",fib(n));

	return 0;
}



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

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fo(i, a, b, k) for(int i = a; i <= b; i += k)
#define _fo(i, a, b, k) for(int i = a; i >= b; i -= k)
#define foa(i, a) for (auto &i : a)
#define fod(i, a) for(int i = 1; i*i <= a; i++)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)  
#define log2i(x) (31-__builtin_clz(x))
#define log2ll(x) (63-__builtin_clzll(x)) 
#define msz(x) __builtin_popcount(x) 
#define mszll(x) __builtin_popcountll(x) 
#define fom(i, a, b) for(int i = a; i < (1<<b); i++)
#define ifon(i, mask) if(mask&(1<<i))
#define ss(i, mask) while(i=(i-mask)&mask)
#define ifss(i, mask) if(i > (mask^i)) 

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

const int N = 1e5+1;
const int MOD = 1e9+7;
const ll INF = INT_MAX;
const ll _INF = INT_MIN;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int a, b, c;
	cin >> a >> b >> c;
	cout << max(0, c-(a-b));
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define log(i,n) log(n)/log(i);
using namespace std;
typedef long long ll;


int main()
{
	ll n;
	cin >> n;
	cout << n * (n - 1) / 2 << endl;
}



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

using namespace std;

#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

const double eps = 1e-10;
const int MOD = 1000000007;

void printv(vector<auto> const& s) {
  REP(i, s.size()) {
    cout << s[i] << endl;
  }
}

void warshall_floyd(vvi &c) {
  int n = c.size();
  REP(i, n) {
    REP(j, n) {
      REP(k, n) {
        c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
      }
    }
  }
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int h, w; cin >> h >> w;
  vvi c(10);
  REP(i, 10) {
    c[i].resize(10);
    REP(j, 10) {
      cin >> c[i][j];
    }
  }
  warshall_floyd(c);

  int tmp = 0, ans = 0;
  REP(i, h) {
    REP(j, w) {
      cin >> tmp;
      if(tmp != -1) ans += c[tmp][1];
    }
  }

  cout << ans << endl;
  
  
}


Measured memory_bytes: 256
//
//  main.cpp
//  A
//
//  Created by Hashizo on 2020/03/14.
//  Copyright © 2020 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())


int main(int argc, const char * argv[]) {

	 ll data[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	

	ll k;
	cin >> k;


	cout << data[k-1] << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define random_shuffle asdasdd

const int MAXN = 2 * 105000;

int n;
int a[MAXN], b[MAXN];
int an[MAXN], bn[MAXN];

vector<int> prefixFunction(vector<int> s) {
  vector<int> p(sz(s));
  for (int i = 1; i < sz(s); i++) {
    int prev = p[i - 1];
    while (prev > 0 && s[prev] != s[i]) {
      prev = p[prev - 1];
    }
    if (s[prev] == s[i]) {
      prev++;
    }
    p[i] = prev;
  }
  return p;
}

int main() { 

  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &b[i]);
  }

  for (int i = 0; i < n; i++) {
    an[i] = a[i] ^ a[(i + 1) % n];
  }

  for (int i = 0; i < n; i++) {
    bn[i] = b[i] ^ b[(i + 1) % n];
  }

  vector <int> s;
  for (int i = 0; i < n; i++) {
    s.push_back(bn[i]);
  }
  s.push_back(-1);
  for (int i = 0; i < n; i++) {
    s.push_back(an[i]);
  }
  for (int i = 0; i < n; i++) {
    s.push_back(an[i]);
  }

  vector<int> kmp = prefixFunction(s);
  for (int i = n + 1; i + 1 < sz(s); i++) {
    if (kmp[i] == n) {
      cout << i - 2 * n << " " << (a[i - 2 * n] ^ b[0]) << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 11756