akhauriyash/Code-Regression huggingface dataset:
N = int(input())
S = input()

key = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            key.append([i,j,k])
            
flag1 = 0
flag2 = 0
flag3 = 0
ans = 0



for i in range(len(key)):
    flag1 = 0
    flag2 = 0
    flag3 = 0
    
    flag1 = S.find(str(key[i][0]))
    
    if flag1 == -1:
        continue
        
    flag2 = S.find(str(key[i][1]),flag1+1)
    
    if flag2 == -1:
        continue
        
    flag3 = S.find(str(key[i][2]),flag2+1)
    
    if flag3 == -1:
        continue
                            
    if flag1 != -1 and flag2 != -1 and flag3 != -1:
        ans += 1
        
print(ans)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
typedef long double ld;
const int inf = 1e9 + 7;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 3;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < b; i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define fact(n) rep(i, 1, n+1)ft.pb((ft[i-1]*i)%mod);
#define mod_in(a) exp(a, mod-2)
#define ncr(n, r) ((ft[n]*mod_in((ft[r]*ft[(n)-(r)])%mod))%mod)
#define deb(x) cout << #x << " " << x << endl;
#define flash ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define endl '\n'
ll prime[100000];
ll exp(ll a,ll b);
void sieve(ll n);
ll gcd(ll a ,ll b);
ll countdigit(ll n);
int main()
{

	flash
	ll a,b;
	cin>>a>>b;
	if(a>9||b>9)cout<<"-1";
	else cout<<a*b;
}
//
//
//
//
//
// IMPORTANT FUNCTIONS
ll exp(ll a, ll b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
ll gcd(ll a,ll b){
    if(a==0)return b;
    return gcd(b%a,a);
}
void sieve(ll n) {
    for(ll i=0;i<=n;i++) {
        prime[i]=1;
    }
    prime[0]=0;prime[1]=0;
    for(ll i=2;i<=n;i++) {
        if(prime[i]==1) {
            for(ll j=2;i*j<=n;j++) {
                prime[i*j]=0;
            }
        }
    }
}
ll countdigit(ll  n) 
{ 
    return floor(log10(n) + 1); 
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>


using namespace std;

int main(){
	int n,r;
	while(cin >> n >> r,n){
		int p[n];
		fill(p,p+n,0);
		int s = r;
		for(int i = 0;;i++,i %= n){
			if(p[i] == r){
				cout << i << endl;
				break;
			} else {
				if(s == 0){
					s += p[i];
					p[i] = 0;
				} else {
					p[i]++;
					s--;
				}
			}
		}
	}
}

Measured memory_bytes: 1160
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 1e17 - 10;
const double PI = acos(-1);
typedef pair<LL, LL> Pll;
LL h, w, n, m, s, ans = 0, a[100000], num = 0, sum = 0;
int flag = 0;
string str,stt;
int main() {
	cin >> n;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n%i == 0)
			ans = i;
	}
	num = n / ans;
	while (num > 0) {
		num /= 10;
		sum++;
	}
	cout << sum << endl;
	return 0;
}


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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define per(i,n) for(int i = n; i >= 0; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }



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

  int n;
  cin >> n;
  map<string, vector<P>> mp;
  set<string> st;
  rep(i,n) {
    string s;
    int p;
    cin >> s >> p;
    mp[s].emplace_back(p,i+1);
    st.insert(s);
  }
  for(auto it = mp.begin(); it != mp.end(); it++) {
    sort(rall(it->se));
  }
  for(auto it = st.begin(); it != st.end(); it++) {
    vector<P> v = mp[*it];
    rep(i,sz(v)) {
      cout << v[i].se << endl;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;

int kouka[6] = { 500,100,50,10,5,1 };
int main() {
	int a;
	while (cin >> a, a) {
		a = 1000 - a;
		int sum = 0;
		for (int b = 0; b < 6; b++) {
			sum += a / kouka[b];
			a -= a / kouka[b] * kouka[b];
		}
		cout << sum << endl;
	}
}

Measured memory_bytes: 3064
#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--)
typedef long long ll;
typedef unsigned long long ull;

int a[200000];

int main()
{
	int N, num = 1, ans = 0;

	cin >> N;
	rep(i, N) cin >> a[i];

	rep(i, N) {
		if (a[i] == num) num++;
		else ans++;
	}
	if (num == 1) ans = -1;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	
      	int a  = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
      	System.out.println(Math.min(a + b + 1, c) + b);
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
new_data_set;
const LL MOD = 1000003;

int pangkat(int a, int b) {
	int tmp = 1;
	for (int i = 1; i <= b; i++) {
		tmp *= a;
	}
	return tmp;
}

int main() {
	int N;
	cin >> N;
	int tmp = N, cnt = 0;
	while (tmp > 0) {
		tmp /= 10;
		cnt++;
	}
	int ans = 0;
	for (int i = 1; i <= cnt; i += 2) {
		if (i == cnt) {
			tmp = pangkat(10, cnt - 1);
			ans += (N - tmp + 1);
		} else {
			ans += 9 * pangkat(10, i - 1);
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[100005];
int k;
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	scanf("%d",&k);
	for (int i=1;i<=n;i++)
		if (s[i]!='a'&&(26-(s[i]-'a'))<=k){
			k-=26-(s[i]-'a');
			s[i]='a';
		}
	k%=26;
	while (k>0){
		s[n]++;k--;
		if (s[n]>'z')s[n]='a';
	}
	puts(s+1);
}

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



int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    string s; cin>>s;
    if(s[s.length()-1]=='s') {cout<<s; cout<<"es";}
    else{cout<<s;cout<<'s';}
}


Measured memory_bytes: 3648
#include <iostream>  // cin,cout
#include <stdio.h>   // printf,scanf (standard input/output)
#include <cmath>     // abs(x),pow(x,2)
#include <string>
#include <string.h>  // strlen, strcmp
#include <algorithm> // min,max, sort(v.begin(),v.end())
#include <vector>
#include <time.h>
using namespace std;

struct Data{
    int A;
    int Num;
    
    bool operator<( const Data& right ) const {
        //return A == right.A ? S < right.S : A < right.A;
        return Num > right.Num;
    }
};

int Func(){
    int x = 0;
    return x;
}

int main(){
    int N;
    cin >> N;
    
    int v[100010];
    vector<int> even{};
    vector<int> odd{};
    vector<Data> e;
    vector<Data> o;
    
    for (int i=0;i<N;i++) cin >> v[i];
    
    for (int i=0;i<N/2;i++) {
        even.push_back(v[2*i]);
        odd.push_back(v[2*i+1]);
    }
    
    sort(even.begin(),even.end());
    sort(odd.begin(),odd.end());
    
    int previous = even[0];
    Data temp_0{};
    temp_0.A = even[0];
    temp_0.Num = 1;
    e.push_back(temp_0);
    for (int i=1;i<even.size();i++) {
        if (even[i]==previous) {
            e[e.size()-1].Num += 1;
        }
        else {
            previous = even[i];
            Data temp{};
            temp.A = even[i];
            temp.Num = 1;
            e.push_back(temp);
        }
    }
//    for (int i=0;i<e.size();i++) {
//        cout << e[i].A << " " << e[i].Num << endl;
//    }
    
    previous = odd[0];
    temp_0.A = odd[0];
    temp_0.Num = 1;
    o.push_back(temp_0);
    for (int i=1;i<odd.size();i++) {
        if (odd[i]==previous) {
            o[o.size()-1].Num += 1;
        }
        else {
            previous = odd[i];
            Data temp{};
            temp.A = odd[i];
            temp.Num = 1;
            o.push_back(temp);
        }
    }
    
    sort(e.begin(),e.end());
    sort(o.begin(),o.end());
    
    //cout << e[0].A << endl;
    if (e[0].A!=o[0].A) {
        cout << N - e[0].Num - o[0].Num << endl;
    }
    else {
        if (e.size()==1 and o.size()==1) {
            cout << N/2 << endl;
        }
        else if (e.size()==1) {
            cout << N - (N/2+o[1].Num) << endl;
        }
        else if (o.size()==1) {
            cout << N - (e[1].Num+N/2) << endl;
        }
        else {
            if (e[0].Num+o[1].Num >= e[1].Num+o[0].Num) {
                cout << N - (e[0].Num+o[1].Num) << endl;
            }
            else {
                cout << N - (e[1].Num+o[0].Num) << endl;
            }
        }
    }
    
    return 0;
}

Measured memory_bytes: 2168
#include<stdio.h>
#include<math.h>
int main(void){
  int A[10000];
  int N,i,j,C,x;
  C=0;
 
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
    x=0;
    for(j=2;j<=sqrt(A[i]);j++){
      if(A[i]%j==0)x++;
    }
    if(x==0)C++;
  }
  printf("%d\n",C);
  return 0;
}

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


int main(){
    int n, k, tipo, cont=0;
    scanf("%d %d", &n, &k);
    int pessoas[n], qrecebe;
    for(int i=0; i<n; ++i)
    	pessoas[i]=0;
    
    for(int j=0; j<k; ++j){
    	scanf("%d", &tipo);	
    	for(int i=0; i<tipo; ++i){
    		scanf("%d", &qrecebe);
    		pessoas[qrecebe - 1]=1;
    	}
    }
    for(int i=0; i<n; ++i){
    	if(pessoas[i]==0)
    		cont+=1;
    }
    printf("%d\n", cont);

    return 0;
}

Measured memory_bytes: 1728
def f(s, d)
    return 0 if s == d
    return f(-d, -s) if d <= 0
    return f(0, -s) + f(0, d) if s < 0
    return d.to_s(2).count(?1) if s == 0
    k = s.to_s(2).size
    l = d.to_s(2).size
    return f(s - (1 << k - 1) , d - (1 << l - 1)) if k == l
    sprintf("%0#{l}b", s).count(?0) - (s & (s ^ (s - 1))).to_s(2).size + d.to_s(2).count(?1)
end

n = gets.to_i
n.times do
    s, d= gets.split.map(&:to_i)
    p f(s, d)
end



Measured memory_bytes: 6932
#include <stdlib.h>
#include <string.h>
int size(const void *x,const void *y);
int main(){
  int N;
  int L[100];// 0 to 99
  int i = 0;
  char tmp[1024];
  char *tp;
  int sum = 0;
  
  if(scanf("%d",&N)<0){
    return 1;
  }
  
  // printf("%d\n",N);
  
  if (scanf("%[0-9 ^\n]",tmp)<0){
    return 1;
  }
  //fgets(tmp,512,stdin);
  // printf("%s\n",tmp);
  tp = strtok(tmp, " ");
	
  L[i] = atoi(tp);
  i=1;
  while(tp = strtok(NULL, " ")){
    L[i] = atoi(tp);
    i++;
  }
  //ソート
  qsort(L,i,sizeof(int),size);
  i--; 
  //
  
  for(int j = i ; 0<j && N > 0 ;j-=2){
    // printf("%d[%d],%d[%d]\n",j,L[j],j-1,L[j-1]);
    if(L[j]<L[j - 1]){
      sum += L[j];
    }else{
      sum += L[j - 1];
    }
    N--;
  }
  printf("%d",sum);
  return 0;
}
 
int size(const void *x,const void *y){
  if(*(int *)x > *(int *)y){
    return 1;
  }else if(*(int *)x < *(int *)y){
    return -1;
  }else{
    return 0;
  }
}


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

using namespace std;

int main() {
  size_t N;  
  string S;  
  cin >> N >> S;
 
  
  size_t result = 0;  
  vector<size_t> z;  // [0, z[i])  [i, i+z[i])
  for (size_t l1 = 0; l1 < N - 1; ++l1) {
    
    z.clear();
    z.resize(N - l1, 0);
 
    // Z-Algorithm
    size_t beg = 0, end = 0;  // [l1, l1+(end-beg))     [beg, end)
    for (size_t i = 1; i < z.size(); ++i) {
      if (i + z[i - beg] < end) {
        
        z[i] = z[i - beg];
      } 
      else {
       
        const size_t l2 = l1 + i;
        size_t len = i < end ? (end - i) : 0;  
        for (; l2 + len < N; ++len) {
          if (S[l1 + len] != S[l2 + len]) break;
        }
        z[i] = len;
        beg = i;
        end = i + len;
      }
 
      
      result = max(result, min(i, z[i]));
    }
  }
 
  cout << result;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j) for(int i;i<j;i++)
#define print(t) cout<<t<<endl
typedef long long ll;
typedef string str;

int main(){
	int n,x,cnt=0,sum=0;
	cin >> n >> x;
	rep(i,n){
		int l;cin>>l;
		sum+=l;
		if(sum<=x){
			cnt++;
		}
	}
	cout<<cnt+1<<endl;
	return 0;
}

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

int main() {
  int N,L;
  cin>>N>>L;
  
  int sum=(N+1)*N/2+(L-1)*N;
  
  if(L>0) {
  	sum -= L;
  }
  else if(L+N-1<0){
    sum -= L+N-1;
  }
  cout << sum <<endl;
}

Measured memory_bytes: 256
package main

import (
    "fmt"
)

func main() {
    var n, w int
    fmt.Scan(&n, &w)
    is := make([][]int, n)
    for i := 0; i < n; i++ {
        var a, b int
        fmt.Scan(&a, &b)
        is[i] = []int{a, b}
    }

    // dp[i][n] i番目までWの重さで最大の価値
    dp := make([][]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = make([]int, w+1)
    }

    for i := 1; i <= n; i++ {
        wt, v := is[i-1][0], is[i-1][1]
        for j := 0; j <= w; j++ {
            if j-wt >= 0 && j-wt <= w {
                dp[i][j] = max(dp[i-1][j-wt]+v, dp[i-1][j])
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    var m int
    for i := 0; i <= w; i++ {
        m = max(m, dp[n][i])
    }

    fmt.Println(m)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func abs(n int) int {
    if n < 0 {
        return -n
    }
    return n
}


Measured memory_bytes: 81792
c = [input().split() for i in range(3)]

a1 = 0
a2 = 0
a3 = 0
b1 = 0
b2 = 0
b3 = 0

flag = 0
for i in range(0, 101):#a1の数
    for j in range(0, 101):#b1の数
        for k in range(0, 101):#b2の数
            if i+j == int(c[0][0]) and i+k == int(c[0][1]):
                a1 = i
                b1 = j
                b2 = k
                b3 = int(c[0][2])-i

if int(c[1][0])-b1 == int(c[1][1])-b2 and int(c[1][1])-b2 == int(c[1][2])-b3 and int(c[1][0])-b1 == int(c[1][2])-b3:
    if int(c[2][0])-b1 == int(c[2][1])-b2 and int(c[2][1])-b2 == int(c[2][2])-b3 and int(c[2][0])-b1 == int(c[2][2])-b3:
        flag = 1 

if flag == True:
    print("Yes")
else:
    print("No")

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

//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

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(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define RES(a,i,j) a.resize(i);rep(ii,i)a[ii].resize(j); 
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout<<a<<" "<<b<<" "<<c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 
#define gre(n) greater<n>()

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
const int INF = 1000000000;
const double dINF = 1000000000;
const ll INF64 = 922337203685477580ll;
const ll MOD = 1000000007ll;
const dou pi=3.141592653589793;
//メモ
//二次元配列のresizeのしかた
//vv.resize(n);
//for(size_t i=0; i<n; i++){
// vv[i].resize(n);
//}

//メモ
//負の辺を持つ最短経路問題では到達不可経路でも初期化値より小さくなりうるので注意しよう！

long long modpow(long long a, long long n) { //累乗の余剰
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main(){
    ll m,n;
    std::cin >> m>>n;
    std::cout << modpow(m,n) << std::endl;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define loop(i,n) for(int i=0; i<(n); i++)
#define loop3(i,a,n) for(int i=a; i<(n); i++)

int main()
{
  ll n;
  cin>>n;
  vector<ll>a(n),b(n),c(n);
  loop(i,n)
  {
      cin>>a[i]>>b[i]>>c[i];
  }
  ll dp[3][n];
  dp[0][0]=a[0];
  dp[1][0]=b[0];
  dp[2][0]=c[0];
  loop3(i,1,n)
  {
      dp[0][i]=a[i]+ max(dp[1][i-1], dp[2][i-1]);
      dp[1][i]=b[i]+ max(dp[0][i-1], dp[2][i-1]);
      dp[2][i]=c[i]+ max(dp[1][i-1], dp[0][i-1]);
  }
  ll ans=max(dp[0][n-1],max(dp[1][n-1], dp[2][n-1]));
  cout<<ans<<endl;
}


Measured memory_bytes: 7988
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    ll N, M;
    cin >> N >> M;
    ll res = 0;
    if(M - N * 2 < 0) {
        cout << min(N, M / 2) << endl;
    } else {
        M -= N * 2;
        cout << N + M / 4 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
from itertools import combinations_with_replacement

n,m,q = map(int,input().split())

L = [i+1 for i in range(m)]
li = [input().split() for i in range(q)]

for i in range(q):
    li[i] = [int(x) for x in li[i]]

ans = 0
for v in combinations_with_replacement(L,n):
    sum1 = 0
    for i in li:
        if v[i[1]-1] - v[i[0]-1] == i[2]:
            sum1 +=i[3]
    ans = max(ans,sum1)
print(ans)

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

int solve(int a[][3],int n){
	
	int dp[n][3];
	dp[0][0]=a[0][0];
	dp[0][1]=a[0][1];
	dp[0][2]=a[0][2];
	for(int i=1;i<n;i++){
		dp[i][0]=a[i][0]+max(dp[i-1][1],dp[i-1][2]);
		dp[i][1]=a[i][1]+max(dp[i-1][0],dp[i-1][2]);
		dp[i][2]=a[i][2]+max(dp[i-1][0],dp[i-1][1]);
	}
	return max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
}

int main(){
	int n;
	cin>>n;
	int a[n][3];
	int i,j;
	for(i=0;i<n;i++){
		for(j=0;j<3;j++)
			cin>>a[i][j];
	}
	
	cout<<solve(a,n)<<endl;
	
	return 0;
}

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

int main(){
  long n,x;
  cin >> n >> x;
  vector<long> a(n);
  for(long i = 0;i < n;i++){
    cin >> a.at(i);
  }
  long kekka = 0;
  for(long i = 0;i < n-1;i++){
    long eat = a.at(i) + a.at(i+1) - x;
    if(a.at(i) + a.at(i+1) > x){
      if(eat <= a.at(i+1)){
        kekka += eat;
        a.at(i+1) -= eat;
      }
      else{
        kekka += eat;
        a.at(i+1) = 0;
        a.at(i) = x;
      }
    }
  }
  cout << kekka << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)

using namespace std;
typedef unsigned long long ll;
const ll N=12e4,mo=998244353;

ll jc[N],ny[N];

inline ll ksm(ll o,ll t)
{
	ll y=1;
	for(;t;t>>=1,o=o*o%mo)
	if(t&1)y=y*o%mo;
	return y;
}

inline ll C(int a,int b)
{return (a<b||b<0)?0:(jc[a]*ny[b]%mo*ny[a-b]%mo);} 

int n,x;

int main()
{
	scanf("%d%d",&n,&x);
	jc[0]=ny[0]=1;
	fo(i,1,n)jc[i]=jc[i-1]*i%mo;
	ny[n]=ksm(jc[n],mo-2);
	fd(i,n-1,1)ny[i]=ny[i+1]*(i+1)%mo;
	ll ans=1;
	fo(i,1,x-1){
		int ha=i>>1;
		fo(l,0,ha){
			int lef=i-2*l;
			ans=(ans+C(n,l)*C(n-l,lef))%mo;
		}
	}
	fo(i,1,n){
		if(2*i>=x-1){
			if(x%2==1)
			fo(l,i,n)
			if(2*l-(x-1)>=x-1)ans=(ans+C(n,l))%mo;
			break;
		}
		int hh=(x-1)-2*i,ha=hh>>1;
		fo(l,0,ha)ans=(ans+C(hh-l,l)*C(n,2*i+hh-l))%mo;
	}
	cout<<ans;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

struct P{
  string name;
  int x,y,w,h;
  vector<P> v;
};

string tab="";
void pr(P p ){
  tab += " ";
  cout << tab << p.name << " "<<p.x << ","<<p.y<<","<<p.w<<","<<p.h << endl;
  for( unsigned int i=0;i<p.v.size();i++ )
    pr( p.v[i] );
  tab = tab.substr( 1 );
}


P parse( string s ){
  P p;
  unsigned int i=1,j;
  char c[10];
  p.name="";
  while( s[i]!='>' ) p.name += s[i++];
  i++;
  j=0; while( s[i]!=',' ) c[j++]=s[i++];
  c[j]='\0'; i++; p.x = atoi( c );
  j=0; while( s[i]!=',' ) c[j++]=s[i++];
  c[j]='\0'; i++; p.y = atoi( c );
  j=0; while( s[i]!=',' ) c[j++]=s[i++];
  c[j]='\0'; i++; p.w = atoi( c );
  j=0; while( s[i]!='<' ) c[j++]=s[i++];
  c[j]='\0'; p.h = atoi( c );

  if( s[i+1]=='/' )
    i+= ( p.name.length() + 3 );  // name+ '</>'

  while( i<s.length() ){
    int st = i;
    string nm="";
    for( j=st+1; s[j]!='>' ;j++ ) nm+=s[j];
    if( nm=="/"+p.name ) break;

    i = s.find( nm, j );
    i += (nm.length()+1);
    p.v.push_back( parse(s.substr( st,i-st )) );
  }
  return p;
}

const string nf="OUT OF MAIN PANEL 1";

string search( int x,int y, P p){
  string rslt;
  if( p.x<= x && x<=p.w &&
      p.y<= y && y<=p.h ){
    for( unsigned int i=0;i<p.v.size();i++ ){
      rslt = search( x,y,p.v[i] );
      if( rslt!=nf )
	return rslt;
    }
    rslt = p.name + " ";
    int size = p.v.size(), k=10000;

    if( size>0 ){
      while( size/k==0 ) k/=10;
      while( size>0 ){
	int d = size/k;
	size = size % k;
	k/=10;
	char c='0'+d;
	rslt += c;
      }
    }else
      rslt += '0';

    return rslt;
  }else
    return nf;
}


int main(){
  P p;
  int n,x,y;
  string s;

  while( cin>>n && n ){
    cin >> s;
    p = parse( s );

    //    pr( p );

    for( int lp=0;lp<n;lp++ ){
      cin >> x>>y;
      cout << search( x,y,p ) << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int main(void){
	
	char w[100];
	int i;
	gets(w);
	i=0;
	while(w[i]!='\0'){
		
		if(w[i]==',')
				w[i]=' ';
				i++;
	}
	puts(w);
	
	return 0;
}

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

int main() {
	vector<int> d;
	int n, r, p, c, tmp;
	cin >> n >> r;
	while(n != 0) {
		d.resize(n);
		for (int i = 0;i < n;i ++) d[i] = i + 1;
		for (int i = 0;i < r;i ++) {
			cin >> p >> c;
			for (int j = 0;j < c;j ++) {
				tmp = d[n - p - c + 1];
				d.erase(d.begin() + n - p - c + 1);
				d.push_back(tmp);
			}
		}
		cout << d[n - 1];
		cin >> n >> r;
		cout << endl;
	}
	return 0;
}


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

int main(){
  int n,a[100],min,max;
  cin >> n;
  min = 1000000001,max=-1;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]<min)min=a[i];
    if(a[i]>max)max=a[i];
  }
  cout << max - min << endl;
}


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

int main(void){
    int n;
    cin>>n;
    vector<string> s(n);
    map<string, int> mp;
    bool ng = false;
    rep(i,n){
        cin>>s[i];
        mp[s[i]]++;
        if (mp[s[i]] == 2) {
            ng = true;
        }
    }
    for (int i = 1; i < n; i++){
        if (s[i-1].back() != s[i].front()){
            ng = true;
        }
    }
    cout<<((!ng) ? "Yes" : "No")<<endl;
    return 0;
}


Measured memory_bytes: 256
S=list(input())

rud=['R','U','D']
lud=['L','U','D']
odd=[S[i] for i in range(len(S)) if i%2==1]
eve=[S[i] for i in range(len(S)) if i%2==0]

for o in odd:
  if o not in lud:
    print('No')
    exit()
for e in eve:
  if e not in rud:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 3064
// C - pushpush
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

vi solve(int N, vi &A){
	vi ans(N);//0_origin
	int isodd = N % 2;
	int f = N/2, b = N/2 + 1;
	if(isodd == 0){//even <- 0_origin
		f--;
		b--;
	}
	rp(a, 0, N){
		int ix = a%2 != isodd? f--: b++;
		ans[ix] = A[a];
	}
	return ans;
}

int main(){
	int N; cin>>N;
	vi A(N);
	rp(i, 0, N) cin>>A[i];
	vi ans = solve(N, A);
	rp(i, 0, N) cout<< ans[i] <<" ";
}

Measured memory_bytes: 3712
n = int(input())
a = [int(i) for i in input().split()]

count=0
while True:
    check = list(map(lambda x:x%2, a))
    if check.count(1) > 0:
        break
    else:
        a = list(map(lambda x:x//2, a))
        count+=1

print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define ios() ios::sync_with_stdio(true)
#define INF 1044266558
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
int n,k,x;
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            ans+=2*min(x,k-x);
        }
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
int main(){
        long long int N,A,max1=0,max2=0,index;
        std::cin>>N;
        for(int i=0; i<N; i++) {
                std::cin>>A;
                if(max1<=A) {
                        max2=max1;
                        max1=A;
                        index=i;
                }
                else if(max2<=A) max2=A;
        }
        for(int i=0; i<N; i++) {
                if(i==index) std::cout<<max2<<std::endl;
                else std::cout<<max1<<std::endl;
        }
        return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ll long long
#define P pair<int,int>
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
const int INF = 2002002002;
const ll LLINF = 9009009009009009009;
using namespace std;

int main() {
    fast_io
    int x;
    rep(i,5) {
        cin >> x;
        if (x == 0) {
            cout << i+1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int main(){
string s;
int len;
cin>>s;
len=s.length();
for(int i=0;i<len;i++){
	if(i%2==0)cout<<s[i];
}
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define ll long long
int k,a[100001],vis[100001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
int c[100001];
int main(){
	scanf("%d",&k);
	memset(a,0x3f,sizeof a);
	a[1]=1; pq.push(make_pair(1,1));
	while(!pq.empty()){
		pair<int,int> P=pq.top(); pq.pop();
		int u=P.second, d=P.first;
		if(vis[u]) continue;
		int v=(u+1)%k;
		if(a[v]>d+1) a[v]=d+1, pq.push(make_pair(a[v],v));
		for(int i=u;;i=i*10%k){
			if(c[i]||vis[i]) break;
			if(a[i]>d) a[i]=d, pq.push(make_pair(a[i],i));
			c[i]=1;
		}
		for(int i=u;;i=i*10%k){
			if(!c[i]) break;
			c[i]=0;
		}
		vis[u]=1;
	} printf("%d",a[0]);
	return 0;
}

Measured memory_bytes: 2552
n,k = map(int,input().split())
a = [int(x) for x in input().split()]
_min = 1145141919810
for i in range(2**(n-1)):
    ctr = 0
    val = 0
    h_max = a[0]
    for j in range(n-1):
        if (i>>j)&1:
            ctr+=1
            h_max = h_max+1 if h_max>=a[j+1] else a[j+1]
            val+=h_max-a[j+1]
        if h_max<a[j+1]:
            h_max = a[j+1]
    if ctr==k-1 and val<_min:
        _min = val
print(_min)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168

"""
import sys
from sys import stdin
from math import ceil
input = stdin.readline


def solve(n):
    dp = [[0] * (n+1) for _ in range(n+1)]
    dp[0][0] = 1

    for i in range(1, n+1):
        for j in range(i, n+1):
            t = 0
            for k in range(1, min(j+1, 3+1)):
                t += dp[i-1][j-k]
            dp[i][j] = t

    total = 0
    for d in dp:
        total += d[-1]
    return total


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break

        result = solve(n)
        print(ceil(result / 365 / 10))


if __name__ == '__main__':
    main(sys.argv[1:])
    

Measured memory_bytes: 7688
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef tuple<int,int,string,int,string> T;

signed main(){
	int n,v,w,d;
	string t,s;
	cin>>n;
	vector<T> V(n);
	r(i,n){
		cin>>v>>w>>t>>d>>s;
		V[i]=T(v,w,t,d,s);
	}
	sort(V.begin(),V.end());
	r(i,n){
		tie(v,w,t,d,s)=V[i];
		cout<<v<<' '<<w<<' '<<t<<' '<<d<<' '<<s<<endl;
	}
}


Measured memory_bytes: 17728
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
     public class Program
    {
        public static void Main(string[] args)
        {
            //Your code goes here
               var array  = Console.ReadLine().Split(' ');
               var a = int.Parse(array[0]);
               var b = int.Parse(array[1]);
            
            
            if (a == 1)
            {
                a = 14;
            }
            if (b== 1)
            {
               b = 14;
            }
            
            if (a >b) Console.WriteLine("Alice");
            else if(a <b) Console.WriteLine("Bob");
            else {
                Console.WriteLine("Draw");
            }
    }
}
}

Measured memory_bytes: 2648
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll fact[1000010];
ll invfact[1000010];
void makefact(int n,ll m){
	n=min(n,m-1);
	fact[0]=1;
	rep(i,0,n)fact[i+1]=fact[i]*(i+1)%m;
	invfact[n]=invp(fact[n],m);
	for(int i=n;i>0;i--)invfact[i-1]=invfact[i]*i%m;
}
ll choose(int n,int r,int m){return n<0||r<0||n-r<0?0:fact[n]*invfact[r]%m*invfact[n-r]%m;}


int main(){
	int x,y;
	scanf("%d%d",&x,&y);
	if((x+y)%3){
		puts("0");
		return 0;
	}
	
	makefact(1000000+10,MOD);
	//2a+ b=x
	// a+2b=y
	// a+ b=(x+y)/3
	int a=x-(x+y)/3;
	int b=y-(x+y)/3;
	printf("%d",choose(a+b,a,MOD));
}

Measured memory_bytes: 15744
N = int(input())
point = [list(map(int,input().split())) for _ in range(N)]
dis = [[0]*N for _ in range(N)]
for i in range(N):
  for j in range(i+1,N):
    dis[i][j] = ((point[i][0]-point[j][0])**2 + (point[i][1]-point[j][1])**2)**0.5
    dis[j][i] = dis[i][j]

cont = 0
for i in range(N):
  cont += sum(dis[i])

print(cont/N)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    int sum1=0,sum2=0,n1=n,n2=n;
    while(n1>0){
        n1-=a;
        sum1+=b;
    }
    while(n2>0){
        n2-=c;
        sum2+=d;
    }
    cout<<min(sum1,sum2)<<endl;
}


Measured memory_bytes: 3076
def powmod(b,r,mod)
  a = 1
  while r > 0
    if r%2 == 1
      a = a * b % mod
    end
    b = b * b % mod
    r /= 2
  end
  a
end

def invmod(f, mod)
  powmod(f, mod-2, mod)
end

def factorial(n, mod)
  fs = [1]
  (1..n).each{ |k| fs << (fs[-1] * k) % mod }
  fs
end

def inv_factorial(n, mod)
  fs = [1]
  f = 1
  (1..n).each{ |k|
    f = f * k % mod
    fs << invmod(f, mod)
  }
  fs
end

N,M,K = gets.split.map &:to_i
Mod = 10**9 + 7
V = (1..N-1).reduce(0){ |a,i| a + i*(N-i) }*M*M + (1..M-1).reduce(0){ |a,i| a + i*(M-i) }*N*N
NM = N*M

# guaranteed: NM >=2, K >= 2
fs = factorial(NM, Mod)
is = inv_factorial(NM, Mod)

R = NM - 2; C = K - 2
p fs[R] * is[R-C] % Mod * is[C] % Mod * V % Mod


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


int main() {
  rep(i,3000) {
    int x = 0;
    int y = 0;
    cin >> x >> y;
    if (x == 0 && y == 0) {
      continue;
    };
    cout << min(x,y) << " " << max(x,y) << endl;
  }
}


Measured memory_bytes: 2980
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
//cout << fixed << setprecision(10) << ans << endl;
//int gcd(int a,int b){return b?gcd(b,a%b):a;}
int p[200000];
int q[200000];
int r[200000];
int ans[600000];

signed main(){
    int x,y,a,b,c;
    cin >> x >> y >> a >> b >> c;
    REP(i,a){
        cin >> p[i];
    }
    REP(i,b){
        cin >> q[i];
    }
    REP(i,c){
        cin >> r[i];
    }
    sort(p,p+a);
    sort(q,q+b);
    sort(r,r+c);
    reverse(p,p+a);
    reverse(q,q+b);
    reverse(r,r+c);
    REP(i,x){
        ans[i] = p[i];
    }
    REP(i,y){
        ans[i+x] = q[i];
    }
    REP(i,min(x+y,c)){
        ans[x+y+i] = r[i]; 
    }
    sort(ans,ans+x+y+min(x+y,c));
    reverse(ans,ans+x+y+min(x+y,c));
    int ans2 = 0;
    REP(i,x+y){
        ans2 += ans[i];
    }
    cout << ans2 << endl;
    return 0;
}

Measured memory_bytes: 8832
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val A = intArrayOf(0) + readLine()!!.split(" ").map { it.toInt() }

    val box = IntArray(N + 1)
    for(i in N downTo 1){
        var x = i + i
        var sum = 0
        while (x in 0..N){
            sum += box[x]
            x += i
        }
        if(sum % 2 != A[i]){
            box[i] = 1
        }
    }

    box.mapIndexed { index, i ->
        Pair(index, i)
    }.filter {
        it.second == 1
    }.let {
        println(it.size)
        if(it.isNotEmpty()){
            println(it.map { it.first }.joinToString(separator = " "))
        }
    }
}

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

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define EPS 1e-8
#define DEB 0

const int dx[] = {0,1,0,-1};
const int dy[] = {-1,0,1,0};
int w,h,sx,sy,home,last;
int field[16][16];
int num[16][16];

#if DEB
stack<int> st;
#endif

class state{
public:
  char x,y;
  int s;
  state(char _x, char _y, int _s){
    x = _x;
    y = _y;
    s = _s;
  }
  
  bool operator<(const state& a)const{
    if( x==a.x ){
      if( y==a.y ) return s<a.s;
      else         return y<a.y;
    }else{
      return x<a.x;
    }
  }
  
};


map<state,int> msi;

bool ischeck(int s){
  return (((last&s)) == last) ;
}
bool inside(int x, int y){
  return (x<0 || y<0 || x>=w || y>=h);
}


int dfs(int x, int y, int s){
  if( (1<<home)-1 == s ){ // ÆÍ³ïÉßêé©Ç¤©
    rep(k,4){
      for(int i=1; i<20; i++){
	int tx = x + dx[k]*i;
	int ty = y + dy[k]*i;
	//if( inside(tx,ty) || field[ty][tx]==1 )break;
	if( inside(tx,ty) )break;

	if( field[ty][tx]==2 ){
#if DEB
	  printf("goal , (%d,%d)  s:%d\n",x,y,s);
	  stack<int> tmp = st;
	  while( !tmp.empty() ){
	    printf("%d,",tmp.top());
	    tmp.pop();
	  }
	  puts("\n");
#endif
	  return 1;
	}
      }
    }
    return 0;
  }
  if( msi.count(state(x,y,s)) ){ //ùÉÊÁ½ê
    return msi[state(x,y,s)];
  }
  if( ischeck(s) ){
    return 0;
  }
  
  int ret = 0;
  rep(k,4){
    for(int i=1; i<20; i++){
      int tx = x + dx[k]*i;
      int ty = y + dy[k]*i;
      if( inside(tx,ty) ) break;
      if( field[ty][tx]==1 ){
	//if( s&(1<<num[ty][tx]) ) break;	
	field[ty][tx] = 0;
#if DEB
	st.push(num[ty][tx]);
#endif 
	ret += dfs(tx,ty,s|(1<<num[ty][tx]));
#if DEB
	st.pop();
#endif
	field[ty][tx] = 1;
	break;
      }
    }
  }
  msi[state(x,y,s)] = ret;
  return ret;
}

int main(){

  while(scanf("%d%d",&w,&h),w|h){
    msi.clear();
    memset(num,-1,sizeof(num));
    home = last = 0;
    rep(i,h){
      rep(j,w){
	scanf("%d",&field[i][j]);
	if( field[i][j]==2 ){
	  sx = j;
	  sy = i;
	}
	if( field[i][j]==1 ){
	  num[i][j] = home;
	  home++;
	}
      }
    }

    //last homes
    rep(k,4){
      for(int i=1; i<20; i++){
	int tx = sx + dx[k]*i;
	int ty = sy + dy[k]*i;
	if( inside(tx,ty) )break;
	if( field[ty][tx]==1 ){
	  last |= (1<<num[ty][tx]);
	}
      }
    }
#if DEB
    printf("home:%d  sx,sy = %d,%d\n",home,sx,sy);
    printf("last:%d\n",last);
    rep(i,h){
      rep(j,w){
	printf("%2d ",num[i][j]);
      }
      puts("");
    }
#endif   
    dfs(sx,sy,0);
    printf("%d\n",msi[state(sx,sy,0)]);
  }
  

  return 0;
}

Measured memory_bytes: 32000
#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#define int long long
using namespace std;

#define fin(i,n) for (int i = 0; i < n; i++)
#define fin2(i,a,b) for (int i = a; i < b; i++)
#define ford(i,n) for (int i = n-1; i >= 0; i--)
#define ford2(i,a,b) for (int i = a-1; i >= b; i--)
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define mod 1000000007
#define PI 3.1415926535897932384626
#define EXP1 2.718281828459045
#define BIG 1000000000000000000

#define sl(n) scanf("%lld", &n)
#define sll(n,m) scanf("%lld %lld", &n, &m)
#define slll(n,m,k) scanf("%lld %lld %lld", &n, &m, &k)
#define sllll(n,m,k,o) scanf("%lld %lld %lld %lld", &n, &m, &k, &o)
#define sd(n) scanf("%lf", &n)
#define sdd(n,m) scanf("%lf %lf", &n, &m)
#define sddd(n,m,k) scanf("%lf %lf %lf", &n, &m, &k)
#define sc(c) scanf(" %c", &c)
#define ss(s) scanf("%s", s)
#define sal(t,n) fin(iz,n) { scanf("%lld", &t[iz]); }
#define sad(t,n) fin(iz,n) { scanf("%lf", &t[iz]); }
#define gl(t) scanf(" %[^\n]", t);

#define pc(n) printf("%c\n", n)
#define ps(s) printf("%s\n", s)
#define pss(s) printf("%s\n", s.c_str())
#define pl(n) printf("%lld\n", n)
#define pll(n,m) printf("%lld %lld\n", n, m)
#define plll(n,m,k) printf("%lld %lld %lld\n", n, m, k)
#define pd(n) printf("%lf\n", n)
#define pdd(n,m) printf("%lf %lf\n", n, m)
#define pal(t,n) fin(rz,n) { printf("%lld ", t[rz]); } printf("\n")
#define pad(t,n) fin(rz,n) { printf("%lf ", t[rz]); } printf("\n")

#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
 
#define OK ps("OK")
#define OK1 ps("OK1")
#define OK2 ps("OK2")

#define ll int
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>

#define dll pair<ll, ll>
#define vdll vector<dll>
#define vvdll vector<vdll>

#define vb vector<bool>
#define vvb vector<vb>
#define vd vector<double>
#define vvd vector<vd>
#define vc vector<char>
#define vvc vector<vc>

#define all(v) v.begin(), v.end()
#define vlen(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second

int n;
const int b = 22;
int c[b][b];
int dp[b][1 << b];

int gdp(int i, int mask)
{
    if (i == n) {
        if (mask == (1 << n) - 1) return 1;
        else return 0;
    }
    if (dp[i][mask] == -1) {
        dp[i][mask] = 0;
        for (int j = 0; j < n; ++j) {
            if (c[i][j] && (mask & (1 << j)) == 0) {
                dp[i][mask] += gdp(i+1, mask + (1 << j));
                dp[i][mask] %= mod;
            }
        }
    }
    return dp[i][mask];
}

signed main()
{
    sl(n);
    fin(i, n) sal(c[i], n);
    fill_n(&dp[0][0], b*(1<<b), -1);
    pl(gdp(0, 0));
}

Measured memory_bytes: 721152
#include <bits/stdc++.h>
using namespace std;
#define int long long

bool isprime(int n){
    double rootn = sqrt(n);
    if (n < 2){
        return false;
    }
    else if (n == 2){
        return true;
    }
    else if (n % 2 == 0){
        return false;
    }
    else{
        for(int i = 3; i <= rootn; i += 2){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

// 空のベクトルを二つ渡す。N (>=2) 以下の素数を primes に順番に入れる。
void prime_vectors(int N, vector<int>& primes, vector<bool>& is_prime){
    primes = {};
    is_prime = {};
    for(int i=0; i<=N; i++){
        is_prime.push_back(true);
    }

    primes.push_back(2);
    for(int j=4; j<=N; j+=2){
        is_prime[j] = false;
    }

    int i;
    for(i=3; i*i<=N; i+=2){
        if(!is_prime[i]) continue;
        primes.push_back(i);
        for(int j=2*i; j<=N; j+=i){
            is_prime[j] = false;
        }
    }

    for(; i<=N; i+=2){
        if(is_prime[i]){
            primes.push_back(i);
        }
    }
}

signed main(){
    // cout << fixed << setprecision(10) << flush;

    int w, h;
    cin >> w >> h;
    vector<int> ans = {};
    while(w != 0 && h != 0){
        int wall[h][w][4]; // 上が 0, 右が 1, ...        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                for(int e=0; e<4; e++){
                    wall[i][j][e] = 1;
                }
            }
        }

        for(int i=0; i<h; i++){
            for(int j=0; j<w-1; j++){
                int a;
                cin >> a;
                wall[i][j][1] = a;
                wall[i][j+1][3] = a;
            }
            if(i < h-1){
                // i=h-1 のときは下へは行かない
                for(int j=0; j<w; j++){
                    int a;
                    cin >> a;
                    wall[i][j][2] = a;
                    wall[i+1][j][0] = a;
                }
            }
        }

        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));
        int min_d = 0;

        int dis[h][w];
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                dis[i][j] = -1;
            }
        }
        dis[0][0] = 1;
        
        while(!q.empty()){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            int dx[4] = {0, 1, 0, -1};
            int dy[4] = {-1, 0, 1, 0};

            for(int e=0; e<4; e++){
                if(wall[y][x][e] == 1){
                    // 壁なので通れない
                    // 領域外との通行もこれで防げるはず
                    continue;
                }
                int ny = y + dy[e];
                int nx = x + dx[e];
                if(dis[ny][nx] == -1){
                    q.push(make_pair(ny, nx));
                    dis[ny][nx] = dis[y][x] + 1;
                }
            }

            if(dis[h-1][w-1] != -1){
                // ゴールについた
                min_d = dis[h-1][w-1];
                break;
            }
        }
        ans.push_back(min_d); // ゴールにつかなかったときは min_d = 0 のまま
        cin >> w >> h;
    }

    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << endl;
    }

    return 0;
}


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

int main(){
  ll n; cin >> n;
 vector<ll> a(200000,0);
 vector<ll> ent(n);
 rep(i,n){
   cin >> ent[i];   ll m=ent[i];
   m--;
   a[m]++;
 }
  ll sum=0;
 rep(i,200000){
    ll l=a[i]; sum+=(l*(l-1))/2;
 }
 rep(i,n){
   if(a[ent[i]-1]==0)cout << sum << endl;
   else{
     ll b=a[ent[i]-1]-1;
     cout << sum-b << endl;
   }
 }
}

Measured memory_bytes: 5760
n, m, q = map(int, input().split())
Q = [list(map(int, input().split())) for i in range(q)]

A=[1]*n
#スコアけいさん
score=0
for a in Q:
    if A[a[1]-1]-A[a[0]-1]==a[2]:
        score += a[3]

max_score=score

while True:
    #つぎのAの作成
    count=0
    for i in range(1,n+1):
        if A[-i]!=m:
            next=A[-i]+1
            for j in range(1,i+1):
                A[-j]=next
            break
        else:
            count+=1

    if count==n:
        break

    #スコアけいさん
    score=0
    for a in Q:
        if A[a[1]-1]-A[a[0]-1]==a[2]:
            score += a[3]

    if score>max_score:
        max_score=score

print(max_score)

Measured memory_bytes: 9252
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
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; }

const int MAX_N = 4020;
const int INF = 1145141919;

struct BIT{
    // [1, n]
    vector<int>bit;
    int N;
    void init(int n){
        N = n;
        bit = vector<int>(n, 0);
    }
    BIT(int n=0){
        init(n);
    }
    int sum(int i){
        int s = 0;
        while(i>0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, int x){
        if(i==0)return;
        while(i <= N){
            bit[i] += x;
            i += i & -i;
        }
    }
};

int dp[MAX_N][MAX_N];

int main(){
    
    rep(i,MAX_N)rep(j,MAX_N)dp[i][j] = INF;
    dp[0][0]=0;

    int N;
    cin >> N;
    BIT bit(2*N+10);

    vector<int>bpos(N+2, 0), wpos(N+2, 0);
    for(int i = 1; i <= 2*N; i++){
        char c;
        int a;
        cin >> c >> a;
        if(c=='B')bpos[a] = i;
        else wpos[a] = i;
        bit.add(i, 1);
    }

    for(int b=0; b<=N; b++){
        BIT tmpBit = bit;
        for(int w=0; w<=N; w++){
            chmin(dp[b+1][w], dp[b][w] + tmpBit.sum(bpos[b+1]-1));
            chmin(dp[b][w+1], dp[b][w] + tmpBit.sum(wpos[w+1]-1));
            tmpBit.add(wpos[w+1], -1);
        }
        bit.add(bpos[b+1], -1);
    }

    cout << dp[N][N] << endl;

    return 0;
}

Measured memory_bytes: 63360