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

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int K, S, ans = 0;

	cin >> K >> S;

	repc(X, 0, K) {
		if (S - X > 2 * K || X > S) continue;
		ans += min(S - X, K) - max(0, S - X - K) + 1;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

const int MAX = 1e6;
int a[MAX+1];
int b[MAX+1];
void solve()
{
  int n, t, ans=0;
  cin >> n;
  for(int i=0; i<n; i++)
    cin >> t, a[t]++;
  for(int i=1; i<=MAX; i++)
    b[i] = 1;
  for(int i=1; i<=MAX; i++)
      if(a[i])
      {
        bool flag = 1;
        for(int j=i; j<=MAX; j+=i)
          if((i==j && a[j]>=2) || (i!=j && a[j]))
            b[j] = 0;
      }
  for(int i=1; i<=MAX; i++)
    if(a[i] && b[i])
      ans++;
  cout << ans << "\n";
}
int main()
{
  fastio
  solve();
  return 0;
}


Measured memory_bytes: 11468
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
long long s,count1;
main(){
  long long count[10]={0};
  cin>>s;
  int ans=0;
  int j=0;
  for(int i=0;s>0;i++)
  {
    count[i]= s % 10;
    s /= 10; j++;
  }
  j--;
  count1=1e9;
  for(;j>1;j--){
    ans=min(count1,abs(753-(100*count[j]+10*count[j-1]+count[j-2])));
    count1=ans;
  }
  cout<<ans<<endl;
}

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

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

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int a, b;
  cin >> a >> b;

  int result = 0;
  for (int i = a; i <= b; i++) {
    string s = to_string(i);
    bool ok = true;
    rep(j, s.size()) {
      if (s[j] != s[s.size() - 1 - j]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      result++;
    }
  }
  cout << result << endl;

  return 0;
}


Measured memory_bytes: 256
# Initialization
N, M = map(int, input().split())
adj = {}
for _ in range(M):
    u, v = [int(i) - 1 for i in input().split()]
    if u in adj:
        adj[u].append(v)
    else:
        adj[u] = [v]
S, T = [int(i) - 1 for i in input().split()]

INF = -1
dist = [[INF] * 3 for _ in range(N)]

# BFS
q = [(S, 0)]
dist[S][0] = 0
while len(q) > 0:
    u, nl = q.pop(0)
    if u not in adj:
        continue
    for v in adj[u]:
        ml = (nl + 1) % 3
        if dist[v][ml] != INF:
            continue
        dist[v][ml] = dist[u][nl] + 1
        q.append((v, ml))

ans = dist[T][0]
if ans == INF:
    print(-1)
else:
    print(ans // 3)


Measured memory_bytes: 45196
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<long long>v;
 
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	long long n,tmp;
 
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>tmp;
		v.push_back(tmp);
	}
	map<long long,long long>p;
	for(int j=0;j<n;j++){
		if(p.count(v[j])==0){
			p.insert({v[j],1});
		}else if(p[v[j]] != 0){
			p[v[j]]++;
		}
	}
	long long sum = 0;
	for(auto it : p){
		sum += (it.second * (it.second-1))/2;
	}
	for(int i=0;i<n;i++){
		cout << sum - (p[v[i]]-1)<<endl;
	}
	return 0;
}

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

void b_picture_frame(void) {
	int h, w;
	char a[110][110];
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a[i][j];
		}
	}
	
	for (int i = 0; i < (h + 2); i++) {
		for (int j = 0; j < (w + 2); j++) {
			if ((i == 0) || (i == h + 1)) cout << "#";
			else if ((j == 0) || (j == w + 1)) cout << "#";
			else cout << a[i - 1][j - 1];
		}
		cout << endl;
	}
}


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


Measured memory_bytes: 3592
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = min(ind + l[1] -1 , N-1)
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)

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

int main()
{
  ll N; cin >> N;
  string S; cin >> S;

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

  ll ans = 1;
  for (int i=1; i<N; i++) {
    if (S[i-1] != S[i]) ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

//関数宣言
//int func(int x, int y);

int main(void){

  //スカラー入力
  int N,M;

  scanf("%d %d", &N, &M);

  //配列入力
  int L[M], R[M];

  for(int i=0; i<M; i++){
    scanf("%d %d", &L[i], &R[i]);
  }

  int maxL=L[0], minR=R[0];
  for(int i=1; i<M; i++){
    if(maxL < L[i]){
      maxL = L[i];
    }
    if(minR > R[i]){
      minR = R[i];
    }
  }

  int ans;
  if(maxL <= minR){
    ans = minR - maxL + 1;
  }else{
    ans = 0;
  }

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 896
from collections import deque

n,k = map(int, input().split())
s = input()

cnt_01 = []
prev = s[0]
cnt = 0
for c in s:
    if c != prev:
        cnt_01.append(cnt)
        cnt = 1
    else: 
        cnt += 1
    prev = c
else:
    cnt_01.append(cnt)


if len(cnt_01) <= 2*k:
    print(n)
    exit()


if s[0] == '0':
    ans_candi = sum(cnt_01[0:2*k])
    cnt_01 = cnt_01[1:]
else:
    ans_candi = 0


first_que = cnt_01[0:2*k+1]
que = deque(first_que)
curr_sum = sum(first_que)
ans = curr_sum
for i in range(k, len(cnt_01)-1):
    break_flag = False
    poped1 = que.popleft()
    poped2 = que.popleft()
    curr_sum -= (poped1 + poped2)
    if 2*i+1 < len(cnt_01):
        que.append(cnt_01[2*i+1])
        curr_sum += cnt_01[2*i+1]
    if 2*i+2 < len(cnt_01):
        que.append(cnt_01[2*i+2])
        curr_sum += cnt_01[2*i+2]
    else:
        break_flag = True
    ans = max(curr_sum, ans)
    if break_flag: break

print(max(ans,ans_candi))


Measured memory_bytes: 5236
#include<iostream>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int n;
    long sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	if(i%3==0||i%5==0)
    		continue;
    	else
    		sum+=i;
    }
    cout<<sum;
}

Measured memory_bytes: 3652
n=int(input());s=input()
l=[[0]*26 for i in range(n-1)]
r=[[0]*26 for i in range(n-1)]

for i in range(n-1):
  l[i][ord(s[i])-ord('a')]=1
  if i!=n-2:
    for j in range(26):
      l[i+1][j]=l[i][j]

for i in range(n-2,-1,-1):
  r[i][ord(s[i+1])-ord('a')]=1
  if i!=0:
    for j in range(26):
      r[i-1][j]=r[i][j]

lr=[[0]*26 for i in range(n-1)]
for i in range(n-1):
  for j in range(26):
    lr[i][j]=l[i][j]*r[i][j]
x=0
for i in range(n-1):
  x=max(x,sum(lr[i]))
print(x)

Measured memory_bytes: 3064
import heapq

def greedy(limit, n):
    ans = 0
    hq = []
    for i in range(n-1, -1, -1):
        for item in limit[i]:
            # 最大値を取り出したいので負で格納
            heapq.heappush(hq, -item)
        if hq:
            ans += -heapq.heappop(hq)
    return ans

def solve():
    n = int(input())
    left = []
    limit_l = [[] for i in range(n)]
    l_cnt = 0
    right = []
    limit_r = [[] for i in range(n)]
    r_cnt = 0
    ans = 0
    for i in range(n):
        k, l, r = map(int, input().split())
        ans += min(l, r)
        if l > r:
            # 左に並びたい
            limit_l[k-1].append(l-r)
            l_cnt+=1
        else:
            # 右に並びたい
            if n-k-1 >= 0:
                limit_r[n-k-1].append(r-l)
            else:
                # 右のスコアを獲得できない
                pass
            r_cnt+=1
    ans += greedy(limit_l, n)
    ans += greedy(limit_r, n)
    print(ans)
    return 

t = int(input())
for i in range(t):
    solve()

Measured memory_bytes: 46736
import java.util.*;


public class Main {
    static List<String> z;

    public static void permutation(String q, String ans) {
        if (q.length() <= 1) {
            z.add(ans + q);
        } else {
            for (int i = 0; i < q.length(); i++) {
                permutation(q.substring(0, i) + q.substring(i + 1), ans + q.charAt(i));
            }
        }
    }

    public static void main(String[] args) {
        z = new ArrayList<>();

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
//        int[] Ps = new Ps[N];
//        int[] Qs = new Qs[N];
        StringBuilder P_sb = new StringBuilder();
        StringBuilder Q_sb = new StringBuilder();
        for (int n = 0; n < N; n++) {
            P_sb.append(Integer.toString(sc.nextInt()));
        }
        for (int n = 0; n < N; n++) {
            Q_sb.append(Integer.toString(sc.nextInt()));
        }

        StringBuilder sb = new StringBuilder();

        for (int n = 0; n < N; n++) {
            sb.append(Integer.toString(n + 1));
        }

//        System.out.println(sb.toString());

//        permutation("12345", "");
        permutation(sb.toString(), "");
//        System.out.println(z.size());
        int a = 0; int b = 0;
        for (int i = 0; i < z.size(); i++) {
//            System.out.println(z.get(i));
            if ( P_sb.toString().equals(z.get(i)) ) a = i;
            if ( Q_sb.toString().equals(z.get(i)) ) b = i;
        }
        System.out.println(Math.abs(b - a));
    }
}

Measured memory_bytes: 50832
/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
int h, w;
string a[30][30];
void solve() {
    cin >> h >> w;
    string tar = "snuke";
    int x, y;
    x = y = 0;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
            if(a[i][j] == tar) {
                x = i, y = j;
            }
        }
    cout << char('A' + y) << x + 1 << endl;

}
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

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 T>
vector<T> make_v(size_t a){return vector<T>(a);}

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

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

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

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  using P = pair<Int, Int>;
  vector<vector<P> > G(n);
  for(Int i=0;i<m;i++){
    Int s,t,d;
    cin>>s>>t>>d;
    G[s].emplace_back(t,d);
  }
  const Int INF = 1e15;
  Int ans=INF;
  
  for(Int p=0;p<n;p++){
    auto dp=make_v<Int>(n,1<<n);
    fill_v(dp,INF);
    dp[p][1<<p]=0;
    for(Int b=0;b<(1<<n);b++){
      for(Int v=0;v<n;v++){
	if((~b>>v)&1) continue;
	for(auto e:G[v]){
	  Int u,d;
	  tie(u,d)=e;
	  if(u==p&&b==(1<<n)-1) chmin(ans,dp[v][b]+d);
	  if((b>>u)&1) continue;   
	  chmin(dp[u][b|(1<<u)],dp[v][b]+d);
	}
      }
    }
  }
  
  if(ans==INF) ans=-1;
  cout<<ans<<endl;
  return 0;
}



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

char s[3];

int main() {
	cin >> s;
	for(int i=0;i<3;++i)
		if (s[i] == '7') {
			printf("Yes");
			return 0;
		}
	printf("No");
	return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long LL;
const int M=2e5+5;
const LL INF=1e12+5;

int a[M],f[M];
int n;
LL k;
bool check(LL mid)
{
	LL sum=0;
	for(int i=0;i<n;i++)
	{
		//if(f[i]>mid) return false;
		if(a[i]>mid/f[i])
			sum+=a[i]-mid/f[i];
	}
	return sum<=k;
}

int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
		scanf("%d",&f[i]);
	sort(a,a+n);
	sort(f,f+n,greater<int>());
	LL l=0,r=INF;
	LL ans=r,mid;
	while(l<=r)
	{
		mid=l+((r-l)>>1);
		if(check(mid))
		{
			ans=min(ans,mid);
			r=mid-1;
		}
		else
			l=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main(){
  int n,m;
  cin >> n >> m;

  vector<vector<int>> ks(m,vector<int>(n,-1));
  vector<int> kk(m);
  for (int i = 0; i < m; i++)
  {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++)
    {
      cin >> ks[i][j];
      ks[i][j]--;
    }
  }

  vector<int> p(m);
  for (int i = 0; i < m; i++)
  {
    cin >> p[i];
  }

  // for (int i = 0; i < m; i++)
  // {
  //   for (int j = 0; j < ks[i].size(); j++)
  //   {
  //     cout << ks[i][j];
  //   }
  //   cout << endl;
    
  // }
  

  int ans = 0;
  for (int bit = 0; bit < (1<<n); bit++)
  {
    map<int,int> mp;
    for (int i = 0; i < n; ++i) {
      if (bit & (1<<i)) {
        mp[i]=1;
      }
      else mp[i]=0;
    }

    for (int i = 0; i < m; i++)
    {
      int cnt = 0;
      for (int j = 0; j < n; j++)
      {
        cnt+=mp[ks[i][j]];
      }
      if (!(cnt%2==p[i])) break;
      if (i==m-1) ans++;
    }    
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[200003],ans[200003];
int main(){
  int n,tot=0;
  scanf("%d",&n);
  for(int i=1;i<=n;++i)
    scanf("%d",&a[i]);
  for(int i=n;i>0;--i){
    int cnt=0;
    for(int j=i*2;j<=n;j+=i)
      cnt=(cnt+ans[j])%2;
    if(cnt==a[i])
      ans[i]=0;
    else{
      tot++;
      ans[i]=1;
    }
  }
  printf("%d\n",tot);
  for(int i=1;i<=n;++i){
    if(ans[i])
      printf("%d ",i);
  }
  printf("\n");
  return 0;
}

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

int main() {
  int N,K,C;
  cin>>N>>K>>C;
  string S;
  cin>>S;
  int a=0,b=0;
  vector<int>p(K);
  vector<int>q(K);
  while(a<K){
    if(S.at(b)=='x'){
      b++;
    }
    else{
      p.at(a)=b;
      b+=C+1;
      a++;
    }
  }
  
  a=K-1,b=N-1;
  while(a>=0){
    if(S.at(b)=='x'){
      b--;
    }
    else{
      q.at(a)=b;
      b-=C+1;
      a--;
    }
  }
  for(int i=0;i<K;i++){
    if(p.at(i)==q.at(i)){
      cout<<p.at(i)+1<<endl;
    }
  }
  
}

Measured memory_bytes: 3332
N, H = map(int,input().split())

A = []
B = []

for i in range(N):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)
A.sort(reverse = True)
B.sort(reverse = True)
Max = A[0]
cnt = 0
while H > 0 and cnt < N:
    b = B[cnt]
    if b <= Max:
        break
    H -= b
    cnt += 1
while H > 0:
    H -= Max
    cnt += 1
print(cnt)

Measured memory_bytes: 86360
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

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

__attribute__((constructor))
void initial() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    string answer = "keyence";
    string S;
    cin >> S;
    int length = S.size();
    int cutLength = length - answer.size();
    bool result = false;

    // DEBUG(cutLength);

    if (cutLength > 0) {
        for (int s = 0; s <= length - cutLength; s++) { // 全てのカットポジションsについて
            // 部分文字列を作る
            // DEBUG(s);
            vector<char> candidate;
            for(int i = 0; i < s; i++) { // カットした前側
                // DEBUG(S[i]);
                candidate.pb(S[i]);
            }

            for(int i = s + cutLength; i < length; i++) { // カットした後ろ側
                // DEBUG(S[i]);
                candidate.pb(S[i]);
            }

            bool tmpResult = true;
            rep(i, answer.size()) {
                // DEBUG(candidate[i]);
                // DEBUG(answer[i]);
                if (candidate[i] != answer[i]) tmpResult = false;
            }
            // DEBUG(tmpResult);
            if (tmpResult) result = true;
        }
        cout << (result ? "YES" : "NO") << endl;
    } else {
        cout << (answer == S ? "YES" : "NO") << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x) // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    vector<ll> v;
    ll ans = 0;
    for (ll i = 0; i < n; i++)
    {
        ll t;
        cin >> t;
        ans += t;
        if (t % 10 != 0)
            v.push_back(t);
    }
    if (ans % 10 != 0)
    {
        cout << ans << endl;
    }
    else
    {
        if (v.empty())
        {
            cout << 0 << endl;
        }
        else
        {
            sort(ALL(v));
            ans -= v.front();
            cout << ans << endl;
        }
    }
    
}

Measured memory_bytes: 256
N = int(input())
hlist = list(map(int, input().split()))
inf = float("inf")
dp = [inf] * N
dp[0] = 0
dp[1] = abs(hlist[1] - hlist[0])
for i in range(2, N):
    dp[i] = min(dp[i - 1] + abs(hlist[i] - hlist[i - 1]), dp[i - 2] + abs(hlist[i] - hlist[i - 2]))
print(dp[-1])


Measured memory_bytes: 13928
#include <bits/stdc++.h>
using namespace std;
#define rep for(int i = 0;i<n;i++)
 
int main(void){
  long long n;cin >>n;
  bool frag = false;long long a = 1;
  for(long long i = 2;i<=sqrt(n)+1;i++){
    if(n % i == 0){
      a = i;
      frag = true;
    }
  }
  long long str;
  if(frag == true){
    str = n/a;
  }else{
    str = n;
  }
  //cout << str << endl;
  cout << to_string(str).size() << endl;
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  while(cin >> n && n){
    ll M = 0,z3 = n * n * n;
    REP(i,1,n){
      REP(j,i,n){
        if(i * i * i + j * j * j <= z3){
          M = max(M,(ll)(i*i*i+j*j*j));
        }
      }
    }
    cout << z3 - M << endl;
  }
  return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const int mod=1000000007;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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

int a[1000000];
bool b[1000000];

int main(){
  int N;
  cin >> N;
  for(int i = 1; i <= N; i++) cin >> a[i];
  for(int i = N; i>0; i--){
    int pos = i;
    int mul = i;
    int sum = 0;
    while(pos <= N){
      if(b[pos]) sum++;
      pos += mul;
    }
    if(sum%2!=a[i]) b[i]=true;

  }
  int m = 0;
  for(int i = 1; i <= N; i++){
    if(b[i]) m++;
  }
  cout << m << endl;
  rep(i,N){
    if(b[i+1]) cout << i+1 << " ";
  }
  cout << endl;
}



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

int main() {
  int A, B;
  cin >> A >> B;
  int ans = 0;
  for (int i = A; i <= B; i++) {
    int a, b, c, d, e;
    a = i % 10;
    b = (i % 100 - i % 10) / 10;
    c = (i % 1000 - i % 100) / 100;
    d = (i % 10000 - i % 1000) / 1000;
    e = (i - i % 10000) / 10000;
    if (a == e && b == d) ans++;
  }
  cout << ans;
}


Measured memory_bytes: 3620
n=int(input())
h=[0]+list(map(int,input().split()))+[0]

cnt=0
while any([i!=0 for i in h]):
    start,end=100,100
    for i in range(n+2):
        if h[i]!=0:
            start=min(start,i)
        elif h[i]==0 and start<i:
#            end=min(end,i)
            end=i
            break
    l=[i-1 for i in h[start:end]]
    h=h[:start]+l+h[end:]
    cnt+=1
print(cnt)

Measured memory_bytes: 3064
n, k = map(int, input().split())
mod = 10 ** 9 + 7
a = [i for i in range(n + 1)]
b = [0] * (n + 1)
c = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[i]
a.reverse()
c[0] = a[0]
for i in range(1, n + 1):
    c[i] = c[i - 1] + a[i]
ans = 0
for i in range(n + 1):
    if i + 1 >= k:
        ans += (c[i] - b[i] + 1)
        ans %= mod
print(ans)

Measured memory_bytes: 38332
/*
 * Main.cpp
 *
 *  Created on: 26/03/2020
 *      Author: freyman
 */

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	cout << (n*(n-1))/2 + (m*(m-1))/2 << "\n";

	cout << "\n";

}

Measured memory_bytes: 256
// at coder beginner
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define  boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ull unsigned long long
#define deb(x) cout<<#x<<" "<<x<<endl;
#define deb2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define deb2l(x,y,i) cout<<#x<<i<<" "<<x<<" "<<#y<<i<<" "<<y<<endl;

#define fr(i,l,r) for(ll i=l;i<r;i++)
#define mems(a,x) memset(a,x,sizeof(a))
#define mod 1000000007
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vll vector<ll>
#define pbp(x,y) push_back(make_pair(x,y))
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll  maxx=1e10+5;
void solve(){
  ll n,m;
  cin>>n>>m;
  ll gcd=__gcd(n,m);
  cout<<(n*m)/gcd;
  
    
}
int main(){
    ll t=1;
//cin>>t;
ll k=1;
    while(k<=t){

     solve();
     k++;
    }
    return 0;
}


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

#define ll long long
#define ull unsigned long long

using namespace std;

int main() {
	int H, W, K;
	cin >> H >> W >> K;

	vector <string> s;
	for (int ii = 0; ii < H; ++ii){
		string hoge;
		cin >> hoge;
		s.push_back(hoge);
	}

	//行ごとに累積和
	vector<vector<int>> sum(H, vector <int> (W+1, 0));
	for (int ii = 0; ii < H; ++ii){
		for (int jj = 0; jj < W; ++jj){
			sum[ii][jj+1] = sum[ii][jj] + (s[ii][jj] - '0');
		}
	}

	int ans = 100100100;
	int tryMax = (1 << (H-1) );
	for (int ii = 0; ii < tryMax; ++ii){
		// printf("ii %i\n", ii);

		//"切れ目"を登録
		vector <int> div;
		int tmp = ii;
		for (int jj = 0; jj < H-1; ++jj){
			if (tmp & 1 == 1){
				div.push_back(jj);
			}
			tmp = tmp >> 1;
		}
		int divNum = div.size();


		bool success = true;
		bool rremain = true;
		int l = 0;
		int r = 1;
		while (l <= W) {
			// printf("l = %i, r = %i\n", l, r);
			//部分和がKより大きくなるまでrを動かす
			bool rmove = true;
			while (rmove) {
				vector <int> tmpSum(div.size()+1, 0);
				if (r > W) {
					rremain = false;
					break;
				}

				if (div.size() == 0){
					for (int jj = 0; jj < H; ++jj){
						tmpSum[0] += sum[jj][r] - sum[jj][l];
					}
					// printf("tmpSum[0] %i\n", tmpSum[0]);
					if (tmpSum[0] > K){
						if (r == l+1){
							success = false;
						}
						rmove = false;
						break;						
					}
				} else {
					int cnt = 0;
					for (int jj = 0; jj < H; ++jj){
						if (jj == div[cnt] + 1){
							cnt++;
							tmpSum[cnt] += sum[jj][r] - sum[jj][l];
						} else {
							tmpSum[cnt] += sum[jj][r] - sum[jj][l];
						}
					}
					// assert(cnt == div.size());
					for (int jj = 0; jj < div.size()+1; ++jj){
						if (tmpSum[jj] > K){
							if (r == l+1){
								success = false;
							}
							rmove = false;
							break;
						}
					}
				}
	
				if (!success){
					break;
				}

				if (rmove){
					r++;
				}
			}

			if (!success){
				break;
			}

			//部分和がKより大きくなったら
			if (!rremain){
				break;
			}
			divNum += 1;
			l = r-1;
			// printf("divNum[%d] = %d\n", ii, divNum);
		}


		if (success){
			ans = min(ans, divNum);
		}
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.typecons;
import std.algorithm, std.array, std.range, std.container;
 
void main() {
	auto data = readln.split;
	auto N = data[0].to!long, X = data[1].to!long;
	
	long height(long level) { return 2^^(level+2) - 3; }
	long p_num(long level) { return 2^^(level+1) - 1; }
	
	long solve(long level, long x) {
		if (level == 0 || x == 0) return x;
		auto h = height(level-1);
		if (x <= h+1)        return solve(level-1, x-1);
		else if (x <= 2*h+2) return p_num(level-1) + 1 + solve(level-1, x-h-2);
		else return p_num(level);
	}
	writeln(solve(N, X));
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a[1000],s,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 cin>>a[i];
     sort(a+1,a+1+n);
    for(int i=n;i>=1;i--)
     if(i>=n-m+1)
      s=s+a[i];
    cout<<s<<endl;
return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define int long long int
constexpr int INF = std::numeric_limits<int>::max();
constexpr int NINF = std::numeric_limits<int>::min();
using namespace std;

void solve() {
  int N;
  string S;
  cin >> N >> S;

  int ans = 0;
  int x = 0;

  for (char c:S) {
    if (c == 'I') {
      x++;
    } else {
      x--;
    }

    ans = max(ans, x);
  }
  cout << ans << endl;
}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ans, n, i, j, k, a[55], tag;
int main(){
	cin>>n;
	for(i = 1; i <= n; i++) cin>>a[i];
	for(i = 1; i <= n; i++)
	    for(j = 1; j <= n; j++){
	    	swap(a[i], a[j]); tag = 0;
	    	for(k = 1; k < n; k++)
	    	    if(a[k] >= a[k+1]) tag = 1;
	    	if(!tag){
	    		cout<<"YES"<<endl;
				return 0;
			}
			swap(a[i], a[j]);
		}
	cout<<"NO"<<endl;
}

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

int main(){
  string S;
  cin >> S;
  int A=0;
  for(int i=0;i<S.size();i++){
    int B=S.at(i)-'0';
    A+=B;
    if(A>=9){
      A-=9;
    }
  }
  if(A%9==0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}
    

Measured memory_bytes: 3764
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <list>


using namespace std;

const int MODULE = 1e9 + 7;

int main(int argc, char * argv [] )
{
    int N;
    cin >> N;

    vector<long long> A(N);
    vector<long long> T(N);
    vector<long long> R(N, 1);

    for (int i = 0; i < N; ++i) {
        cin >> T.at(i);
        if (i == 0 || T.at(i) > T.at(i - 1)) {
            R.at(i) = 0;
        } else {
            R.at(i) = T.at(i);
        }
    }

    for (int i = 0; i < N; ++i) {
        cin >> A.at(i);
        if (i == 0) {
            continue;
        }
        if (A.at(i) < A.at(i - 1)) {
            if ( (R.at(i - 1) == 0 && A.at(i - 1) != T.at(i - 1))
                || (R.at(i - 1) > 0 && A.at(i - 1) > T.at(i - 1)) ) {
                cout << 0 << endl;
                return 0;
            }
            R.at(i - 1) = 1;
        } else {
            if (R.at(i - 1) == 0) {
                if (T.at(i - 1) > A.at(i - 1)) {
                    cout << 0 << endl;
                    return 0;
                }
                R.at(i - 1) = 1;
            } else {
                R.at(i - 1) = min(A.at(i - 1), T.at(i - 1));
            }
        }
    }

    if ( (R.at(N - 1) == 0 && T.at(N - 1) != A.at(N - 1))
         || (R.at(N - 1) > 0 && T.at(N - 1) < A.at(N - 1)) ) {
        cout << 0 << endl;
        return 0;
    }

    R.at(N - 1) = R.at(0) = 1;

    long long sum = 1;

    for (int i = 0; i < N; ++i) {
        sum = (sum * R.at(i)) % MODULE;
    }

    cout << sum << endl;

    return 0;
}



Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
#define ll              long long int
#define ld              long double
#define mk              make_pair
#define pb              push_back
#define f               first
#define s               second
#define fo(i,a,b)       for(i=a;i<b;i++)
#define foe(i,a,b)      for(i=a;i<=b;i++)
#define all(x)          x.begin(),x.end()
#define vi              vector<int>
#define vl              vector <long long int>
#define pii             pair <int,int>
#define pll             pair <long long int, long long int>
#define vpii            vector< pair<int,int> >
#define vpll            vector < pair <long long int,long long int> >
#define MOD             998244353
using namespace std;
const int inf = INT_MAX;
const ll inf64 = LLONG_MAX;


ll add(ll x, ll y) {ll res = x + y; return (res >= MOD ? res - MOD : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= MOD ? res % MOD : res);}
ll sub(ll x, ll y) {ll res = x - y; return (res < 0 ? res + MOD : res);}
ll lcm(ll x, ll y) {ll res = (x * y) / __gcd(x, y); return res;}
ll power(ll x, ll y) {if (y < 0) return 1; ll res = 1; x %= MOD; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}

vl fac;

ll modinv(ll n) { return power(n, MOD - 2);}

ll nCr(ll n, ll r)
{
	if (r == 0)return 1;
	return mul(mul(fac[n], modinv(fac[r])), modinv(fac[n - r]));
}

int main()
{
	boost;
	ll n, m, i, k;
	cin >> n >> m >> k;
	fac = vl(n + 1);
	fac[0] = 1;
	fo(i, 1, n + 1)fac[i] = mul(fac[i - 1], i);
	ll p;
	ll ans = 0;
	foe(p, n - k, n)
	{
		ans = add(ans, mul(nCr(n - 1, p - 1), mul(m, power(m - 1, p - 1))));
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 4772
S = input()
n = len(S)
sum = 0
for i in range(2**(n-1)):
    B = [""] * (n-1)
    f = ""
    for j in range(n-1):
        if((i>>j)&1):
            B[j] = "+"
            
    for a,b in zip(S, B+[""]):
        
        f += a
        f += b
        
    sum += eval(f)

print(sum)

Measured memory_bytes: 3064
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
char c[3];
cin>>c[0]>>c[1]>>c[2];
sort(c,c+3);
if(c[0]=='a'&&c[1]=='b'&&c[2]=='c')
cout<<"Yes";
else
cout<<"No";
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Fri May  8 14:17:18 2020

@author: shinba
"""
S,T = map(str,input().split())
A,B = map(int,input().split())
U = input()

if U == S:
    print(A-1,B)
else:
    print(A,B-1)



Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iostream>
#include <ctime>
using namespace std;
#define _LL long long
#define rep(i, n) for (_LL i = 0; i < (_LL)(n); i++)
#define vecrep(itr, v) for (auto itr = (v).begin(); itr != (v).end(); itr++)

int main()
{
    int n; cin >> n;
    double ret = 0;
    rep(i, n)
    {
        double a; cin >> a;
        ret += 1.0 / a;
    }
    cout << std::fixed << std::setprecision(15) << 1.0 / ret;
    return 0;    
}

Measured memory_bytes: 3764
import Control.Monad

main = do
  n <- getLine
  let n2 = read n :: Int
  ss <- replicateM n2 getLine
  let s = map (map strToInt) (map words ss)
      c = column $ map partSum s
      maxs = map maxPart c
      ans = foldl1 max maxs
  putStrLn $ show ans

strToInt :: String -> Int
strToInt str = read str

partSum :: [Int] -> [Int]
partSum [] = []
partSum (x:xs) = scanl1 (+) (x:xs) ++ (partSum xs)

column :: [[Int]] -> [[Int]]
column [] = []
column xs = foldr (zipWith (:)) [ [] | _ <- head xs] xs

maxPart :: [Int] -> Int
maxPart [] = 0
maxPart xs = foldl1 max $ scanl1 fsum xs
              where fsum a b
                      |a < 0     = b
                      |otherwise = a + b

Measured memory_bytes: 81832
N, Y = map(int, input().split())

for man in range(N+1):
    for sen in range(N+1):
        if man + sen > N:
            break
        if 10000*man + 5000*sen + 1000*(N-man-sen) == Y:
            print(man, sen, N-man-sen)
            exit()
print('-1 -1 -1')


Measured memory_bytes: 9104
#include <iostream>
#include <sstream>

using namespace std;

int main()
{
    int H, W, A, B;
    cin >> H >> W >> A >> B;

    stringstream ss;
    for (int x = 0; x < H; ++x)
    {
        for (int y = 0; y < W; ++y)
        {
            const bool l = x < B;
            const bool u = y < A;
            ss << ((l ^ u) ? 0 : 1);
        }
        ss << endl;
    }
    cout << ss.str() << endl;

    return 0;
}


Measured memory_bytes: 3332
N = int(input())


def gcd(a, b):
    tmp_a, tmp_b = a, b
    a = max(tmp_a, tmp_b)
    b = min(tmp_a, tmp_b)
    r = a % b
    while r > 0:
        a = b
        b = r
        r = a % b
    return b
    

def lcm(a, b):
    return a*b//gcd(a, b)


tmp = 1
for i in range(N):
    T = int(input())
    ans = lcm(T, tmp)
    tmp = ans

print(ans)


Measured memory_bytes: 3064
N=int(input())
W = [input() for _ in range(N)]

flag=1

for i in range(N-1):
    if W[i][-1]!=W[i+1][0]:
        flag=0
        
W.sort()
for i in range(N-1):
    if W[i]==W[i+1]:
        flag=0
        
if flag==1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38384
#include <iostream> // cout, endl, cin
#include <iomanip>
#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
#include <math.h>
#include <numeric>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int INF = 1001001001;
const int BG = 1000000007;

int64_t factorical(int num)
{
    int64_t ans = 1;
    for (int i = 1; i <= num; i++)
    {
        ans = (ans * i) % BG;
    }
    return ans;
}

int main()
{
    int N, M;
    cin >> N >> M;

    int64_t nc = factorical(N);
    int64_t mc = factorical(M);

    int diff = abs(N - M);
    if (diff > 1)
    {
        cout << 0 << endl;
    }
    else if (diff == 1)
    {
        cout << (nc * mc) % BG << endl;
    }
    else if (diff == 0)
    {
        cout << (nc * mc * 2) % BG << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<ll> VLL;
typedef vector<PLL> VP;
const static int INF = 1000000000;
const static int MOD = 1000000007;
const int dx[4]={1, 0, -1, 0};
const int dy[4]={0, 1, 0, -1};
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; }
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "
//charを整数に
int ctoi(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return 0; }
// 累積和 for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i]; 
void cum_sum(int N,vector<double> a, vector<double> &s){ for(int i=0; i<N; i++){ s[i+1]=s[i]+a[i];}}
//ユークリッドの控除法
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; // Be careful not to overflow
}
//素数判定
bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}
int getdigit(ll num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
//空白文字も入力 getline(cin, S);
//桁数指定 setprecision

int main()
{
    ll K;
    cin >> K;
    if(K%7==0){
        ll L=9*K/7;
        if(L%2==0 || L%5==0){
            cout << -1 << endl;
            return 0;
        }
        ll t=1;
        ll count=0;
        while(1){
            t*=10;
            if(t%L==1){
                cout << count+1 << endl;
                return 0;
            }
            t%=L;
            count++;
        }
    }
    else{
        ll L=9*K;
        if(L%2==0 || L%5==0){
            cout << -1 << endl;
            return 0;
        }
        ll t=1;
        ll count=0;
        while(1){
            t*=10;
            if(t%L==1){
                cout << count+1 << endl;
                return 0;
            }
            t%=L;
            count++;
        }
    }
}

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

using namespace std;

void swap(int *p,int *q)
{
	int temp=*p;
	*p=*q;
	*q=temp;
}

void sol()
{
	int a[3];

	for(int i=0;i<3;++i)
	{
		cin >> a[i];
	}

	swap(&a[0],&a[1]);
	swap(&a[0],&a[2]);

	for(int i=0;i<3;++i)
	{
		cout << a[i] << " ";
	}
}

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

	sol();
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) *b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////



int main() {
	
	ll N, M;
	cin >> N >> M;

	vector<ll> A(N + 1,0), B(M + 1,0);
	repn(i, N) cin >> A[i];
	repn(i, M) cin >> B[i];

	sort(++A.begin(), A.end());
	sort(++B.begin(), B.end());

	//repn(i, N) cout << A[i] << " ";
	//cout << endl;
	//repn(i, M) cout << B[i] << " ";
	//cout << endl;

	ll ans = 1;

	for(ll i=N*M; i>=1; i--) {
		auto itra = lower_bound(A.begin(), A.end(), i);
		ll a = distance(A.begin(), itra);

		auto itrb = lower_bound(B.begin(), B.end(), i);
		ll b = distance(B.begin(), itrb);

		ll sp;

		if (a <= N - 1 && A[a + 1] == i) { sp = 0; }
		else if (b <= M - 1 && B[b + 1] == i) { sp = 0; }

		else if (a <= N && A[a] == i && b <= M && B[b] == i) { sp = 1; }

		else if (a <= N && A[a] == i) { sp = M-b+1; }
		else if (b <= M && B[b] == i) { sp = N-a+1; }
		else { sp=(N-a+1)*(M-b+1)-(N*M-i); }

		
		//cout << i << " "<<a <<" "<< b <<" "<< sp<<endl;

		if (sp <= 0) { ans = 0; break; }
		else { ans = ans * sp%MOD; }

	}

	cout << ans;


	system("PAUSE");
}


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

using namespace std;
const int maxn = 1e5 + 1;
const int maxm = 1e5;

int main()
{
	int n, m;
	cin >> n >> m;
	
	int problem[maxn][1] = {0};
	int countA = 0, countP = 0, countAa[maxn][1] = {0}, countPp[maxn][1] = {0};
	
	while (m--)
	{
		int p;
		string s;
		cin >> p >> s;
		if (problem[p][1] == 0 && s == "WA")
		{
			countPp[p][1]++;
			countP++;
		}
		else if (problem[p][1] == 0 && s == "AC")
		{
			countA++;
			countAa[p][1] = 1;
			problem[p][1] = 1;	
		}
		else {
			continue; 
		}
	}
	
	for (int i = 1; i <= n; i++)
	{
		if (countAa[i][1] == 0)
		{
			countP -= countPp[i][1];
		}
	}
	
	
	cout << countA << " " << countP;
	return 0;
}


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

int main(){
  long long a, b;
  cin >> a >> b;
  if((a+b) % 2 == 0){
    cout << (a+b) / 2 << endl;
  }
  else{
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;

int main()
{
	int32_t N;
	cin >> N;

	int32_t _max = -1;
	int32_t _min = 1001;
	for (int32_t i = 0; i < N; i++) {
		int32_t a;
		cin >> a;
		_max = max(_max, a);
		_min = min(_min, a);
	}

	cout << (_max - _min) << endl;

	return 0;
}


Measured memory_bytes: 256
# coding: utf-8

A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0
for a in range(A + 1):
	for b in range(B + 1):
		for c in range(C + 1):
			if 500 * a + 100 * b + 50 * c == X:
				count += 1

print(count)

Measured memory_bytes: 3188
#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    int N, i, num[3], j, k, count, ans=0;
    string S;

    cin >> N;
    cin >> S;

    // 0~999を作れるかを調べる
    for(i=0; i<=999; i++){
        num[0] = i / 100;
        num[1] = (i / 10) % 10;
        num[2] = i % 10;

        k = 0;

        for(j=0; j<N; j++){
            if(S[j] == ('0' + num[k])){ // 整数を文字列に変換して比較する
                k++;
            }

            if(k == 3){
                break;
            }
        }

        if(k == 3){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n,m = [int(i) for i in input().split()]
k = []
for i in range(m):
  array = [int(i) for i in input().split()]
  k.append(array)

p = [int(i) for i in input().split()]
ans = 0
chk = 0

for i in range(2**n):
  r = format(i,'b')
  r = r.zfill(n)[::-1]
  for j in range(m):
    for l in range(1,k[j][0]+1):
      chk += int(r[k[j][l]-1])
    if chk % 2 != p[j]:
      chk = 0
      break
    if j == m-1:
      #print(r,chk)
      ans += 1
    chk = 0
  
print(ans)

Measured memory_bytes: 41072
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
typedef vector<int> VE;
const ll mod = 1000000007; //10^9+7



int main(){
  int n;
  cin >> n;
  int dp[100002];
  REP(i, 100002){dp[i] = i;}
  dp[0] = 0;
  //9^6 = 531441 6^7 = 279936
  REP(i, 100002){
    int j = 1;
    int k = 1;
    while(i + int(pow(6, j)) <= n){
      dp[i + int(pow(6, j))] = min(dp[i + int(pow(6, j))], dp[i] + 1);
      j++;
    }
    while(i + int(pow(9, k)) <= n){
      dp[i + int(pow(9, k))] = min(dp[i + int(pow(9, k))], dp[i] + 1);
      k++;
    }
  }
  int ans = dp[n];
  if(ans == n){
    int count = 0;
    for(int i = n; i <= 0; i--){
      if(dp[i] != i){
        ans = min(ans, dp[i] + count);
      }
      count++;
    }
  }
  //REP(i, n + 1)print(i << " " <<dp[i]);
  print(ans);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

/*
    辺が存在しない場合、dist[i][j] = INF、ただしdist[i][i] = 0 とする
    頂点数 V のとき :
    vector<vector<int>> dist(V, vector<int>(V, INF));
    for(int i = 0; i < V; i++){
        dist[i][i] = 0;
    }
*/
template <typename T>
void WarshallFloyd(vector<vector<T>>& dist) {
    int V = dist.size();
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    // dist[i][i] < 0 が存在 <-> 負の閉路が存在
}

signed main() {
    int n, m;
    ll l;
    cin >> n >> m >> l;
    int a, b;
    ll c;
    vector<vector<ll>> dist(n, vector<ll>(n, LINF));
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    rep(i, m) {
        cin >> a >> b >> c;
        a--;
        b--;
        dist[a][b] = dist[b][a] = c;
    }
    int q;
    cin >> q;
    int s[q], t[q];
    rep(i, q) {
        cin >> s[i] >> t[i];
        s[i]--;
        t[i]--;
    }
    WarshallFloyd(dist);
    vector<vector<ll>> distt(n, vector<ll>(n, LINF));
    for (int i = 0; i < n; i++) {
        distt[i][i] = 0;
    }
    for (int u = 0; u < n; u++){
        for (int v = 0; v < n; v++){
            if (0 < dist[u][v] && dist[u][v] <= l) distt[u][v] = 1;
        }
    }
    WarshallFloyd(distt);
    rep(i, q) {
        cout << (distt[s[i]][t[i]] != LINF ? distt[s[i]][t[i]] - 1 : -1) << endl;
    }
    return 0;
}

Measured memory_bytes: 5696