akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author apurba_debnath
 */

#include <bits/stdc++.h>

#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl

using namespace std;

class CStep {
public:
    void solve(std::istream &in, std::ostream &out) {
        ll n, stools = 0, mx = LONG_LONG_MIN;
        in >> n;
        vector<ll> v(n);
        for (ll i = 0; i < n; ++i) {
            in >> v[i];
            mx = max(mx, v[i]);
            if (i > 0) {
                if (v[i] < mx)
                    stools += mx - v[i];
            }
        }
        out << stools;
    }
};


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

    CStep solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);

    return 0;
}


Measured memory_bytes: 4756
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define rep(i,n) for(int i=0;i<n;i++)
int gcd(int a, int b){
    int r=1;
    while(r!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void revStr(char* str){
    int size = strlen(str);
    int i,j;
    char tmp = {0};
    for(i = 0, j = size - 1; i < size / 2; i++, j--){
        tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }return;
}
typedef struct{
    int a,b,c;
}data;

//昇順
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
//構造体降順
int comp( const void *c1, const void *c2 )
{
  data test1 = *(data *)c1;
  data test2 = *(data *)c2;
  int tmp1 = test1.b;   /* b を基準とする */
  int tmp2 = test2.b;
  return tmp2 - tmp1;
}

#define MAXSIZE 200000
int list[MAXSIZE];
int tail;

void Init(void){
    tail=0;
}
int Top(void){
    return 0;
}

int Next(int pos){
    if(pos<tail-1){
        return pos+1;
    }else{
        return -1;
    }
}
int Count(void){
    return tail;
}

int Item(int pos){
    if((pos>=0)&&(pos<tail)){
        return list[pos];
    }else{
        return 0;
    }
}
void Add(int value){
    if(tail<MAXSIZE){
        list[tail]=value;
        tail++;
    }
}
void Delete(int pos){
    if((pos>=0)&&(pos<tail)){
        int i;
        for(i=pos;i<tail-1;i++){
            list[i]=list[i+1];
        }
        tail--;
    }
}

int main(){
    int A,B,M;
    scanf("%d%d%d",&A,&B,&M);
    int ref[A];
    int wav[B];
    data sale[M];
    rep(i,A){
        scanf("%d",&ref[i]);
    }
    rep(i,B){
        scanf("%d",&wav[i]);
    }
    rep(i,M){
        scanf("%d%d%d",&sale[i].a,&sale[i].b,&sale[i].c);
    }
    int fct[M+1];
    rep(i,M){
        fct[i]=ref[sale[i].a-1]+wav[sale[i].b-1]-sale[i].c;
    }
    qsort(ref,A,sizeof(int),compare_int);
    qsort(wav,B,sizeof(int),compare_int);
    fct[M]=(ref[0]+wav[0]);
    qsort(fct,M+1,sizeof(int),compare_int);
    printf("%d",fct[0]);
}


Measured memory_bytes: 4456
/*********************
*  Author: xuziyuan  * 
*********************/
 
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
 
using namespace std;
 
LL n,m,x,y,re[60],ans=0;
vector <pii> g[60];
vector <LL> pass;
bool ok;
 
void dfs(LL pos,LL to,LL no)
{
  if(pos==to)
  {
    ok=true;
    return;
  }
  rep(i,g[pos].size())
  {
    if(g[pos][i].fi==no) continue;
    pass.pb(g[pos][i].se);
    dfs(g[pos][i].fi,to,pos);
    if(ok) return;
    pass.pop_back();
  }
}
 
int main()
{
  cin>>n;
  rep(i,n-1)
  {
    cin>>x>>y;
    g[x].pb(mpr(y,i));
    g[y].pb(mpr(x,i));
  }
  cin>>m;
  rep(i,m)
  {
    cin>>x>>y;
    ok=false;
    dfs(x,y,0);
    rep(j,pass.size()) re[i]|=(LL)pow(2,pass[j]);
    pass.clear();
  }
  rep(i,1<<m)
  {
    LL cnt=0,now=0;
    rep(j,m)
    {
      if((i&(1<<j))==0) continue;
      now|=re[j];
      cnt++;
    }
    LL c=0;
    while(now>0)
    {
      c+=now%2;
      now/=2;
    }
    if(cnt&1) ans-=(LL)pow(2,n-1-c);
    else ans+=(LL)pow(2,n-1-c);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <math.h>
 
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
 
	int x,y,z;
	cin >> x >> y;
    z = x*x-y;
    cout << z << "\n";
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int x,a,b;
    scanf("%d %d %d",&x,&a,&b);
    if(abs(x-a)<abs(x-b))
        printf("A\n");
    else
        printf("B\n");



    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
  int a,b;
  cin>>a>>b;
  if(a==1&&b==1) cout<<"Draw"<<endl;
  else if(a==1) cout<<"Alice"<<endl;
  else if(b==1) cout<<"Bob"<<endl;
  else if(a==b) cout<<"Draw"<<endl;
  else if(a>b) cout<<"Alice"<<endl;
  else cout<<"Bob"<<endl;

  return 0;
}


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

int main() {
	
	int a, b;
	cin >> a >> b;
	if(a * b % 2 == 1) puts("Odd");
	else puts("Even");
	
	return 0;
}

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

main(){
	int m[6]={1,5,10,50,100,500};
	int sumv = 0;
	for(int i=0; i<6; ++i){
		int c; cin>>c;
		sumv += m[i]*c;
	}
	cout<<(sumv>=1000?1:0)<<endl;
}


Measured memory_bytes: 3112
#include <iostream>
#include <string>
using namespace std;


int main(){

    string S;
    cin >> S;


    bool abc[3] = { false, false, false };
    bool ans = true;

    for( int i = 0; i < 3; i++ ){
        if( S[i] == 'a' ) abc[0] = true;
        if( S[i] == 'b' ) abc[1] = true;
        if( S[i] == 'c' ) abc[2] = true;
    }

    for( int i = 0; i < 3; i++ ){
        if( ! abc[i] ){
            cout << "No" << endl;
            ans = false;
            break;
        }
    }

    if( ans ) cout << "Yes" << endl;

    return 0;

}

Measured memory_bytes: 256
def pow(a,n,p):
    if n==1:
        return a%p
    elif n%2==1:
        return a*pow(a,n-1,p)
    else:
        return (pow(a,n//2,p)**2)%p
from math import factorial as f
 
def nCr(n,r,p):
    r=min(r,n-r)
    if r==0:
        return 1
    x,y=1,1
    for i in range(r):
        x=x*(n-i)%p
        y=y*(i+1)%p
    return x*pow(y,p-2,p)%p


n, a, b = map(int, input().split())

ans = (pow(2, n, 10**9 + 7) - 1 - nCr(n, a, 10**9 + 7) - nCr(n, b, 10**9 + 7)) % (10**9 + 7)

print(ans)

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

int main(void){
		int n,m,l;
		cin >> n >> m >> l;
		int a[n][m];
		int b[m][l];
		long long c[n][l];

		for(int i = 0;i < n;i++){
				for(int j = 0;j < m;j++){
						a[i][j] = 0;
				}
		}
		for(int i = 0;i < m;i++){
				for(int j = 0;j < l;j++){
						b[i][j] = 0;
				}
		}
		for(int i = 0;i < n;i++){
				for(int j = 0;j < l;j++){
						c[i][j] = 0;
				}
		}
		//配列へ入力
		
		for(int i = 0;i < n;i++){
				for(int j = 0;j < m;j++){
						cin >> a[i][j];
				}
		}
		for(int i = 0;i < m;i++){
				for(int j = 0;j < l;j++){
				cin >> b[i][j];
				}
		}
		//計算、出力
		for(int i = 0;i < n;i++){
				for(int j = 0;j < l;j++){
						for(int k = 0;k < m;k++){
								c[i][j] += a[i][k] * b[k][j];
						}
						cout << c[i][j] ;
						if( j != l-1){
								cout << " ";
					    }	
				}
				cout << endl;
		}
		return 0;
}

Measured memory_bytes: 1312
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 1e2 + 5  , M = 2e5 + 4 , MOD = 1e9 + 7;
int arr[N] ,n , k;
ll mem[N][M];
ll solve(int idx ,int rem){
    if(rem < 0)
        return 0 ;
    if(idx == n){
      return (rem == 0);
    }
    ll &ret = mem[idx][rem] ;
    if(~ret)
        return ret ;
    ret = ( (solve(idx , rem - 1) % MOD) + (solve(idx + 1 , rem) % MOD) - solve(idx+1 , rem - arr[idx] - 1) + 2 * MOD);
    ret%=MOD;
    return ret ;

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(mem , -1 , sizeof mem);
    cin >> n >> k ;
    for(int i = 0 ; i < n; ++i){
        cin >> arr[i];
    }
    cout << solve(0 , k) %MOD;
    return 0;
}


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

long long seven(long n) {
    long l = 0;
    for (long i = 0; i < n; ++i) {
        l += 7 * pow(10, i);
    }
    return l;
}

long order(long x) {
    return log(x) / log(10) + 1;
}

int main() {
    long K;
    cin >> K;
    long a = 0;
    long b = order(K);
    long long l = seven(b);

    if (l >= K) {
        a = b;
    }
    else {
        a = b+1;
        l =seven(a);
    }
    
    for (int i = 0; i < K; ++i) {
        long r = l % K;
        if (r == 0) {
            cout << a << endl;
            return 0;
        }
        else {
            long long c = order(r);
            l = r * pow(10, b-c) + seven(b-c);
            if (l >= K) {
                a += b - c;
            }
            else {
                a += b - c + 1;
                l = r * pow(10, b-c+1) + seven(b-c+1);
            }
        }
    }
    cout << -1 << endl;

    return 0;
}

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

typedef struct  {
	double x;
	double y;
}Vec;

int main(int argc, const char * argv[]) {
	
	Vec p1,p2;
	
	scanf("%lf %lf %lf %lf",&p1.x,&p1.y,&p2.x,&p2.y);
	
	double ans = sqrt(pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2));
	
	printf("%f\n",ans);
	return 0;
	
}

Measured memory_bytes: 652
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	s := getNextString(scanner)
	t := getNextString(scanner)
	cs := make([]int, 26)
	ct := make([]int, 26)
	n := len(s)
	m := len(t)
	for i := 0; i < n; i++ {
		cs[s[i]-'a']++
	}
	for i := 0; i < m; i++ {
		ct[t[i]-'a']++
	}
	ss := make([]string, 0)
	for i := 0; i < 26; i++ {
		for j := 0; j < cs[i]; j++ {
			ss = append(ss, fmt.Sprintf("%c", 'a'+i))
		}
	}
	tt := make([]string, 0)
	for i := 26 - 1; i >= 0; i-- {
		for j := 0; j < ct[i]; j++ {
			tt = append(tt, fmt.Sprintf("%c", 'a'+i))
		}
	}
	if strings.Compare(strings.Join(ss, ""), strings.Join(tt, "")) == -1 {
		fmt.Fprintln(writer, "Yes")
		return
	}
	fmt.Fprintln(writer, "No")
}


Measured memory_bytes: 1824
#include <iostream>

typedef long long ll;

int n, a;
int x[51];
ll dp[51][51][3000];

int main(){
	std::cin >> n >> a;
	for(int i = 0; i < n; ++i)std::cin >> x[i];
	
	dp[0][0][0] = 1;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			for(int k = 0; k < 2600; ++k){
				if(dp[i][j][k] == 0)continue;
				
				dp[i + 1][j][k] += dp[i][j][k];
				dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
				
			}
		}
	}
	
	ll ans = 0;
	for(int i = 1; i <= n; ++i){
		ans += dp[n][i][i * a];
	}
	
	std::cout << ans << std::endl;
	
	return 0;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5005;
int Dp[N][N],dp[N][N];
int n,k,x[N];
bool check(int mid)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<k;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(i!=mid&&j-x[i]>=0)dp[i][j]+=dp[i-1][j-x[i]];
		}
	}
	for(int i=0;i<k;i++)
	{
		if(dp[n][i]&&i+x[mid]>=k)
		{
			return true;
		}
	}
	return false;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>x[i];
	sort(x+1,x+1+n);
	dp[0][0]=1;
	int l=0,r=n;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
			r=mid-1;
		else
			l=mid+1;
	}
	cout<<r<<endl;
	return 0;
}

Measured memory_bytes: 98048
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; ++i) {
		cin >> S[i];
	}
	int xl = inf, xr = -inf, yl = inf, yr = -inf;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (S[i][j] == 'B') {
				xl = min(xl, i + j);
				xr = max(xr, i + j);
				yl = min(yl, i - j);
				yr = max(yr, i - j);
			}
		}
	}
	cout << max(xr - xl, yr - yl) << endl;
	return 0;
}


Measured memory_bytes: 3572
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(M)]
V = [x for x in range(N+1)]
total = N * (N-1) // 2

def find(A, x):
    parent = A[x]
    if parent == x: return x
    root = find(A, parent)
    A[x] = root
    return root

def union(A, x, y):
    root, second = find(A, x), find(A, y)
    if root > second:
        second, root = root, second
    A[second] = root

conv = 0
answer = []
group = [1] * (N+1)
for a, b in AB[::-1]:
    answer.append(total - conv)
    root_A = find(V, a); root_B = find(V, b)
    if root_A != root_B:
        conv += group[root_A] * group[root_B]
        group[root_A] += group[root_B]
        group[root_B] = group[root_A]
        union(V, a, b)

for x in answer[::-1]:
    print(x)


Measured memory_bytes: 38116
#include <bits/stdc++.h>
using namespace std;
 
int main() {
string s;
cin>>s;
if(s=="Sunny"){
cout<<"Cloudy"<<endl;
}
if(s=="Cloudy"){
cout<<"Rainy"<<endl;
}
if(s=="Rainy"){
cout<<"Sunny"<<endl;
}
}

Measured memory_bytes: 256
#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 main(){
	int n;cin>>n;
	if ( n % 2 == 0){
		cout << n/2 - 1<<endl;
	} 
	else{
		cout << n / 2 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int64_t N, ans = 0;
    cin >> N;
    vector<vector<int64_t>> A(9, vector<int64_t> (9));
    vector<int64_t> B(9);
    for (int i = 1; i <= N; i++){
        string s = to_string(i);
        if (s.at(0) == '0' || s.at(s.size() - 1) == '0'){
            continue;
        }
        A.at(s.at(0) - '1').at(s.at(s.size() - 1) - '1')++;
    }
    for (int i = 0; i < 9; i++){
        for (int j = i; j < 9; j++){
            if (i == j){
                ans += A.at(i).at(j) * (A.at(i).at(j) - 1);
                ans += A.at(i).at(j);
            }
            else {
                ans += A.at(i).at(j) * A.at(j).at(i) * 2;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  string s,t;
  cin>>s>>t;
  string ans;
  int n=s.size(),m=t.size();
  for(int i=0;i<=n-m;i++){
    bool f=0;
    string a=s;
    for(int j=0;j<m;j++){
      if(a[i+j]=='?') continue;
      if(a[i+j]!=t[j]) f=1;
    }
    if(f) continue;
    for(int j=0;j<m;j++) a[i+j]=t[j];
    for(int j=0;j<n;j++) if(a[j]=='?') a[j]='a';
    if(ans.empty()) ans=a;
    else ans=min(ans,a);
  }
  
  if(ans.empty()) cout<<"UNRESTORABLE"<<endl;
  else cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
program main
  implicit none

  character(len=100) :: s
  character(len=7) :: c
  integer :: n, i

  read(*,*) s

  n = len_trim(s)
  c = 'keyence'

  if(index(s,c) /= 0) then
     if (index(s,c) == 1 .or. index(s,c, back=.true.) == n-6) then
        write(*,*) 'YES'
     else
        write(*,*) 'NO'
     end if
     stop
  else
     do i = 1, 7
        if(index(s,c(1:i)) == 1 .and. index(s,c(i+1:7), back=.true.) == n-(6-i)) then
           write(*,*) 'YES'
           stop
        end if
     end do
     
     write(*,*) 'NO'
  end if
end program main


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


int main() {
  int a, b;
  cin >> a >> b;
  cout << (a-1)*(b-1) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define mp make_pair
#define pb push_back
#define EB emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr double eps = 1e-14; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

class MaxFlow{
    public:
        struct edge{
            int to,cap,rev;
            edge(int t,int c,int r){to=t,cap=c,rev=r;}
        };

        int N;
        vector<vector<edge>> G;
        vector<bool> used;

        // n : ???????????°
        MaxFlow(int n){
            N = n;
            G.resize(n);
            used.resize(n);
        }

        // ???????????????????????¨????????????????????????
        void add_edge(int from,int to,int cap=1){
            G[from].push_back(edge(to,cap,G[to].size()));
            G[to].push_back(edge(from,0,G[from].size()-1));
        }

        // v??????t?????????f??\?????§??????????????§??????
        int dfs(int v, int t, int f){
            if (v == t) return f;
            used[v] = true;

            for (size_t i = 0; i < G[v].size(); i++){
                edge &e = G[v][i];
                if (!used[e.to] && e.cap>0){
                    int d = dfs(e.to, t, min(f, e.cap));
                    if (d > 0){
                        e.cap -= d;
                        G[e.to][e.rev].cap += d;        //???????????????
                        return d;
                    }
                }
            }
            return 0;
        }

        // s??????t???????????§???????±???????
        int max_flow(int s,int t){
            int flow = 0;
            while(true){
                used.assign(N,false);
                int f=dfs(s,t,INF);
                if(f==0) return flow;
                flow += f;
            }
        }
};

int VX,VY,E;

int main(){
    cin >> VX >> VY >> E;
    MaxFlow flow(VX+VY+2);
    rep(i,E){
        int x,y;
        cin >> x >> y;
        y += VX;
        flow.add_edge(x,y);
    }

    rep(i,VX){
        flow.add_edge(VX+VY,i);
    }
    rep(i,VY){
        flow.add_edge(i+VX,VX+VY+1);
    }

    int ans = flow.max_flow(VX+VY,VX+VY+1);
    cout << ans << endl;
}

Measured memory_bytes: 3176
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
 
using namespace std;
 
#define int long long
//typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int h,w,mi = INF;
	cin >> h >> w;
	for(int i = 1;i < h;i++){
		int a = i * w,b = (h - i) * (int)(w / 2),c = (h - i) * (int)((w + 1) / 2);
		mi = min(mi,max({abs(a - b),abs(b - c),abs(c - a)}));
		b = w * (int)((h - i) / 2);
		c = w * (int)((h - i + 1) / 2);
		mi = min(mi,max({abs(a - b),abs(b - c),abs(c - a)}));
	}
	for(int i = 1;i < w;i++){
		int a = i * h,b = (w - i) * (int)(h / 2),c = (w - i) * (int)((h + 1) / 2);
		mi = min(mi,max({abs(a - b),abs(b - c),abs(c - a)}));
		b = h * (int)((w - i) / 2);
		c = h * (int)((w - i + 1) / 2);
		mi = min(mi,max({abs(a - b),abs(b - c),abs(c - a)}));
	}
	cout << mi << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll n; cin >> n;
    ll k; cin >> k;
    vector <ll> as = {0};
    REP(i, n){
        ll a; cin >> a;
        as.push_back(a);
    }
    vector <ll> results = {1};
    map <ll, vector<ll>> cnt;
    cnt[1] = {0};
    ll cycle_start;
    ll cycle_len;
    for(int i=1; i<n*2+1; i++){
        ll cur = results[i-1];
        ll next = as[cur];
        results.push_back(next);
        cnt[next].push_back(i);
        if (cnt[next].size() == 2){
            cycle_start = cnt[next][0];
            cycle_len = cnt[next][1] - cycle_start;
            break;
        }
    }
    if (cycle_start > k){
        cout << results[k] << endl;
    } else {
        cout << results[cycle_start + (k-cycle_start)%cycle_len] << endl;
    }
    return 0;
}

Measured memory_bytes: 27936
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  if(n&1){cout<<"No";return 0;}
  int f=0;
  string s;
  cin>>s;
  int x=n/2;
  for(int i=0;i<n/2;i++)
  {
    if(s[i]!=s[x])
    {cout<<"No"<<endl;f=1;break;}
    
     x++;}
  if(f==0)
    cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(str(input()))
length = len(S)
cnt = 0
for a, b in zip(S, S[::-1]):
    if a!=b:
        cnt += 1
print(cnt//2)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
using namespace std;

map <int, int> divisor_counts;

int main(){
    int N;
    cin >> N;
    for(int i = 2; i <= N; i++){
        int cur_num = i;
        for(int j = 2; j <= i; j++){
            while(cur_num % j == 0){
                if(divisor_counts.find(j) == divisor_counts.end()){
                    divisor_counts[j] = 1;
                } else {
                    divisor_counts[j] ++;
                }
                cur_num /= j;
            }
            if(cur_num == 1){
                break;
            }
        }
    }

    int four_counts = 0;
    int two_counts = 0;
    int twenty_four_num = 0;
    int forteen_num = 0;
    int seventy_four_num = 0;
    for(auto it = divisor_counts.begin(); it != divisor_counts.end(); it++){
        //cout << it->first << " " << it->second << endl;
        if(it->second >= 4){
            four_counts ++;
        }
        if(it->second >= 2){
            two_counts ++;
        }
        if(it->second >= 14){
            forteen_num++;
        }
        if(it->second >= 24){
            twenty_four_num++;
        }
        if(it->second >= 74){
            seventy_four_num++;
        }
    }
    int ans = 0;
    ans += four_counts * (four_counts - 1) / 2 * (two_counts - 2);
    ans += forteen_num * (four_counts - 1);
    ans += twenty_four_num * (two_counts - 1);
    ans += seventy_four_num;    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;

int main(){
    int n, m;
    cin >> n;
    map<string,int> b, r;
    string s;
    while(n-- > 0){
        cin >> s;
        b[s]++;
    }
    cin >> m;
    while(m-- > 0){
        cin >> s;
        r[s]++;
    }
    int ans = 0;
    for(auto p : b) ans = max(ans, p.second-r[p.first]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (1E9+7)
#define PI 3.1415926535897932384626433832795

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	int n;
	vi fib(45,1);
	for (int i = 2; i < 45; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	cin >> n;
	cout << fib[n] << endl;
}


Measured memory_bytes: 3096
n = int(input())

A = [[] for i in range(n)]

for i in range(n):
  A[i] = list(map(int, input().split()))

B = [[0 for i in range(2)] for j in range(n)]
order = []

time = 0

def dfs(n, num):
  global time
  while time < 2*n:
    a = num
    time += 1
    if B[num-1][0] == 0: # まだ発見していないとき
      if A[num-1][1] != 0: # 次の頂点があるとき
        order.append(A[num-1][0]) # 発見したことを記録する
        B[num-1][0] = time # 発見時刻を記録する
        A[num-1][1] -= 1 # 次の頂点数を１減らす
        if B[A[num-1][2]-1][0] == 0: # 次の頂点がまだ発見されていないとき
          num = A[num-1].pop(2) # 次の頂点に移動
        else: # 次の頂点が発見済みのとき
          del A[num-1][2] # 次の頂点をルートから削除
      else: # 次の頂点がないとき
        l = len(order) # これまで経由した頂点数
        order.append(A[num-1][0]) # 発見したことを記録する
        order.append(A[num-1][0]) # 調べ終えたことを記録する
        B[num-1][0] = time # 発見時刻を記録する
        time += 1 # 時刻を１進める
        B[num-1][1] = time # 調査終了時刻を記録する
        num = order[l-1] # １つ前の頂点に戻る
    elif  B[num-1][1] == 0: # 発見しているが、調べ終えていないとき
      if A[num-1][1] == 0: # 次の頂点がないとき
        order.append(A[num-1][0]) # 調べ終えたことを記録する
        B[num-1][1] = time # 調査終了時刻を記録する
        m = order.index(num) # 発見した順番を調べる
        num = order[m-1] # 発見する前の頂点に移動
      else: # 次の頂点があるとき
        A[num-1][1] -= 1 # 次の頂点数を１減らす
        order.append(A[num-1][0]) # 経由したことを記録する
        if B[A[num-1][2]-1][0] == 0: # 次の頂点がまだ発見されていないとき
          num = A[num-1].pop(2) # 次の頂点に移動
        else: # 次の頂点が発見済みのとき
          del A[num-1][2] # つぎの頂点をルートから削除
        time -= 1 # 時刻を戻す
    else: # すでに調査終了した頂点に移動したとき
      l = len(order) # これまで経由した頂点数
      num = order[l-1] # １つ前の頂点に戻る
      time -= 1 # 時刻を戻す
      if num == a:
        break

for i in range(n):
  if B[i][0] == 0:
    dfs(n, A[i][0])

for i in range(n):
  print(str(i+1) + " ", end="")
  print(" ".join(map(str, B[i])))


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

int main() {
    int N;
    cin >> N;
    vector<string> v(N);
    rep(i,N) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    cout << v.size() << endl;
    return 0;
}


Measured memory_bytes: 9520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

bool is_prime[1000010];

int main() {
    int n;
    ll ans = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n-1; ++i) {
        if(a[i] > a[i+1]){
            ans += a[i]-a[i+1];
            a[i+1] += (a[i]-a[i+1]);
        }
    }
    cout << ans  << endl;
    return 0;
}

Measured memory_bytes: 4040
n,l=map(int,input().split())
a=list(map(int,input().split()))
lastmusubi=-1
tmp=0
for i in range(n-1):
  if a[i]+a[i+1]>tmp:
    lastmusubi=i
    tmp=a[i]+a[i+1]
if tmp>=l:
  print('Possible')
  if lastmusubi>0:
    for j in range(lastmusubi):
      print(j+1)
  if lastmusubi<n-1:
    for j in range(n-2,lastmusubi,-1):
      print(j+1)
  print(lastmusubi+1)
else:
  print('Impossible')
  

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


// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //

#define int               long long
#define endl              '\n'
#define ff                first
#define ss                second
#define mp                make_pair
#define pb                push_back
#define vii               vector<int> 
#define pii               pair<int,int>
#define vpii              vector< pii >
#define all(v)            v.begin(),v.end()
#define loop(i,s,e)       for(int i=s;i<e;i++)
#define rloop(i,e,s)      for(int i=e;i>=s;i--)
#define mset(a,f)              memset(a,f,sizeof(a))
#define M                 1000000007
#define fastio            ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define prvec(v)          loop(i_u_j,0,v.size())cout << v[i_u_j] <<" "; cout << endl;
#define prarr(arr,n)      loop(i_u_j,0,n)cout << arr[i_u_j] << " "; cout << endl;
#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)


template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //
const int N = 3e5 + 7;
int n;
int arr[N];
int dp[N];
int getans(int id)
{     
      if( dp[id] != -1 ) return dp[id];
      if( id  == n - 1  ) return 0;
      int a1,a2;
      a1 = a2 = 1e18;
      a1 = abs(arr[id] - arr[id + 1]) + getans(id+1);
      if( id + 2 < n ) a2 = abs(arr[id] - arr[id+2]) + getans(id+2);
      return dp[id] = min(a1,a2);
}
void solve()
{
      cin >> n;
      loop(i,0,n) cin >> arr[i];
      mset(dp,-1);
      cout << getans(0);
}

int32_t main() {
    fastio;

  
  int t = 1; 
  //cin>>t;
  
  while(t--) solve();
  
  


}


// M A F I A - M A F I A - M A F I A - M A F I A - M A F I A - M A F I A //















Measured memory_bytes: 7424
package main

import (
	"bufio"
	_ "container/heap"
	"fmt"
	"os"
	_ "sort"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const MOD = int(1e+9) + 7
const INF = 1 << 60

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	defer wtr.Flush()
	N := sc.nextInt()
	G := make([][]int, N)
	for i := 0; i < N-1; i++ {
		a, b := sc.nextInt()-1, sc.nextInt()-1
		G[a] = append(G[a], b)
		G[b] = append(G[b], a)
	}
	q := &Queue{}
	D1 := make([]int, N)
	D2 := make([]int, N)
	for i := 0; i < N; i++ {
		D1[i] = -1
		D2[i] = -1
	}
	bfs := func(cur int, D []int) {
		for i := 0; i < len(G[cur]); i++ {
			next := G[cur][i]
			if D[next] == -1 {
				D[next] = D[cur] + 1
				q.push(next)
			}
		}
	}
	D1[0] = 0
	q.push(0)
	for !q.isEmpty() {
		bfs(q.pop(), D1)
	}
	D2[N-1] = 0
	q.push(N - 1)
	for !q.isEmpty() {
		bfs(q.pop(), D2)
	}
	black, white := 0, 0
	for i := 0; i < N; i++ {
		if D1[i] <= D2[i] {
			black++
		} else {
			white++
		}
	}

	if black > white {
		fmt.Fprintln(wtr, "Fennec")
	} else {
		fmt.Fprintln(wtr, "Snuke")
	}
}

type Queue struct {
	arr []int
}

func (q *Queue) push(v int) {
	q.arr = append(q.arr, v)
}

func (q *Queue) pop() int {
	res := q.arr[0]
	q.arr = q.arr[1:]
	return res
}

func (q *Queue) isEmpty() bool {
	return len(q.arr) == 0
}


Measured memory_bytes: 12416
n, k = map(int, input().split())
check = [0 for i in range(n)]
for i in range(k):
    d = int(input())
    a = list(map(int, input().split()))
    for j in a:
        if check[j-1] == 0:
            check[j-1] = 1
ans = 0

for i in check:
    if i == 0:
        ans += 1
print(ans)

Measured memory_bytes: 9192
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
m=int(input())
def factorize(n):
    fct={}
    temp=n
    if temp<4:
        fct[temp]=1
    else:
        e=0
        while temp%2==0:
            temp=temp//2
            e+=1
        if e>0:
            fct[2]=e
    
    for b in range(3,int(n**0.5)+1,2):
        e=0
        while temp%b == 0:
            temp=temp//b
            e+=1
        if e>0:
            fct[b]=e
    if temp!=1:
        fct[temp]=1
    return fct
res={}
for i in range(2,m+1):
    f=factorize(i)
    for j in f:
        if j not in res:
            res[j]=f[j]
        else:
            res[j]+=f[j]
ans=1
for i in res.values():
   
    ans*=(i+1)
print(ans%(10**9+7))

Measured memory_bytes: 74364
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var total = Enumerable.Range(1, (int)N).Sum();
            return total;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 28128
N = int(input())
S = [int(i) for i in input().split(' ')]
Q = int(input())
T = [int(i) for i in input().split(' ')]

T.sort()
# print(T)
count = 0

S = set(S)
for s in S:
    # print(s)
    high = len(T) - 1
    low = 0
    while high >= low:
        mid = (high + low) //2
        # print(mid,high,low,s)
        if T[mid] ==  s:
            count += 1
            break
        elif T[mid] > s:
            high = mid -1
        else:
            low = mid +1

print(count)



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

/*
素因数分解をする(エラトステネスの篩)
return はvectorで素因数が入っている
*/
vector<int>eratosthenes(int n) {
	vector<int>res;
	vector<bool>prime(n + 1, 1);
	prime[0] = prime[1] = false;
	for (int i = 2;i*i <= n;++i) {
		if (prime[i] == true) {
			for (int j = 2 * i;j <= n;j += i) {
				prime[j] = false;
			}
		}
	}
	for (int i = 0;i <= n;++i) {
		if (prime[i] == true && i % 5 == 1)res.push_back(i);
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	vector<int>v = eratosthenes(55555);
	for (int i = 0;i < n;i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static bool f = false, t = true;
    static void Main(string[] args)
    {
        long sum = 0;
        long[] a = Read.longs();
        for(long i = a[0]; i <=a[1]; i+=i)
        {
            sum++;

        }
        Console.WriteLine(sum);
        Console.ReadLine();
    }
    public static long gcd(long a, long b)
    {
        while (true)
        {
            if (a == 0) { return b; }
            if (b == 0) { return a; }
            if (a > b) { a -= b; }
            else { b -= a; }
        }
    }
    public static long lcm(long a, long b) { return a / gcd(a, b) * b; }
    public static bool IsPrime(int num)
    {
        if (num < 2) return false;
        else if (num == 2) return true;
        else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

        double sqrtNum = Math.Sqrt(num);
        for (int i = 3; i <= sqrtNum; i += 2)
        {
            if (num % i == 0)
            {
                // 素数ではない
                return false;
            }
        }

        // 素数である
        return true;
    }
}
public static class Read
{
    public static void outl(string n = "") { Console.WriteLine(n); return; }
    public static long Long() { return long.Parse(Console.ReadLine()); }
    public static long[] longs() { return Console.ReadLine().Split().Select(long.Parse).ToArray(); }
    public static int Int() { return int.Parse(Console.ReadLine()); }
    public static int[] ints() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); }
    public static string Str() { return Console.ReadLine(); }
    public static string[] Strs() { return Console.ReadLine().Split(); }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define ALL(a) (a).begin(), (a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll, ll> pii;
const ll INF = 1LL << 58;
const ll MOD = 1000000007;
typedef vector<pii> vpii;
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;
}

signed main()
{
    //  以降 cin の入力元が 'input.txt' になる
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    int N, M;
    cin >> N >> M;
    if (N % 2 == 0)
    {
        bool bo = true;
        int a = 0;
        int b = 1;
        int c = N / 2;
        int d = N / 2 + 2;
        REP(i, M)
        {
            if (bo)
            {
                bo = false;
                cout << a + 1 << " " << b + 1 << endl;
                a = (a + N - 1) % (N);
                b = (b + 1) % (N);
            }
            else
            {
                bo = true;
                cout << c + 1 << " " << d + 1 << endl;
                c = (c + N - 1) % (N);
                d = (d + 1) % (N);
            }
        }
    }
    else
    {
        int a, b;
        a = 0;
        b = 1;
        REP(i, M)
        {
            cout << a + 1 << " " << b + 1 << endl;
            a = (a + N - 1) % (N);
            b = (b + 1) % (N);
        }
    }

    return 0;
}

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

int main(){
  int n,h;
  int m=0,ans=0;
  
  cin >> n;
  
  for(int i=0; i<n; i++){
    cin >> h;
    if( m <= h ) ans ++;
    m = max( m , h );
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
from bisect import bisect_left
N = int(input())
A = [int(input()) for i in range(N)]
X = [A[0]]

for i in range(1, N):
    if X[0] >= A[i]:
        X.insert(0, A[i])
    else:
        idx = bisect_left(X, A[i])
        X[idx-1] = A[i]

print(len(X))


Measured memory_bytes: 86020
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 10e15+9
#define EPS 1e-10
#define MAX_N 100100
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

double t, d, ta, tb, da, db;

int main(){
	cin >> t >> d >> ta >> tb >> da >> db;
	double ans = INF;
	for (int i = 0; i < d; i += da){
		for (int j = 0; j + i <= d; j += db){
			ans = min(ans, abs(t - (ta*(double)i + tb*(double)j) / ((double)(i + j))));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1280
"""
Writer: SPD_9X2

dpか?(なるほど)
左からi番目までの店でk個行くと決めた時の最小の時間？

at+b と xt+y があった時、at+bを先に取ったほうが最終的に小さくなる条件は
頑張って手計算すると
x/(1+y) < a/(1+b) なので、a/(1+b)が大きい方から貪欲していくのが正解っぽい？

→ただの貪欲は×
ただ、いくつか取るやつを選べば、その中では↑の式によって最適な取り方が決まる

→a/(1+b)の大きい方からしかとらないので、その順で使う、使わないでdpする
→O(N**2)

どうやってdpするか…

=========答えを見た========
a != 0なら指数関数的に増えるので、(最低で2倍)
回る店の数はせいぜい30にしかならない。
よって、a != 0に関して回る店の数とその最小値をdpした後、a == 0に関して調べればいい…
むずいけど分かるなぁ…(悔しい)

"""
N,T = map(int,input().split())

kab = []
azero = []

for i in range(N):

    a,b = map(int,input().split())

    if a == 0:
        azero.append(b)
    else:
        k = a/(1+b)
        kab.append([-1*k,a,b])


nt = 0
kab.sort()
dp = [float("inf")] * 29
dp[0] = 0

for k,a,b in kab:

    for i in range(27,-1,-1):

        dp[i+1] = min(dp[i+1] , 1 + dp[i] + a*(1+dp[i]) + b )

azero.sort()
dsum = [0]
for i in azero:
    dsum.append(dsum[-1] + 1 + i)

ans = 0
import bisect
for i in range(29):

    if dp[i] > T:
        break

    else:
        ans = max(i + bisect.bisect_right(dsum,T-dp[i]) - 1 , ans )
    
print (ans)

Measured memory_bytes: 89052
#include <stdio.h>
int main(){
  int A,B,C,ret;
  ret = scanf( "%d %d" , &A,&B );
  if( ret == EOF ) {
    return -1;
  }
  C= A+B;
  if(A-B>C){
    C=A-B;
  }
  if(A*B>C){
   C=A*B;
  }
  printf("%d",C);
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int ac1,wa1,tle1,re1;
string s;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		if(s=="AC"){
			ac1++;
		}
		else if(s=="WA"){
			wa1++;
		}
		else if(s=="RE"){
			re1++;
		}
		else{
		tle1++;
		}
	}
	cout<<"AC x "<<ac1<<endl<<"WA x "<<wa1<<endl<<"TLE x "<<tle1<<endl<<"RE x "<<re1; 
	return 0;
}

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

using namespace std;

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

class Cube {
public:
    int f[6];

    Cube() {}

    void roll_z() { roll(1, 2, 4, 3); }//
    void roll_y() { roll(0, 2, 5, 3); }//
    void roll_x() { roll(0, 1, 5, 4); }//
    void roll(int i, int j, int k, int l) {
        int t = f[i];
        f[i] = f[j];
        f[j] = f[k];
        f[k] = f[l];
        f[l] = t;
    };

    void move(char ch) {
        if (ch == 'E') REP(i, 3) roll_y();
        if (ch == 'W') roll_y();
        if (ch == 'N') roll_x();
        if (ch == 'S') REP(i, 3) roll_x();
    }
};

int getRight(Cube c1, int f1, int f2) {
    REP(i, 6) {
        REP(j, 4) {
            if (c1.f[0] == f1 && c1.f[1] == f2) return c1.f[2];
            c1.roll_z();
        }
        if (i % 2 == 0) c1.roll_y();
        else c1.roll_x();
    }
    return -1;
}

int main() {
    Cube c;
    int f1, f2;
    REP(i, 6) cin >> c.f[i];

    int q;
    cin >> q;

    REP(i, q) {
        cin >> f1 >> f2;
        cout << getRight(c, f1, f2) << endl;
    }
}

Measured memory_bytes: 3056
X = input()
a = ""
y = int(X)
while y > 0:
    i = int(y % 26)
    if i == 0:
        a = "z" + a
        y = y - 26
    else:
        a ='abcdefghijklmnopqrstuvwxy'[i-1] + a
        y = y - i
    y = y / 26
print (a)

Measured memory_bytes: 9176
#include<bits/stdc++.h>
#define F first
#define S second
#define LL long long
#define PB push_back
#define MP make_pair
#define I insert

const LL N = 2002, mod = 1000000007;

using namespace std;

LL n, m, i, j, k, l, r, t, ans;
LL a[N];
bitset < 4000001 > b;

int main(){
	cin >> n;
	for ( i = 0; i < n; ++i ){
		cin >> a[i];
		k += a[i];
	}
	b[0] = 1;
	for ( i = 0; i < n; ++i ){
		b = (b|(b<<a[i]));
	}
	for ( i = (k+1) / 2; ; ++i ){
		if ( b[i] ){
			cout << i << endl;
			break;
		}
	}
	return 0;
}
 
/**/
//      IIIIIIIII      OOOOO             A          NN        N    EEEEEEEEEE
//          I         O     O           A A         N N       N    E
//          I        O       O         A   A        N  N      N    E
//          I        O       O        A     A       N   N     N    E
//          I        O       O       AAAAAAAAA      N    N    N    EEEEEEEE
//          I        O       O      A         A     N     N   N    E
//          I        O       O     A           A    N      N  N    E
//          I         O     O     A             A   N       N N    E
//      IIIIIIIII      OOOOO     A               A  N        NN    EEEEEEEEEE ___ KAPANADZE

Measured memory_bytes: 2176