akhauriyash/Code-Regression huggingface dataset:
x,y = map(int, input().split())

mod = 10 ** 9 + 7

def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(10 ** 6) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(10 ** 6)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod





def solve():
    if (x + y) % 3 != 0:
        return 0
    ab = (x + y) // 3
    if x < ab or x > 2 * ab:
        return 0
    a = x - ab
    return comb(ab, a)

print(solve())

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll a,b; cin>>a>>b;
  set<ll> s;
  s.insert(a);
  s.insert(b);
  reps(i,3) if(!s.count(i)) cout<<i<<endl;
}

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

typedef long long ll;

int main()
{
	ll a, b, c, d;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	printf("%lld\n", max(max(a*c, a*d), max(b*c, b*d)));
}

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

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
 
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;

int n,k;
string s;

int main() {
    cin >> n >> k >> s;
    bool is_zero = false;
    int cnt = 0;
    int start = 0, i=0;
    int mx = 0;
    while(i<n) {
        while (true) {
            if (s[i] == '0') {
                if (!is_zero) cnt++;
                is_zero = true;
            } else {
                is_zero = false;
            }

            // cout << "cnt" << cnt << endl;
            if (cnt > k) break;
            i++;
            if (i == n) break;
        }

        mx = max (mx, i-start);

        bool flg = false;
        while (true) {
            if (s[start] == '0') {
                flg = true;
            }
            else {
                if (flg) break;
            }
            start++;
            if (start == i) break;
        }
        cnt--;
        if (start == i) break;
    }
    cout << mx << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
   int x;cin>>x;
   if(x<1200)cout<<"ABC"<<endl;
   else cout<<"ARC"<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define INF 1e9
#define MAX_V 51
using namespace std;
typedef vector<int> V;
const V zero(51,0);
struct edge{
  int to,rev;
  V cap;
  edge();
  edge(int to,V cap,int rev):to(to),cap(cap),rev(rev){};
};

bool compare (const V &a,const V &b){
  for(int i=a.size()-1;i>=0;i--)if(a[i]!=b[i])return a[i]<b[i];
  return 0;
}
V min(V &a,V &b){return compare(a,b)? a:b;}

vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,V cap){
  G[from].push_back(edge(to,cap,G[to].size()));
  G[to].push_back(edge(from,cap,G[from].size()-1));  
}

void add(V &a,V &b){for(int i=0;i<(int)a.size();i++)a[i]+=b[i];}
void sub(V &a,V &b){for(int i=0;i<(int)a.size();i++)a[i]-=b[i];}

//?¢?????????????DFS??§??¢???
V dfs(int v,int t,V f){
  if(v == t)return f;
  used[v]=true;
  for(int i=0; i<G[v].size() ;i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap != zero){
      V d = dfs(e.to ,t , min(f,e.cap));
      if(d != zero){
	sub(e.cap,d);
	add(G[e.to][e.rev].cap,d);
	return d;
      }
    }
  }
  return zero;
}

//s??????t???????????§???????±???????
V max_flow(int s,int t){
  V flow=zero;
  for(;;){
    memset(used,0,sizeof(used));
    V f = dfs(s, t, V(51,1e4));
    if(f == zero)return flow;
    add(flow,f);
  }
}

int StoI(string &a,int &i){
  int res=0;
  while(isdigit(a[i])) res=res*10+a[i++]-'0';
  return res;
}

string ItoS(int a){
  string res;
  while(a) res=char(a%10+'0')+res,a/=10;
  if(res.empty()) res="0";
  return res;
}

V StoV(string s){
  if(s=="0") return zero;
  V res(51);
  for(int i=0;i<s.size();i++){
    int a = max(1,StoI(s,i));
    int L = 0;
    if(s[i]=='x')i+=1+(s[i+1]=='^'),L=max(1,StoI(s,i));
    res[L] = a;
  }
  return res;
}

string VtoS(V a){
  string res;
  for(int i=a.size()-1;i>=0;i--){
    if(a[i]==0)continue;
    if(!res.empty()) res+='+';
    if(a[i]>1||i==0) res+=ItoS(a[i]);
    if(i)res+='x';
    if(i>1) res+='^'+ItoS(i);
  }
  if(res.empty()) res="0";
  return res;
}

int main(){
  while(1){
    int n,m;
    cin>>n>>m;
    if(!n&&!m) return 0;
    for(int i=0;i<MAX_V;i++) G[i].clear();
    for(int i=0,a,b;i<m;i++){
      string c;
      cin>>a>>b>>c;
      V vc = StoV(c);
      add_edge(a-1,b-1,vc);
    }

    V ans = max_flow(0,n-1);
    cout<<VtoS(ans)<<endl;
  }
  return 0;
}

Measured memory_bytes: 3304
#include<bits/stdc++.h>
using namespace std;
     
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long int
#define pb push_back
#define endl "\n"
#define ff first
#define ss second
#define N 100009
#define mod 1000000007
#define med 998244353
#define debug cout<<"There There\n";
#define debug1(x) cout<<"\nValue is "<<x<<endl
#define debug2(x,y) cout<<"\nValue is "<<x<<" "<<y<<endl
#define debug3(x,y,z) cout<<"\nValue is "<<x<<" "<<y<<" "<<z<<endl  
#define pr pair<int,int>
#define mx INT_MAX
#define lmx LONG_MAX
#define err return 0
#define cn continue
#define bre break

int n,k;
string s;

int32_t main()
{
	IOS;
	cin>>n>>k>>s;
	for(int i=0;i<n;i++)
	{
		if((i+1)==k)
		{
			cout<<((char)((s[i]-'A')+'a'));
		}
		else
		{
			cout<<s[i];
		}
	}
	cout<<endl;
}	


Measured memory_bytes: 256
li =input().split()
a= int(li[0])
b= int(li[1])

#if a==0 or b==0:
	#c=inta+b
	#print('a')

if a==0 or b==0 or (a+b)%2 != 0:
	c =int(((a+b)/2) + 1)
	#print('b')

else:
	c=int((a+b)/2)
	#print('c')
    
print(c)



Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


double dis(int a,int b,int c,int d){
    return sqrt((a - b) * (a - b) + (c - d) * (c - d));
}


int main(){
    int n;cin >> n;
    vector<P> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].fs >> v[i].sc;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i;
    }
    double t = 0.0;
    do{
        double k = 0.0;
        for (int i = 1; i < n; i++) {
            P p = v[a[i]];
            P q = v[a[i-1]];
            k += dis(p.fs,q.fs,p.sc,q.sc);
        }
        t += k;
    }
    while(next_permutation(ALL(a)));
    double l = 1;
    for (int i = 1; i <= n; i++) {
        l *= i;
    }
    cout <<setprecision(30) << fixed<< t / l << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.readline

def main():
    N, M = map(int, readline().rstrip().split())
    if N == 1 and M == 1:
        print(1)
        return
    if N == 1 or M == 1:
        print(max(N, M) - 2)
        return
    print((N-2) * (M-2))
    return


if __name__ == '__main__':
    main()

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;
const ll INF = 1LL << 60;

int main() {
    int h, w, k; cin >> h >> w >> k;
    V<string> s(h);
    for(int i = 0; i < h; i++) cin >> s[i];

    V<V<int> > vec(h, V<int>(w, 0));
    int cnt = 1;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(s[i][j] == '#'){
                vec[i][j] = cnt;
                cnt++;
            }
        }
    }

    for(int i = 0; i < h; i++){
        for(int j = 1; j < w; j++){
            if(vec[i][j] == 0 && vec[i][j - 1] != 0){
                vec[i][j] = vec[i][j - 1];
            }
        }
        for(int j = w - 2; j >= 0; j--){
            if(vec[i][j] == 0 && vec[i][j + 1] != 0){
                vec[i][j] = vec[i][j + 1];
            }
        }
    }

    for(int j = 0; j < w; j++){
        for(int i = 1; i < h; i++){
            if(vec[i][j] == 0 && vec[i - 1][j] != 0){
                vec[i][j] = vec[i - 1][j];
            }
        }
        for(int i = h - 2; i >= 0; i--){
            if(vec[i][j] == 0 && vec[i][j] == 0 && vec[i + 1][j] != 0){
                vec[i][j] = vec[i + 1][j];
            }
        }
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(j != w - 1) cout << vec[i][j] << ' ';
            else cout << vec[i][j];
        }
        cout << '\n';
    }


    return 0;
}


Measured memory_bytes: 4060
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  vector<string> mat(n);
  rep(i, n) {
    cin >> mat[i];
  }
  vector<string> nextMat(n, string(n, ' '));
  // Here, we check all diffs
  ll ans = 0;
  rep(diff, n) {
    // Update nextMat
    rep(r, n) {
      rep(c, n) {
        nextMat[r][(c+diff)%n] = mat[r][c];
      }
    }
    // Here, nextMat has offset with diff.
    bool isSymmetry = true;
    rep(r, n) {
      for (int c = 0; c < r; ++c) {
        if (nextMat[r][c] != nextMat[c][r]) {
          isSymmetry = false;
          break;
        }
      }
      if (!isSymmetry) { break; }
    }
    if (isSymmetry) {
      ans += n;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 512
program infinity
  implicit none
  character :: s*100
  integer(8) :: k,leng, i, count
  
  read *, s
  read *, k
  count = 0
  leng = len_trim(s)
  do i = 1, leng
    if (s(i:i) == "1") then
      count = i
    else
      exit
    end if 
  end do
  if (count < k) then
    print '(a)', s(count+1:count+1)
  else
    print '(a)', "1"
  end if
  stop
end program infinity

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

using namespace std;

void solve() {
    string s;
    cin >> s;
    int cng = -1;
    char c2 = 'a';
    for (char c: s) {
        if (c2 != c) {
            ++cng;
        }
        c2 = c;
    }
    cout << cng;
}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 3312
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int mathNum = Integer.parseInt(sc.next());
        int priceMathNum = Integer.parseInt(sc.next());
        int start = Integer.parseInt(sc.next());
        List<Integer> list = new ArrayList<>();
        for (int x=1; x<=priceMathNum; x++) {
            list.add(Integer.parseInt(sc.next()));
        }
        int x = 0;
        int y = 0;
        for (int z:list) {
            if (start > z) {
                x++;
            } else {
                y++;
            }
        }
        
        System.out.println(x>y?y:x);
    }
}


Measured memory_bytes: 23252
#include<iostream>
#include<iomanip>
using namespace std;
struct Time{
	int hour;
	int minute;
	
	int timeVolume(){
		return hour*100+minute;
	}
	void show(){
		cout << hour << ':';
		cout << setfill('0') << setw(2) << minute;
	}
};
int main(){
	int n;
	cin >> n;
	
	Time nTime[n];
	for(int i = 0; i < n; i++){
		cin >> nTime[i].hour >> nTime[i].minute;
	}
	
	int m;
	cin >> m;
	Time mTime[m];
	for(int i = 0; i < m; i++){
		cin >> mTime[i].hour >> mTime[i].minute;
	}
	
	Time allTime[n+m];
	for(int i = 0; i < n; i++){
		allTime[i] = nTime[i];
	}
	for(int i = n; i < n+m; i++){
		allTime[i] = mTime[i-n];
	}
	
	for(int i = 0; i < n+m; i++){
		for(int j = i+1; j < n+m; j++){
			if(allTime[i].timeVolume() > allTime[j].timeVolume()){
				Time temp = allTime[i];
				allTime[i] = allTime[j];
				allTime[j] = temp;
			}
		}
	}
	for(int i = 0; i < n+m; i++){
		if(i!=0){
			if(allTime[i].timeVolume() == allTime[i-1].timeVolume()){
				continue;
			}
			cout << ' ';
		}
		allTime[i].show();
	}
	cout << '\n';
	return 0;
}

Measured memory_bytes: 1172
using System;

namespace Application
{
    public class MainClass
    {
        public static void Main(string[] args)
        {
            int result = 0;
            int ATGClengths = 0;
            string input = Console.ReadLine();
            int n = input.Length;
            char[] c = new char[n];

            for (int i = 0; i < n; i++)
            {
                c[i] = input[i];
            }
            for (int i = 0; i < n; i++)
            {
                if (c[i] =='A' || c[i] == 'T' || c[i] == 'G' || c[i] == 'C')
                {
                    ATGClengths++;
                    result = Math.Max(ATGClengths, result);
                }
                else
                {
                    ATGClengths = 0;
                }
            }

            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 11092
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>




using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const int INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;



void solve() {
    int n;
    int N = 200000 + 10;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<ll> res(N, 0);
    res[a[0]] = 1;
    for (int i = 0; i < n - 1; ++i) {
        if (a[i + 1] != a[i])
            res[a[i + 1]] = (res[a[i + 1]] + res[a[i]]) % mod;
        //cout << res[a[i + 1]] << endl;
    }
    cout << res[a[n - 1]] << endl;
    

}

//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    solve();


#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


Measured memory_bytes: 2560
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

int N;

int main() {
	scanf("%d", &N);
	if(N < 111) {
		printf("111\n");
	}
	else if(N > 111 && N < 222) {
		printf("222\n");
	}
	else if(N > 222 && N < 333) {
		printf("333\n");
	}
	else if(N > 333 && N < 444) {
		printf("444\n");
	}
	else if(N > 444 && N < 555) {
		printf("555\n");
	}
	else if(N > 555 && N < 666) {
		printf("666\n");
	}
	else if(N > 666 && N < 777) {
		printf("777\n");
	}
	else if(N > 777 && N < 888) {
		printf("888\n");
	}
	else if(N > 888 && N < 999) {
		printf("999\n");
	}
	else {
		printf("%d\n", N);
	}

	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
#include <algorithm>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <istream>
#include <map>
#include <numeric>
#include <ostream>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>


using namespace std;


int ass[10] = {0, 0, 0, 1, 0, 2, 0, 4, 0, 0};

class Solution {
  string n;
  int dp[10][8][2];
  int rek(int cur, int bm, int eq) {
    if (cur == n.length())
      return bm == 7;
    if (dp[cur][bm][eq] == -1) {
      int rez = 0;
      for (int ctr1 = 0; ctr1 <= (eq ? (n[cur] - '0') : 9); ++ctr1)
        if (ctr1 == 3 || ctr1 == 5 || ctr1 == 7)
          rez += rek(cur + 1, bm | ass[ctr1], eq && ((n[cur] - '0') == ctr1));
      dp[cur][bm][eq] = rez;
    }
    return dp[cur][bm][eq];
  }
 public:
  void solve(std::istream& in, std::ostream& out) {
    memset(dp, -1, sizeof(dp));
    in >> n;
    int rez = 0;
    for (int ctr1 = 0; ctr1 < n.length(); ++ctr1)
      rez += rek(ctr1, 0, ctr1 == 0);
    out << rez;
  }
};

void solve(std::istream& in, std::ostream& out)
{
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}
// Powered by caide (code generator, tester, and library code inliner)


#include <fstream>
#include <iostream>


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


  istream& in = cin;


  ostream& out = cout;

  solve(in, out);
  return 0;
}



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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))
#define F first
#define S second

int main(){
    FAST
    int d; cin >> d;
    cout << "Christmas ";
    for(int i = 0; i < 25 - d; i++){
        cout << "Eve ";
    }
    return 0;
}


Measured memory_bytes: 3536
#include <iostream>
#include <cmath>
#include <numeric>
#define MAX 10000
using namespace std;

/*-- ref. Volume0/0009_PrimeNumber --*/
bool isPrime(int x) {
  if(x == 2) {
	return true;
  }
  
  if(x < 2 || x % 2 == 0) {
	return false;
  }
  for(int i = 3; i <= sqrt(x); i += 2) {
	if(x % i == 0) {
	  return false;
	}
  }
  return true;
}

int main() {
  int pn[MAX] = {};
  int n, i =1, j = 0;

  while(j < MAX) {
	if(isPrime(i)) {
	  pn[j] = i;
	  j++;
	}
	i++;
  }
  
  while(cin >> n) {
	if(n == 0) break;
	cout << accumulate(&pn[0], &pn[n], 0) << endl;
  }
  /*
  for(int k = 0; k < MAX; ++k) {
	cout << pn[k];
	cout << (k < 9999 ? " " : "\n");
  }
  */

  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 ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};


vector<string> f(50);
int dist[60][60];

int main(){
    int H,W;
    int cnt = 0;
    cin >> H >> W;
    rep(i,H) {
	string s;
	cin >> s;
	f[i] = s;
    }

    rep(i,H) {
	rep(j,W) {
	    if(f[i][j] == '.') cnt++;
	}
    }
    cnt -= 2;

    queue<P> q;
    f[0][0] = '#';
    q.push(make_pair(0,0));
    while(!q.empty()) {
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	rep(i,4) {
	    int ny = y + dy[i];
	    int nx = x + dx[i];
	    if(ny >=0 && ny < H && nx >= 0 && nx < W && f[ny][nx] == '.' && dist[ny][nx] == 0) {
		q.push(make_pair(ny,nx));
		dist[ny][nx] = dist[y][x] + 1;
	    }
	}
    }
    // rep(i,H) {
    // 	rep(j,W) cout << dist[i][j];
    // 	cout << endl;
    // }

    if(dist[H-1][W-1] == 0) cout << -1 << endl;
    else cout << cnt - dist[H-1][W-1] + 1 << endl;
    

    
    
    return 0;
}



Measured memory_bytes: 3608
#prag\
ma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define N 200005
using namespace std;
int n,m,dis[N];
bool visited[N];
vector <pair<int,int > > V[N]; 
bool dfs(int x)
{
	visited[x]=true;
	for(int i=0;i<V[x].size();++i)
	{
		int y=V[x][i].first,d=V[x][i].second;
		if(!visited[y])
		{
			dis[y]=dis[x]+d;
			if(!dfs(y)) return false;
		}	
		else if(dis[x]+d!=dis[y]) return false;
	}
	return true;
} 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v,w; scanf("%d%d%d",&u,&v,&w);
		V[u].push_back(make_pair(v,w));
		V[v].push_back(make_pair(u,-w));
	}
	for(int i=1;i<=n;++i)
		if(!visited[i])
			if(!dfs(i))
			{
				printf("No\n");
				return 0;
			}
	printf("Yes\n");
	return 0;
}

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

const int inf = 1e9 + 37;

signed main () {
    int d, g;
    cin >> d >> g;
    vector < int > p(d), c(d);
    for (int i = 0; i < d; ++i)
        cin >> p[i] >> c[i];
    int ans = inf;
    for (int mask = 0; mask < (1 << d); ++mask) {
        int here = 0, cur = 0;
        multiset < int > gang;
        for (int i = 0; i < d; ++i) {
            if (mask & (1 << i)) 
                here += p[i] * 100 * (i + 1) + c[i], cur += p[i];
            else {
                for (int j = 0; j < p[i]; ++j)
                    gang.insert(100 * (i + 1));
            }
        }
        while (!gang.empty() && here < g) {
            here += *prev(gang.end());
            gang.erase(prev(gang.end()));
            ++cur;
        }
        if (here >= g)
            ans = min(ans, cur);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <cstring>
#include <queue>
char kanban[101][101] = { NULL };
using namespace std;
int main() {
	int n;
	int count = 0;
	char base[25] = { NULL };
	scanf("%d", &n);
	scanf("%s", &base);
	for (int i = 1;i <= n;++i) {
		scanf("%s", &kanban[i]);
		for (int first_moji = 0;kanban[i][first_moji] != NULL;++first_moji) {
			if (base[0] == kanban[i][first_moji]) {
				for (int space = 1;kanban[i][first_moji + space] != NULL;++space) {
					int kurikaesi = 1;
					while (true) {
						if (base[kurikaesi] == NULL) {
							count++;
							goto end;
						}
						if (base[kurikaesi] != kanban[i][first_moji + (kurikaesi * space)]) { break; }
						kurikaesi++;
					}
				}
			}
		}
	end:;
	}
	printf("%d\n", count);
}


Measured memory_bytes: 1040
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define downque(que)  priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
typedef long long ll;
const int MOD = 1e9+7;


int main(){
  int n; cin>>n;
  int res=0;
 res =pow(n,2);
  
  cout<<res<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int int_sort( const void *a, const void *b ){
    return *(int *)b - *(int *)a;
}

int main(void){
    // 変数
    int result = 0;
    int subtract = 0;
    int max = 0, max_index = 0;
    int k, n;
    int i;
    int a[210000];
    int total[210000];

    // 入力
    scanf( "%d %d", &k, &n );
    for( i = 0; i < n ; i++ ){
        scanf( "%d", &a[ i ] );
    }

    // 演算
    qsort( (void * )a, n, sizeof( a[0] ), int_sort );

    // 区間毎の距離格納、最大値の要素番号を格納
    for( i = 0 ; i < (n-1) ; i++ ){
        total[ i ] = a[ i ] - a[ i + 1 ];
        if( max < a[ i ] - a[ i + 1 ] ){
            max = a[ i ] - a[ i + 1 ];
            max_index = i;
        }
    }

    // 座標０をまたいだ計算
    subtract = ( k - a[0] ) + a[ n - 1 ];

    // 距離の総和
    for( i = 0; i < ( n - 1 ); i++ ){
        result += total[ i ];
    }

    // 区間毎の最大値と、座標０をまたいだ距離を比較し、どちらが大きいか比較
    if( subtract < max ){
        // 区間毎の方が大きい場合
        result += subtract;
        result -= total[ max_index ];
    }

    // 出力
    printf( "%d\n", result );

    return 0;
}

Measured memory_bytes: 1788
# include<iostream> 
using namespace std; 
int main() 
{

  int n;
  cin>>n;
  int d[n];
  long long sum=0;
  for(int i=0;i<n;i++)
  {
  	cin>>d[i];
  }
  for(int i=0;i<n;i++)
  {
  	for(int j=i+1;j<n;j++)
  	{
  		sum+=(d[i]*d[j]);
  	}
  }
  cout<<sum;
return 0; 
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int N=2e5+5;
using namespace std;
int a[N];
int main()
{
    int n;cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]<a[i-1])
        {
            ans+=a[i-1]-a[i];
            a[i]=a[i-1];
        }
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 4408
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

N = int(input())
CSF = [list(map(int, input().split())) for _ in range(N - 1)]

for i in range(N - 1):
    c, s, f = CSF[i]
    time = s + c
    for csfj in CSF[i + 1 :]:
        c, s, f = csfj
        if time < s:
            time = s
        else:
            time = f * ((time + f - 1) // f)
        time += c
    print(time)

print(0)

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

int main() {
	ll h, n;
	cin >> h >> n;
	vector<vector<ll>>ab(n, vector<ll>(2));
	for (int i = 0; i < n; i++)cin >> ab.at(i).at(0) >> ab.at(i).at(1);
	vector<vector<ll>>dp(n, vector<ll>(h+1,1000000000));
	for (int i = 0; i < n; i++)dp.at(i).at(0) = 0;
	for (int i = 1; i <= h; i++) {
		double x = (double)i / (double)ab.at(0).at(0);
		dp.at(0).at(i) = ab.at(0).at(1) * ceil(x);
	}
	for (int i = 1; i <= n - 1; i++) {
		for (int j = 1; j <= h; j++) {
			if (j <= ab.at(i).at(0)) {
				dp.at(i).at(j) = min(dp.at(i - 1).at(j),ab.at(i).at(1));
			}
			else dp.at(i).at(j) = min(min(dp.at(i - 1).at(j),dp.at(i).at(j-ab.at(i).at(0))+ab.at(i).at(1)),dp.at(i - 1).at(j - ab.at(i).at(0)) + ab.at(i).at(1));
		}
	}
	cout << dp.at(n - 1).at(h) << endl;
	/*for (int i = 0; i < n; i++) {
		for (int j = 0; j < h + 1; j++)cout << " " << dp.at(i).at(j);
		cout << endl;
	}*/
}

Measured memory_bytes: 78592
//
//  main.cpp
//  tarea
//
//  Created by AdÃ¡n LÃ³pez Alatorre on 3/31/17.
//  Copyright Â© 2017 AdÃ¡n LÃ³pez Alatorre. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string.h>
#include <bitset>
#include <set>
#include <cstdio>
#include <cmath>
#include <vector>
#include <iomanip>
#include <stack>
#include <map>
#include <queue>
#include <climits>
#define se second
#define fi first

using namespace std;

typedef  long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> ii;

const int MOD = 998244353, maxN = 1e2 + 6, maxV = 4e6 + 6;



int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    
    int a, b;
    cin >>a >> b;
    
    if(a <= 8 && b <= 8){
        cout << "Yay!\n";
    }
    else{
        cout << ":(\n";
    }
    
}


Measured memory_bytes: 256
/* Code by : Suraj (@suraj1611) */

#include<bits/stdc++.h>
#include <string>

using namespace std;

#define ll long long int
#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mx INT_MAX
#define mn INT_MIN
#define md 1000000007
#define pb push_back
#define mp make_pair
#define pf printf
#define sc scanf
#define maxsize 1100005
#define lb cout<<endl;
#define F first
#define S second
#define print(i) cout<<i<<endl
#define print1(i,j) cout<<i<<" "<<j<<endl
#define label cout<<"hello!"<<endl
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

ll power(ll x, ll  y) 
{ 
    if (y == 0) 
        return 1; 
    else if (y%2 == 0) 
        return power(x, y/2)*power(x, y/2); 
    else
        return x*power(x, y/2)*power(x, y/2); 
} 

int main()
{
	IOS
	
	/*#ifndef ONLINE_JUDGE   
	    freopen("in.txt", "r", stdin);
	    freopen("out.txt", "w", stdout);
	#endif
*/
	ll H,W,h,w;
	cin>>H>>W>>h>>w;
	cout<<(H-h)*(W-w);

	/*#ifndef ONLINE_JUDGE
    	cout<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s\n";
    #endif*/

    return 0;
}

Measured memory_bytes: 256
n = 5.times.map { gets.to_i }
m = n.permutation(5).map { |a,b,c,d,e|
  t = 0

  t += a
  i,j = t.divmod(10)
  t = (j == 0)? i * 10 : (i+1) * 10

  t += b
  i,j = t.divmod(10)
  t = (j == 0)? i * 10 : (i+1) * 10

  t += c
  i,j = t.divmod(10)
  t = (j == 0)? i * 10 : (i+1) * 10

  t += d
  i,j = t.divmod(10)
  t = (j == 0)? i * 10 : (i+1) * 10

  t += e
  t
}

puts m.min

Measured memory_bytes: 1788
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <cassert>
#include <iomanip>

using namespace std;

#define pb push_back
#define dump(x)  cout << " "<< #x << " = " << (x) << endl;
typedef long long ll;
typedef complex<int> P;
const double EPS = 1e-10;
const double PI  = acos(-1.0);



struct st{
	vector<P> vp;
	vector<P> rvp;
};


P d[] = { P(1,0), P(0,1), P(-1,0), P(0,-1) };

void f(vector<P> &vp){
	P p0 = vp[0];
	for(int i=0;i<vp.size();i++) vp[i] -= p0;
	P a = vp[0], b = vp[1];
	int num = 0;
	if(a.real() == b.real()){
		if(a.imag() < b.imag()) num = 3;
		else num = 1;
	}else if(a.imag() == b.imag()){
		if(a.real() < b.real()) num = 0;
		else num = 2;
	}else{
		cout<< "err"<< endl;
	}
	for(int i=0;i<vp.size();i++){
		vp[i] *= d[num];
	}
	return;
}

bool solve(int n){
	vector<st> vst(n+1);
	
	int m; cin>> m;
	vector<P> tmp, rtmp;
	for(int i=0;i<m;i++){
		P in;
		cin>> in.real()>> in.imag();
		tmp.pb(in);
	}
	rtmp = tmp;
	reverse(rtmp.begin(), rtmp.end());
	f(tmp);
	f(rtmp);
	vst[0].vp = tmp;
	vst[0].rvp = rtmp;
	
	for(int i=1;i<n+1;i++){
		int m2; cin>> m2;
		vector<P> tmp;
		for(int j=0;j<m2;j++){
			P in;
			cin>> in.real()>> in.imag();
			tmp.pb(in);
		}
		f(tmp);
		vst[i].vp = tmp;
	}
	
/*	for(int i=0;i<n+1;i++){
		cout<< " "<< i<< endl;
		for(int j=0;j<m;j++) cout<< " "<< vst[i].vp[j].real()<< " "<< vst[i].vp[j].imag()<< endl;
		if(i==0){
			cout<< " "<< i<< endl;
			for(int j=0;j<m;j++) cout<< " "<< vst[i].rvp[j].real()<< " "<< vst[i].rvp[j].imag()<< endl;
		}
	}
*/	
	
	for(int i=1;i<n+1;i++){
		if(vst[0].vp.size() != vst[i].vp.size()) continue;
		for(int k=0;k<2;k++){
			int flg = true;
			for(int j=0;j<m;j++){
				if(vst[i].vp[j] != vst[0].vp[j]){
					flg = false;
					break;
				}
			}
			if(flg) cout<< i<< endl;
			swap(vst[0].vp, vst[0].rvp);
		}
	}
	cout<< "+++++"<< endl;
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	int n;
	while(cin>>n, n) solve(n);
	return 0;
}

 

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin >> n;
    int l[n];
    for (int i=0; i<n; i++){
        cin >> l[i];
    }
    int max = *max_element(l , l + n);
    if (max < accumulate(l, l+n, -max)){
        cout << "Yes";
    } else { cout << "No";}
}

Measured memory_bytes: 256
#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;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    int n;
    cin >> n;
    string s;
    set<string> S;
    rep(i, n) {
        cin >> s;
        S.insert(s);
    }
    cout << S.size() << endl;
    return 0;
}

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

int main(){
    int n, l, minimum;
    cin >> n >> l;
    int t = n * (n + 1) / 2 + n * (l - 1);
    if(l <= 0 && 0 <= l + n - 1){
        minimum = 0;
    } else if(abs(l) < abs(l + n - 1)){
        minimum = l;
    } else {
        minimum = l + n - 1;
    }
    cout << t - minimum << endl;
    return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,q,s,t;
  cin>>n>>q>>s>>t;
  s*=-1;t*=-1;
  vector<Int> a(n+1);
  for(Int i=0;i<=n;i++) cin>>a[i];

  vector<Int> b(n+1);
  for(Int i=1;i<=n;i++) b[i]=a[i]-a[i-1];

  Int ans=0;
  for(Int i=1;i<=n;i++)
    ans+=(b[i]>0?s:t)*b[i];

  for(Int i=0;i<q;i++){
    Int l,r,x;
    cin>>l>>r>>x;
    r++;
    
    ans-=(b[l]>0?s:t)*b[l];
    b[l]+=x;
    ans+=(b[l]>0?s:t)*b[l];
    
    if(r<=n){
      ans-=(b[r]>0?s:t)*b[r];
      b[r]-=x;
      ans+=(b[r]>0?s:t)*b[r];
    }

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



Measured memory_bytes: 5980
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
	int array[100]={0};
	int n;cin>>n;
	int count=0;
	for(int i=0;i<n;i++)
	{
		cin>>array[i];
		if((i+1)%2!=0)
		{
			if(array[i]%2!=0)
			count++;
		}
	}
	cout<<count<<endl;
 }

Measured memory_bytes: 3572
s=input()
l = []
l.append(s[0])
c = 0
for i in range(1, len(s)):
  if s[i] == l[i-1]:
    c += 1
    l.append(str(-(int(s[i])-1)))
  else:
    l.append(s[i])
print(c)


Measured memory_bytes: 6772
w = gets.chomp.downcase
res = 0
while line = gets
  break if line.chomp == 'END_OF_TEXT'
  line.chomp.split(' ').each do |ww|
    ww.sub!(/\./, '')
    ww.downcase!
    if ww == w
      res += 1
    end
  end
end
puts res

Measured memory_bytes: 6100
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int>g[N];
int freq[N],bad,dp[N],ans = 1e9,n,sz[N];
bool col[N],vis[N];
queue<int>q;
string s;
void calc(int u,int p){
	vis[u] = 1;
	int at = (sz[u] + col[u])&1 ? 0 : -2,mn = 1e9,mn2 = 1e9;
	for(auto i : g[u])
		if(i != p && !vis[i]){
			calc(i,u);
			mn2 = min(mn2,dp[i]);
			if(mn2 < mn)swap(mn,mn2);
		}
	dp[u] = min(0,mn) + at;
	ans = min(ans,min(dp[u],mn + mn2 + at));
}
int main(){
	//freopen("readin.txt","r",stdin);
	scanf("%d",&n);
	for(int i = 1,a,b;i < n;i++)
		scanf("%d%d",&a,&b),
		g[--a].push_back(--b),
		g[b].push_back(a);
	cin >> s;
	int temp = 0;
	for(int i = 0;i < n;i++)col[i] = s[i] == 'B';
	for(int i = 0;i < n;i++)temp+=!col[i];
	if(!temp)return printf("%d\n",temp),0;
	for(int i = 0;i < n;i++)
		if(g[i].size() == 1 && col[i])q.push(i),vis[i] = 1;
	temp = 0;
	while(!q.empty()){
		int x = q.front();
		temp++;
		q.pop();
		for(auto i : g[x])
			if((++freq[i]) + 1 == g[i].size() && col[i])
				vis[i] = 1,
				q.push(i);
	}
	for(int i = 0;i < n;i++)
		for(auto j : g[i])sz[i]+=!vis[j];
	for(int i = 0;i < n;i++)
		if(!vis[i] && !((sz[i] + col[i])&1))bad++;
	for(int i = 0;i < n;i++)if(!vis[i] && !col[i])calc(i,-1);
	if (temp + 1 == n)printf("1\n");
	else printf("%d\n",2*(n - 1 - temp) + ans + bad);
}


Measured memory_bytes: 14720
#include <bits/stdc++.h>
#define N 500006
#define mo 1000000009
using namespace std;
char c[N];bool f[4*N];
int n,nowl=1,cs,s[4*N][10];
inline int read()
{
	int x=0,c=getchar();while(c<48)c=getchar();
	while(c>47)x=x*10+c-48,c=getchar();return x;
}
void down(int i,int l,int r)
{
	if(f[i]){
		f[i]=0;s[i][9]=0;s[i][0]=1;
		if(l!=r)f[i<<1]=1;f[i<<1|1]=1;
	}
}
void build(int i,int l,int r)
{
	if(l==r){s[i][c[l]-48]=1;return;}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);build(i<<1|1,mid+1,r);
	for(int j=0;j<10;j++)s[i][j]=s[i<<1][j]&s[i<<1|1][j];
}
bool pd(int i,int l,int r,int x,int y)
{
	down(i,l,r);
	if(l==r)return s[i][y];
	int mid=(l+r)>>1;
	if(x<=mid)return pd(i<<1,l,mid,x,y);
	else return pd(i<<1|1,mid+1,r,x,y);
}
void add(int i,int l,int r,int x)
{
	down(i,l,r);
	if(l==r){
		for(int j=0;j<10;j++)
			if(s[i][j]){s[i][j]=0,s[i][j+1]=1;break;}
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)add(i<<1,l,mid,x);
	else add(i<<1|1,mid+1,r,x);
	down(i<<1,l,mid);down(i<<1|1,mid+1,r);
	for(int j=0;j<10;j++)s[i][j]=s[i<<1][j]&s[i<<1|1][j];
}
void change(int i,int l,int r,int x,int y)
{
	down(i,l,r);
	if(x<=l&&r<=y){f[i]=1;return;}
	int mid=(l+r)>>1;
	if(x<=mid)change(i<<1,l,mid,x,y);
	if(y>mid)change(i<<1|1,mid+1,r,x,y);
	down(i<<1,l,mid);down(i<<1|1,mid+1,r);
	for(int j=0;j<10;j++)s[i][j]=s[i<<1][j]&s[i<<1|1][j];
}
int find(int i,int l,int r)
{
	down(i,l,r);
	if(s[i][9])return l;if(l==r)return r+1;
	int mid=(l+r)>>1;down(i<<1|1,mid+1,r);
	if(s[i<<1|1][9])return find(i<<1,l,mid);
	else return find(i<<1|1,mid+1,r);
}
int find(int i,int l,int r,int x,int y)
{
	down(i,l,r);
	if(s[i][y])return r;if(l==r)return l-1;
	int mid=(l+r)>>1;
	if(x<=mid){
		int a=find(i<<1,l,mid,x,y);
		if(a==mid)return find(i<<1|1,mid+1,r,x,y);
		else return a;
	}
	else return find(i<<1|1,mid+1,r,x,y);
}
int main()
{
	scanf("%s",c+1);n=strlen(c+1);build(1,1,n);
	while(1){
		cs++;
		int R=nowl,L=nowl;
		for(int i=0;i<=9;i++)
			if(pd(1,1,n,R,i))L=R,R=find(1,1,n,R,i)+1;
		if(R==n+1)return printf("%d\n",cs),0;
		else{
			nowl=L+1;
			if(pd(1,1,n,n,9))R=find(1,1,n),add(1,1,n,R-1),change(1,1,n,R,n);
			else add(1,1,n,n);
		}
	}
}

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef vector<int> vi;

int main()
{
    int n;
    while(cin >>n,n)
    {
        //schedule
        int s[50][31]={0};

        rep(i,n)
        {
            int f;
            cin >>f;
            rep(j,f)
            {
                int d;
                cin >>d;
                s[i][d]=1;
            }
        }

        int ans=-1;
        vector<vi> v(n,vi(n,0));

        rep(i,n) v[i][i]=1;

        //i-th day
        for(int i=1; i<=30; ++i)
        {
            vi G[50];
            rep(j,n)rep(k,j)
            {
                if(s[j][i] && s[k][i])
                {
                    G[j].pb(k);
                    G[k].pb(j);
                }
            }

            //root-j BFS
            vi vv(n);
            rep(j,n)
            {
                if(vv[j]) continue;

                vi vis(n);
                vis[j]=1;
                queue<int> que;
                que.push(j);
                while(!que.empty())
                {
                    int now=que.front();
                    que.pop();
                    rep(k,G[now].size())
                    {
                        int nx=G[now][k];
                        if(!vis[nx])
                        {
                            que.push(nx);
                            vis[nx]=1;
                        }
                    }
                }

                vi p(n);
                rep(k,n)
                {
                    if(vis[k])
                    {
                        rep(l,n) p[l]|=v[k][l];
                    }
                }

                rep(k,n)
                {
                    if(vis[k])
                    {
                        rep(l,n) v[k][l]|=p[l];
                    }
                }

                rep(k,n) vv[k]|=vis[k];
            }

            rep(j,n)
            {
                int ct=0;
                rep(k,n) ct+=v[j][k];
                if(ct==n)
                {
                    ans=i;
                    break;
                }
            }

            if(ans>0) break;
        }

        printf("%d\n", ans);
    }
    return 0;
}

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

using ll = long long;

bool is_all_same(const string &s) {
  for (int i = 1; i < s.size(); i++) {
    if (s.front() != s.at(i)) {
      return false;
    }
  }
  return true;
}

int solve(const string &s) {
  char pre_char = '+';
  int count = 0;
  int num_to_rewrite = 0;
  for (char c : s) {
    if (c == pre_char) {
      count++;
      if(count % 2 == 0) {
        num_to_rewrite++;
      }
    } else {
      pre_char = c;
      count = 1;
    }
  }
  return num_to_rewrite;
}

int main() {
  string S;
  cin >> S;
  int K;
  scanf("%d", &K);

  // Sが1文字で構成される場合は、|S| * K / 2 を求める
  if(is_all_same(S)) {
    printf("%lld", (ll)S.size() * (ll)K / 2LL);
    return 0;
  }
  
  string SS = S + S;
  // 書き換える操作の数は等差数列となり、初項と第二項を求め、K番目を求める
  int first = solve(S);
  int second = solve(SS);
  int diff = second - first;
  printf("%lld", (ll)first + ((ll)diff * (ll)(K - 1)));

  return 0;
}

Measured memory_bytes: 256
import sys
import collections
from functools import lru_cache
d = collections.defaultdict(list)
@lru_cache(maxsize=None)
def alg_memoization_recursion(f):
    mt = 0
    for v in d[f]:
        mt = max(mt, alg_memoization_recursion(v) + 1)
    return mt


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    sys.setrecursionlimit(10 ** 6)
    n, m = list(map(int, readline().split()))
    for i in range(m):
        x, y = list(map(int, readline().split()))
        d[x-1] += [y-1]
    mt = 0
    for i in range(n):
        mt = max(mt, alg_memoization_recursion(i))
    print(mt)


if __name__ == '__main__':
    solve()


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

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 200005, mod = 1000000007;
int n, k, cero;
vi neg, pos;

ll pot (ll b, int p) {
	ll res = 1;
	while (p) {
		if (p & 1) (res *= b) %= mod;
		(b *= b) %= mod;
		p /= 2;
	}
	return res;
}

void go () {
	ll acu = 1, res;
	int cn = 0, i = 0, j = 0;

	while (cn + 2 <= k && i + 1 < neg.size()) {
		(acu *= neg[i] * neg[i + 1] % mod) %= mod;
		cn += 2;
		i += 2;
	}

	while (cn + 1 <= k && j < pos.size()) {
		(acu *= pos[j]) %= mod;
		cn++;
		j++;
	}

	if (cn < k) return;

	res = acu;

	while (i >= 2 && j + 1 < pos.size()) {
		ll x = neg[i - 1] * neg[i - 2];
		ll y = pos[j] * pos[j + 1];
		if (x > y) break;

		(acu *= pot(x % mod, mod - 2)) %= mod;
		(acu *= y % mod) %= mod;
		res = acu;

		i -= 2;
		j += 2;
	}

	cout << res << endl;
	exit(0);
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n >> k;

	forn (i, n) {
		int a;
		cin >> a;
		if (a < 0) neg.pb(-a);
		else if (a > 0) pos.pb(a);
		else cero++;
	}

	sort(all(neg), greater<ll>());
	sort(all(pos), greater<ll>());

	go();

	if (cero) cout << 0 << endl;
	else {
		ll res = 1;

		sort(all(pos));
		sort(all(neg));

		int i = 0, j = 0;

		forn (kk, k) {
			if (i < pos.size() && (j == neg.size() || pos[i] < neg[j])) {
				(res *= pos[i]) %= mod;
				i++;
			} else {
				(res *= -neg[j]) %= mod;
				j++;
			}
		}

		cout << MOD(res, mod) << endl;
	}

	return 0;
}


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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto&& x : v){cout << x << " ";} cout << endl
#define printVV(vv) for(auto&& v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto&& p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;
template<typename T> using Graph = vector<vector<T>>;

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

    int N, d;
    cin >> N >> d;
    vi p(N);
    rep(i, N) cin >> p[i];
    int ans = 0;
    rep(i, N) ans += max(0ll, p[i] - d);
    if (ans == 0) {
        cout << "kusoge" << endl;
    } else {
        cout << ans << endl;
    }
}

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

const int N =100010, inf=0x3f3f3f3f;
int dp[N];
int main(){
  int n;scanf("%d", &n);
  memset(dp, inf, sizeof dp);
  dp[0]=0;
  vector<int> v(n);
  for(int i=0;i<n;i++)scanf("%d", &v[i]);

  for(int i=0;i<n;i++)
  {
    if(i<=n-1)
      dp[i+1]=min(dp[i+1], dp[i]+abs(v[i]-v[i+1]));
    if(i<=n-2)
      dp[i+2]=min(dp[i+2], dp[i]+abs(v[i]-v[i+2]));
  }
  printf("%d\n", dp[n-1]);
}


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

void print_sort(vector<int> A)
{
    int i;
    int N = A.size();
    for (i = 0; i < N; ++i)
    {
        if (i == N - 1)
        {
            cout << A[i] << endl;
        }
        else
        {
            cout << A[i] << " " << flush;
        }
    }
}

void insertionSort(vector<int> A) // N個の要素を含む0-オリジンの配列A
{
    int i;
    int N = A.size();
    for (i = 1; i <= N; ++i)
    {
        print_sort(A);

        int v = A[i];
        int j = i - 1;

        while (j >= 0 && A[j] > v)
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
    }
}
int main()
{
    int N;
    vector<int> A;

    cin >> N;
    int i;
    A.reserve(N);
    for (i = 0; i < N; ++i)
    {
        int n;
        cin >> n;
        A.push_back(n);
    }
    insertionSort(A);
}


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

#define ll long long
#define pb push_back
#define fi first
#define se second

/** Dateloper */

using namespace std;

const int mod = 1e9+7;
const int maxn = 1000 * 1000 + 10;

int main()
{
    int n;
    cin>>n;
    vector<int>a(n),b(n);
    for(auto &i:a)
        cin>>i;
    for(auto &i:b)
        cin>>i;
    int cnt=0;
    vector<int>v(n);
    for(int i = 0;i<n;i++)
        v[i]=i+1;
        int pos1,pos2;
    do{
        cnt++;
        if(v==a)
            pos1=cnt;
        if(v==b)
            pos2=cnt;
    }
    while(next_permutation(v.begin(),v.end()));
    cout<<abs(pos1-pos2);
    return 0;
}


Measured memory_bytes: 256