akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
const int inf=1000000007;
const int MOD=1000000007;
int dp[10][2][1000];
signed main(){
  string s;int k;cin>>s>>k;
  rep(i,10){
    rep(j,2){
      rep(kk,1000)dp[i][j][kk]=0;
    }
  }
  int n=(int)s.length();
  int res=0;int start=0;
  rep(i,n){
    if(i==0){
      dp[1][0][i]=s[i]-'1';
      dp[0][0][0]=1;
      dp[1][1][0]=1;
    }
    else{
      dp[0][0][i]=dp[0][0][i-1];
      dp[1][0][i]=dp[1][0][i-1];
      dp[2][0][i]=dp[2][0][i-1];
      dp[3][0][i]=dp[3][0][i-1];
      dp[1][0][i]+=dp[0][0][i-1]*9;
      dp[2][0][i]+=dp[1][0][i-1]*9;
      dp[3][0][i]+=dp[2][0][i-1]*9;
      if(s[i]!='0'){
      dp[0][0][i]+=dp[0][1][i-1];
      dp[1][0][i]+=dp[1][1][i-1];
      dp[2][0][i]+=dp[2][1][i-1];
      dp[3][0][i]+=dp[3][1][i-1];
      dp[1][0][i]+=dp[0][1][i-1]*(s[i]-'1');
      dp[2][0][i]+=dp[1][1][i-1]*(s[i]-'1');
      dp[3][0][i]+=dp[2][1][i-1]*(s[i]-'1');
      dp[1][1][i]+=dp[0][1][i-1];
      dp[2][1][i]+=dp[1][1][i-1];
      dp[3][1][i]+=dp[2][1][i-1];
      }
      else{
        dp[0][1][i]=dp[0][1][i-1];
        dp[1][1][i]=dp[1][1][i-1];
        dp[2][1][i]=dp[2][1][i-1];
        dp[3][1][i]=dp[3][1][i-1];
      }
    }
  }
  //cout<<"ok"<<endl;
  cout<<dp[k][0][n-1]+dp[k][1][n-1]<<endl;
  return 0;
}


Measured memory_bytes: 384
X = int(input())
p = 0
if X == 2 or X == 3:
  print(X)
else:
  while p == 0:
    q = 0
    for i in range(2, int(X**(1/2))+1):
      if X % i == 0:
        q += 1
        break
    if q == 0:
      p += 1
    else:
      X += 1
  print(X)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n, d, i, j, y;
  double dif,sum;
  int count=0, p, q;
  cin>>n>>d;
  int arr[n][d];
  
  for(i=0; i<n; i++)
    for(j=0; j<d; j++)
      cin>>arr[i][j];
      
  for(i=0; i<n-1; i++)
  {
      p = n-1-i;
      q = 1;
      while(p--)
      {
          sum = 0;
          for(j=0; j<d; j++)
          {
              dif = pow(abs(arr[i][j] - arr[i+q][j]),2);
              sum = sum + dif;
          }
          y = sqrt(sum);
          if(y*y == sum)
          count++;
          q++;
      }
  }
  cout<<count<<endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] sa = s.split("");
        int n = s.length();
        int sum=0;
        int max=0;
        for(int i=0;i<n;i++){
            if (sa[i].equals("A")|| sa[i].equals("C")||sa[i].equals("G")||sa[i].equals("T")) {
                sum++;
            }else{
                sum=0;
            }
            if (sum>=max){
                max=sum;
            }
        }
        System.out.println(max);
    }
}


Measured memory_bytes: 21972
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main(void)
{
	int a, b;
	cin >> a >> b;
	cout << (a + b) % 24 << endl;
	return 0;
}


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

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

    int first = (S[0] - '0') * 10 + (S[1] - '0');
    int second = (S[2] - '0') * 10 + (S[3] - '0');

    if(first > 0 && first < 13)
    {
        if(second > 0 && second < 13)
        {
            cout << "AMBIGUOUS" << endl;
        }
        else
        {
            cout << "MMYY" << endl;
        }
        
    }
    else
    {
        if(second > 0 && second < 13)
        {
            cout << "YYMM" << endl;
        }
        else
        {
            cout << "NA" << endl;
        }
        
    }
    
    return 0;
}

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

int n,k,i,a[500001],x,ans;

bool cmp(int a,int b){
	return a>b;
}

int main(){
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> x;
		a[x]++;
	}
	sort(a+1,a+n+1,cmp);
	for(i=k+1;a[i]>0;i++)
		ans+=a[i];
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    ll n,m;
    cin>>n>>m;
    vector<int> v(n);
    rep(i,n) cin>>v[i];
    ll sum = 0;
    rep(i,n) sum+=v[i];
    //cout<<sum<<endl;
    sort(v.begin(),v.end());
    vector<pair<int,int>> v2;
    rep(i,m){
        int c,b;
        cin>>c>>b;
        v2.push_back({b,c});
    }
    sort(v2.begin(),v2.end());
    reverse(v2.begin(),v2.end());
    //cout<<endl;
    /*for( auto u : v2 ){
        cout<<u.first<<" "<<u.second<<endl;
    }*/
    //cout<<endl;
    int now = 0;
    //rep(i,n) cout<<v[i]<<" ";
    //cout<<endl;
    rep(i,n){
        //cout<<v[i]<<" ";
        if(v2[now].first<v[i]) break;
        else{
            v2[now].second --;
            sum -= v[i];
            sum += v2[now].first;
            if(v2[now].second==0){
                now++;
                if(now>=v2.size()) break;
            }
            //if(now>=v2.size()) break;
        }
        //cout<<sum<<endl;
    }
    //cout<< sum << endl;
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 1784
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h=sc.nextInt(),r=sc.nextInt();
        int a=r-h;
        if(a==2*r) {
            System.out.println(0);
        }else if(a>2*r) {
            System.out.println(-1);
        }else {
            System.out.println(1);
        }
     
    }
}


Measured memory_bytes: 26220
#include<stdio.h>
#include<string.h>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
 
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main()
{
    int n;
    int a[105]={};
    scanf("%d\n",&n);
    REP(i,n)scanf("%d",&a[i]);
    REP(i,n)a[i]*=n;
    int sum=0;
    REP(i,n)sum+=a[i];
    sum/=n;
    int min=114514;
    int num=105;
    for(int i=n-1;i>=0;i--)
    {
        if((a[i]-sum)*((a[i]-sum>=0)*2-1)<=min)
        {
            num=i;
            min=(a[i]-sum)*((a[i]-sum>=0)*2-1);
        }
    }
    printf("%d\n",num);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200003],a1,ans,cn[800003];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=n;i>=1;i--)
		if(a[i]<=n)
		{
			a1=1-a[i],ans+=cn[i+a[i]+400000];
			cn[i-a[i]+400000]++;
		}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 8368
#include<stdio.h>

int main(){
	int n;
	scanf("%d", &n);
	char str[n+1];
	scanf("%s", str);
	int sum1=0, sum2=0;
	for(int i=0; i<n/2; i++){
		sum1+=str[i];
	}
	for(int i=n/2; i<n; i++){
		sum2+=str[i];
	}
	if(sum1==sum2){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	
	return 0;
}

Measured memory_bytes: 1604
#include<iostream>

using namespace std;

int main(){
  int W, H, N;
  cin >> W >> H >> N;
  int left = 0;
  int right = W;
  int bottom = 0;
  int top = H;
  for(int i=0; i<N; i++){
    int x, y, a;
    cin >> x >> y >> a;
    switch(a){
      case 1:
        left = max(left, x);
		break;
      case 2:
        right = min(right, x);
		break;
      case 3:
        bottom = max(bottom, y);
		break;
      case 4:
        top = min(top, y);
		break;
    }
  }
  if(right-left<0 || top-bottom<0){
    cout << 0 << endl;
  }else{
    cout << (right-left)*(top-bottom) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <queue>
#include <vector>

#define rep(i,min,max) for(int i=min;i<max;i++)
#define rrep(i,min,max) for(int i=max;i>=min;i--)

using namespace std;

int main(){
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  int l[Q], r[Q];
  rep(i,0,Q){
    cin >> l[i] >> r[i];
    l[i]--;r[i]--;
  }

  int tmp[N];
  tmp[0] = 0;
  rep(i,1,N){
    if(S[i-1] == 'A' && S[i] == 'C')
      tmp[i] = tmp[i-1] + 1;
    else
      tmp[i] = tmp[i-1];
  }

  rep(i,0,Q)
    cout << tmp[r[i]] - tmp[l[i]] << endl;
  
  return 0;
}



Measured memory_bytes: 2176
#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int MAX = 334;
constexpr int INF = (1 << 29);
 
int memo[MAX][MAX];
vector<int> w;
 
int rec(int L, int R)
{
    int &res = memo[L][R];
    if (res != -1) return res;
    if (L >= R) return (res = 0);
     
    res = -INF;
     
    if (abs(w[L] - w[R]) <= 1) {
        int r = rec(L + 1, R - 1);
        if (r == (R - 1) - (L + 1) + 1) {
            res = max(res, r + 2);
        }
    }
     
    for (int i = L; i <= R; i++) {
        res = max(res, rec(L, i) + rec(i+1, R));
    }   
    return res;
}
 
int main()
{
    int N;
    while (cin >> N, N) {
        w.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> w[i];
        }
         
        memset(memo, -1, sizeof(memo));
        cout << rec(0, N - 1) << endl;
    }
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  long long ans=0;
  for(int i=0;i<N-1;i++){
    if(A.at(i)>A.at(i+1)){
      ans+=A.at(i)-A.at(i+1);
      A.at(i+1)=A.at(i);
    }
  }
  cout << ans << endl;
}
    

Measured memory_bytes: 4052
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String w = sc.next();
		int count = 0;
		while(true){
			String s = sc.next();
			if(s.equals("END_OF_TEXT")){
				break;
			}
			if(w.toLowerCase().equals(s.toLowerCase())){
				count++;
			}
		}
		System.out.println(count);
	}
}



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

ll lcm(ll x,ll y)
{
    ll z=x;
    ll w=y;
    ll r=1;
    while(r!=0){
        r=x%y;
        x=y;
        y=r;
    }
    return z*w/x;
}
int main(){
   ll a,b,c,d,cd;
   cin >> a >> b >> c >> d;
   ll c_d,d_d,cd_d;
   c_d=b/c-(a-1)/c;
   d_d=b/d-(a-1)/d;
   cd=lcm(c,d);
   cd_d=b/cd-(a-1)/cd;
   cout << (b-a+1)-c_d-d_d+cd_d << endl;
   return 0;

}

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << end
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    int n,m; cin >> n >> m;
    ll res = (n-m)*(1<<m)*100;
    res += m*(1<<m)*1900;
    cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< ll, ll >   cp2;
typedef pair< ll, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789


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

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

int H, W;
int N;
int A[11234];

int out[112][112];
int cnt = 0;
int idx = 0;

int main(){
	
	cin>>H>>W;
	cin>>N;
	
	REP( i, N ){
		scanf("%d", A+i);
		if( i ) A[i] += A[i-1];
	}
	REP( i, H ){
		REP( j, W ){
			if( i % 2 ){
				out[i][W-j-1] = idx+1;
			}
			else{
				out[i][j] = idx+1;
			}
			cnt++;
			if( cnt == A[idx] ) idx++;
		}
	}
	
	REP( i, H ){
		REP( j, W ){
			if( j ) printf(" ");
			printf("%d", out[i][j]);
		}
		puts("");
	}
	
	return 0;

}

Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

const int INF = INT_MAX;

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

    vector<int> v(n, INF);
    deque<int> dq;
    v[1] = 1;
    dq.push_back(1);
    while(!dq.empty()){
        int a = dq.front();
        dq.pop_front();

        int b = (a + 1) % n;
        if(v[a] + 1 < v[b]){
            v[b] = v[a] + 1;
            dq.push_back(b);
        }
        int c = (a * 10) % n;
        if(v[a] < v[c]){
            v[c] = v[a];
            dq.push_front(c);
        }
    }
    cout << v[0] << endl;

    return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =5005;
ll n,ans=0,mod,c[maxn],dp[maxn][maxn];
int main(){
	cin>>n>>mod;
	for(int i=2;i<=n;i++)c[i]=(i<=(n>>1)+1?i-1:n-i+2);
	for(int i=0;i<=n;i++)dp[i][0]=1;
	for(int i=2;i<=n;i++)
		for(int j=0;j<=n;j++){
			if(j>=c[i])dp[i][j]=(dp[i][j-c[i]]+dp[i-1][j]+mod)%mod;
			else dp[i][j]=dp[i-1][j];
		}
	for(int i=0;i<n;i++)ans=(ans+(n-i)*dp[n][i]%mod)%mod;
	cout<<ans;
}

Measured memory_bytes: 195712
#include <stdio.h>

int main( void ) {
	double a, b, c, d, e, f;

	while ( scanf( "%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f ) == 6 )
		printf( "%.3f %.3f\n", ( c * e - b * f ) / ( a * e - b * d ) + 0.0000001, ( -c * d + a * f ) / ( a * e - b * d ) + 0.0000001 );

	return 0;
}

Measured memory_bytes: 656
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[3],i;
    for(i=0;i<3;i++)
        cin>>a[i];
    sort(a,a+3);
    reverse(a,a+3);
    int d=a[0]*10+a[1]+a[2];
    cout<<d<<endl;
    return 0;
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

readi b | Just (n, _) <- B.readInt b = n

solve :: Int -> [(Int, Int)] -> Int
solve n abs = go 0 abs
  where
    go !k []           = k
    go !k ((a, b):abs) = go (k + (an - a')) abs
      where
        a' = a + k
        an | a' `mod` b == 0 = a'
           | otherwise      = (a' `div` b + 1) * b

main :: IO ()
main = do
    n <- readLn :: IO Int
    abs <- replicateM n $ do
        [a, b] <- fmap readi . B.words <$> B.getLine
        return (a, b)
    print $ solve n (reverse abs)

Measured memory_bytes: 40828
#!/usr/bin/env python3
#ABC138 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
g = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    g[a-1].append(b-1)

ans = [0]*n
for _ in range(q):
    p,x = LI()
    ans[p-1] += x

que = deque()
que.append(0)
check = [True]*n
while que:
    v = que.popleft()
    for i in g[v]:
        if check[i]:
            check[i] = False
            que.append(i)
            ans[i] += ans[v]
print(*ans)


Measured memory_bytes: 62324
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import permutations

# 全探索をするのです
n,m = li()
edges = set()
for _ in range(m):
    a,b = li()
    edges.add((a,b))
    edges.add((b,a))
    
paths = permutations([str(i) for i in range(2,n+1)],n-1)
cnt = 0
for path in paths:
    path = [1] + [int(i) for i in path]
    
    exist = True
    for i in range(n-1):
        if not (path[i], path[i+1]) in edges:
            exist = False

    if exist:
        cnt += 1
        
print(cnt)

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

char ss[10];
char a[10]; bool ojbk=false;

void dfs(int k,int sum){
	if(ojbk) return;
	if(k==4&&sum==7){
		for(int i=0;i<3;i++)
			printf("%c%c",ss[i],a[i]);
		printf("%c=7\n",ss[3]);
		ojbk=true; return;
	}
	if(k==4) return; 
	a[k-1]='+'; dfs(k+1,sum+ss[k]-'0');
	a[k-1]='-'; dfs(k+1,sum-ss[k]+'0');
}

int main(){
	scanf("%s",ss);
	dfs(1,ss[0]-'0');
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int main() {
    long long N, P;
    cin >> N >> P;
    if(N==1) {
        cout << P << endl;
        return 0;
    }
    for(int i=1000000; i > 0; --i) {
        if(P % (long long)pow((double)i, (double)N) == 0) {
            cout << i << endl;
            return 0;
        }
    }
}

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

int main(){

string n;
cin>>n;

ll num=0;

for(ll i=0;i<n.size();i++)
num+=n[i]-'0';

if(num%9 == 0)
cout<<"Yes";
else cout<<"No";

return 0;

}

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

int N, M, Q;
int a[100], b[100], c[100], d[100];
int A[20];
int res = 0;

void debug() {
    for(int i=0; i<N; ++i) {
        cout << A[i] << ' ';  
    }
    cout << '\n';
}

void dfs(int depth, int prev) {
    if(depth < N) {
        for(int i=prev; i<=M; ++i) {
            A[depth] = i;
            dfs(depth + 1, i);
        }
    } else {
        //debug();
        int sum = 0;
        for(int i=0; i<Q; ++i) {
            if(A[b[i]] - A[a[i]] == c[i]) sum += d[i];
        }
        res = max(res, sum);
    }
} 

int main() {
    cin >> N >> M >> Q;
    for(int i=0; i<Q; ++i) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i]; --b[i];
    }
    dfs(0, 1);
    cout << res << '\n';
}

Measured memory_bytes: 3544
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <array>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>

using namespace std;
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

const long long maxa = 1e6 + 1;
vector<long long> spf(maxa + 1, 0);
vector<bool> can(maxa + 1, true);

int main() {

	iota(spf.begin(), spf.end(), 0);

	for (long long i = 2; i * i <= maxa; i++) {
		if (spf[i] == i) {
			for (long long j = i * i; j <= maxa; j += i) if (spf[j] == j) spf[j] = i;
		}
	}

	long long n; cin >> n;
	long long gd = 0;
	vector<long long> a(n); for (long long i = 0; i <= n - 1; i++) cin >> a[i], gd = gcd(gd, a[i]);

	bool is_setwise = (gd == 1);
	bool is_pairwise = true;


	for (long long i = 0; i <= n - 1; i++) {
		long long x = a[i];

		vector<int> s;
		while (x != 1) {
			s.push_back(spf[x]);
			x /= spf[x];
		}
		s.resize(distance(s.begin(), unique(s.begin(), s.end())));

		for (auto pfac : s) {
			if (can[pfac] == false) {
				is_pairwise = false;
				break;
			}
			can[pfac] = false;
		}


		if (!is_pairwise) break;
	}

	if (is_pairwise) cout << "pairwise coprime";
	else if (is_setwise) cout << "setwise coprime";
	else cout << "not coprime";


	return 0;
}

Measured memory_bytes: 19036
n,m=map(int,input().split())
a=[input() for _ in range(n)]
b=[input() for _ in range(m)]
ans="No"
for i in range(n-m+1):
    for k in range(n-m+1):
        if b[0]==a[i][k:k+m]:
            if sum([b[l]==a[i+l][k:k+m] for l in range(m)])==m:
                ans="Yes"
                break
print(ans) 

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define f1(n) for(int i=0;i<n;++i)
#define f2(n) for(int i=1;i<=n;++i)
#define lson(x) x<<1
#define rson(x) x<<1|1
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5;
const int mod = 0x3f3f3f3f;
const ll Mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll Inf = (ll)1e15;
ll a[maxn];
ll cnt[maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n;
	cin >> n;
	ll res = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	for (int i = 0; i <= n; ++i) {
		res += (cnt[i] - 1) * cnt[i] / 2;
	}
	//cout << "res = " << res << endl;

	for (int i = 0; i < n; ++i) {
		int k = cnt[a[i]];
		cout << res - k * (k - 1) / 2 + (k - 1) * (k - 2) / 2 << endl;
	}

	return 0;
}

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

int main(){
 long long int n;
  while(cin >> n){
    if(1<=n && n<=20){
      for(int i=n-1;0<i;i--)
	n *= (long long int)i;
      cout << n << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1156
n, m = map(int, input().split())
INF = 10 ** 6
match_dict = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5,
              6: 6, 7: 3, 8: 7, 9: 6}

a_list = list(map(int, input().split()))
a_sorted = sorted(a_list, reverse=True)

dp = [0, -INF]

for i in range(2, n + 1):
    tmp_dp = []
    for a in a_sorted:
        if i - match_dict[a] < 0:
            tmp_dp.append(-INF)
        else:
            tmp_dp.append(dp[i - match_dict[a]] + 1)
    dp.append(max(tmp_dp))

sum_str = ''
tmp_i = n
while tmp_i > 0:
    for a in a_sorted:
        if tmp_i >= match_dict[a] and dp[tmp_i - match_dict[a]] == dp[tmp_i] - 1:
            sum_str = sum_str + str(a)
            tmp_i = tmp_i - match_dict[a]
            break

print(int(sum_str))


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

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

    vector<ll> A(N);
    int minus = 0;
    for (int i = 0; i < N; i++) {
        ll tmp;
        cin >> tmp;
        if (tmp < 0) {
            minus++;
            A[i] = llabs(tmp);
        } else {
            A[i] = tmp;
        }
    }

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

    if (minus % 2 == 0) {
        cout << accumulate(A.begin(), A.end(), 0LL) << endl;
    } else {
        cout << accumulate(A.begin(), A.end(), 0LL) - A[0] * 2 << endl;
    }

    return 0;
}


Measured memory_bytes: 4024
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int num;
string s;

int main()
{
	cin>>s;
	rep(i,s.size()) if(s[i]=='x') num++;
	if(15-num>=8) puts("YES");
	else puts("NO");
	rt0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<map>

using namespace std;

long long X,D,N,Y,ans,i,j,k,R[200000]={0},W[200000]={0},temp,tW,tR;

char S[200000];

int main()
{
  cin>>N;
  cin>>S;
  
  j=0;
  k=0;
  for(i=0;i<N;i++)
  {
    if(S[i]=='W')
    {
      if(k==1) j++;
      
      W[j]++;
      k=0;
    }
    else
    {
      R[j]++;
      k=1;
    }
  }
  ans=N;
  
  if(j==0)
  {
    if(W[0]==0 || R[0]==0)
    {
      cout<<0;
      return 0;
    }
   
    cout<<min(W[0],R[0]);
    return 0;
      
  }
  
  if(j==1 && W[0]==0 && R[1]==0)
  {
    cout<<0;
    return 0;
  }
  
  for(i=0;i<=j;i++)
  {
    temp=0;
    tW=0;
    tR=0;
    for(k=0;k<=i;k++)
    {
      tW+=W[k];
    }
    for(k=i+1;k<=j;k++)
    {
      tR+=R[k];
    }
    temp=tR+tW-min(tW,tR);
    ans=min(ans,temp);
  }
  
  cout<<ans;
  
}



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

    #define ll long long
    #define ff first
    #define ss second
    #define pb push_back
    #define vll vector<ll>
    #define mll map<ll,ll>
    #define MOD 1000000007
    #define pll pair<ll,ll>
constexpr ll INF = 1999999999999999997; 
    #define fastio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
    int main() {
      fastio;

      string s;
      cin>>s;
      if((s[2]==s[3])&&(s[4]==s[5]))
        cout<<"Yes"<<endl;
      else
        cout<<"No"<<endl;
    }

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

using namespace std;

long long int h[100000+7];
vector<long long int> dp(100000+7);
int main()
{
    int N,K;
    scanf("%d %d\n",&N, &K);
    for(int i=1; i<=N; i++) scanf("%lld ",&h[i]);

    for(int i=2; i<=N; i++)
    {
        long long int res=LLONG_MAX;
        for(int k=i-1; k>=max(i-K,1); k--)
        {
            long long int temp = abs(h[i]-h[k]) + dp[k];
            if(temp<res){ res=temp; }
        }
        dp[i]=res;
    }

    printf("%lld\n",dp[N]);
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    vector<pair<int, int>> odd_count(1e5 + 1);
    vector<pair<int, int>> even_count(1e5 + 1);
    for(int i = 0; i < 1e5 + 1; i++)
    {
        odd_count[i] = {0, i};
        even_count[i] = {0, i};
    }
    for(int i = 0; i < n; i++)
    {
        if(i % 2 == 0)
        {
            even_count[v[i]].first++;
        }else{
            odd_count[v[i]].first++;
        }
    }
    sort(odd_count.begin(), odd_count.end());
    sort(even_count.begin(), even_count.end());
    reverse(odd_count.begin(), odd_count.end());
    reverse(even_count.begin(), even_count.end());
    int maxn = 0;
    for(int i = 0; i < odd_count.size(); i++)
    {
        for(int j = 0; j < even_count.size(); j++)
        {
            if(odd_count[i].second != even_count[j].second)
            {
                maxn = max(maxn, odd_count[i].first + even_count[j].first);
                break;
            }
        }
    }
    cout << n - maxn << endl;
    return 0;
}


Measured memory_bytes: 2304
#include "bits/stdc++.h"
using namespace std;
 
int n,t,a,h,ind;
double mn=1000001;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
 
	cin>>n>>t>>a;
	for(int i=0;i<n;i++){
		cin>>h;
		if(abs(a - double (t - h * 0.006)) < mn){
			mn = abs(a - double (t - h * 0.006));
			ind = i;
		}
	}
	cout<<ind+1;

	return 0;
}

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

using namespace std;

using int64 = long long;

int main(void) {
  int n, m;
  cin >> n >> m;
  vector <int64> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  map<int64, int> mp;
  int64 sum = 0;
  mp[sum] += 1;
  int64 ret = 0;
  for(int i = 0; i < n; i++) {
    sum += a[i];
    // mod は分配できる
    sum %= m;
    // 例: mp[sum]が4ならmod mがsumとなる要素のpairは4通り増える
    ret += mp[sum];
    mp[sum] += 1;
  }
  cout << ret << endl;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<S<<endl
using namespace std;


int main(){
	int a[21],L;
	int x[6]={1,10,100,1000,10000,100000};
	while(cin>>a[0]>>L&&(a[0]||L)){
		bool flag=false;
		int ansj,ansi;
		for(int i=1;!flag;i++){
			int rec[6]={0};
			int t=0,mx=0,mn=0;

			for(int j=a[i-1];j>0;j/=10){
				rec[t]=j%10;
				t++;
			}
			sort(rec,rec+L);
			REP(j,0,L){
				mx+=rec[j]*x[j];
				mn+=rec[L-1-j]*x[j];
			}
			a[i]=mx-mn;
			REP(j,0,i){
				if(a[j]==a[i]){
					ansj=j;
					ansi=i;
					flag=true;
				}
			}

		}
		cout<<ansj<<" "<<a[ansj]<<" "<<ansi-ansj<<endl;;
	}

	return 0;
}

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

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

  if (n < 2) return 0;

  int res = 0;
  int last = sqrt(n);

  for (int a = 1; a <= last; a++) {
    int maxb = (n - 1) / a;
    // printf("a: %d, maxb: %d\n", a, maxb);
    res += 2 * (maxb - a) + 1;
    if (a > maxb) res++;
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3676
#include<bits/stdc++.h>
using namespace std;
int main()
{
    unsigned int n,i,j;
    long long int lar=0,seclar=0;
    cin>>n;
    long long int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n,greater<long long int>());
    

    int count=0;
    for(i=0;i<n-1;i++)
    {
        
        if(a[i]==a[i+1])
        {
            lar=a[i];
            
            break;
        }
        
        
    }
    for(i=0;i<n;i++)
    {if(a[i]==lar)
    {
        count++;
    }}
    for(i=0;i<n-1;i++)
    {
        if(a[i]==a[i+1] && a[i]!=lar && a[i+1]!=lar)
        {
            seclar=a[i];
            break;
        }
        
    }
    if(count<4)
    cout<<lar*seclar;
    else
    cout<<lar*lar;
    return 0;
    
}


Measured memory_bytes: 1024
let solve s =
  let t = Array.make 26 false in
  String.iter (fun c -> t.(Char.code c - Char.code 'a') <- true) s;
  let rec doit i =
    if i = 26 then "None"
    else if not t.(i) then i + Char.code 'a' |> Char.chr |> String.make 1
    else doit (i + 1) in
  doit 0

let () = read_line () |> solve |> print_endline

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{
  	int n, d;
  	cin >> n >> d;
  	if (n % (2 * d + 1) == 0) cout << n / (2 * d + 1);
  	else cout << n / (2 * d + 1) + 1;
 	return 0; 
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <bitset>
#include<iomanip>//小数点以下を精度良く表示

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define INF 2000000000
#define INF2 1000000000000000000
#define PI 3.1415926535
#define rep(i,n) for(int i=0;i<(n);i++)
typedef pair<int, int> P;
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;


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;
}
int up(int a, int b) {
    return (a + a % b) / b;
}

void swap(string s) {
    int low = 0;
    int high = s.length() - 1;
    while (low < high) {
        char tmp = s[low];
        s[low] = s[high];
        s[high] = tmp;
        low++;
        high--;
    }
}

template<class T>  T gcd(T a, T b) {
    while (a % b != 0) {
        T tmp = b;
        b = a % b;
        a = tmp;
    }
    return b;
}

template<class T> T lcm(T a, T b) {
    if (a == b) return b;
    T g = gcd(a, b);
    return (a / g) * b;
}


int main() {
    int n;
    cin >> n;
    Graph G(n+1);
    for (int i = 2; i <= n; i++) {
        int a;
        cin >> a;
        G[a].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << G[i].size() << endl;
    }
    return 0;
}

Measured memory_bytes: 14016
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		int n = sc.nextInt();
		int m = sc.nextInt();
		sc.nextLine();
		int[] map = new int[128];
		for (int i = 0; i < n; i++) {
			String str = sc.nextLine();
			for (char c : str.toCharArray()) {
				map[c]++;
			}
		}


		int two = (n / 2) * (m % 2) + (n % 2) * (m / 2);
		int four = (n / 2) * (m / 2);

		for (int i = 'a'; i <= 'z'; i++) {
			four -= map[i] / 4;
			map[i] %= 4;
			two -= map[i] / 2;

		}
		String ans = "Yes";
		if (four > 0)
			ans = "No";
		two += 2 * four;
		if (two > 0)
			ans = "No";
		System.out.println(ans);

	}
}


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

double dist(int a, int b, vector<int> x, vector<int> y){
  double dx = x[a] - x[b];
  double dy = y[a] - y[b];
  return pow(dx*dx + dy*dy, 0.5);
}
int main(){
  int N;
  cin >> N;
  vector<int> x(N), y(N), v(N);
  for(int i=0; i<N; i++){
    cin >> x[i] >> y[i];
    v[i] = i;
  }
  double sum=0.0;
  do{ 
    for(int i=0; i<N-1; i++){
      sum += dist(v[i], v[i+1], x, y);
    }
  } while(next_permutation(v.begin(), v.end()));
  int Factorial = 1;
  for(int i=2; i<=N; i++){
    Factorial*=i;
  }
  cout << fixed << setprecision(10) << sum/Factorial << endl;

  return 0;
}

Measured memory_bytes: 256
n = gets.to_i
t, a = gets.split.map &:to_i
h = gets.split.map &:to_i
min = Float::INFINITY
mini = 0
for i in 0...n
  x = (a - t + h[i]*0.006).abs
  if x < min
    mini = i
    min = x
  end
end
p mini+1

Measured memory_bytes: 14396
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	int H, W;
	in >> H >> W;
	std::vector<std::vector<std::string>>S(H, std::vector<std::string>(W));
	rep(i, H) rep(j, W) in >> S[i][j];

	rep(i, H)
	{
		rep(j, W)
		{
			if (S[i][j] == "snuke")
			{
				char c = 'A' + j;
				out << c << i + 1 << std::endl;
				return 0;
			}
		}
	}
}


Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
ll lcm(ll a,ll b){
	return a*b/__gcd(a,b) ; 
}
int main(){
    fastio
    ll a , b , c , d ; 
    cin >> a >> b >> c >> d ; 
    ll LCM = lcm(c,d) ; 
    ll both = b/LCM - a/LCM ; 
    if ( a % LCM == 0 ) both++ ; 
    ll first = b/c - a/c ;
    if ( a % c == 0 ) first++ ; 
    ll second = b/d - a/d ; 
    if ( a % d == 0 ) second++ ; 
    debug() << imie(first) imie(second) imie(both) ;
    ll ans = (b-a+1) - (first + second - both) ; 
    cout << ans << endl;
    return 0 ;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define oo (long long)1e18
#define ll long long
#define setdp memset(dp,-1,sizeof(dp))
const ll mod = 1e9+7;
void _IOS(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);}
#define PI 3.14159265359
int sx,sy,tx,ty;
//8c:1a:bf:89:66:b6
struct threeElements{
int _1st,_2nd,_3rd;
};
vector<vector<int>>adj(10);
int sum,n,m,visited[11];
int main()
{
   // freopen ("jumping.in","r",stdin);
   _IOS();
   //18:52
   ll n,m;
   cin>>n>>m;
   vector<pair<ll,ll>>v,v1;
   for(int i=0;i<n;i++)
   {
       int a,b;
       cin>>a>>b;
       v.push_back({a,b});
   }
   for(int i=0;i<m;i++)
   {
       int a,b;
       cin>>a>>b;
       v1.push_back({a,b});
   }
   for(int i=0;i<n;i++)
   {
       ll ans=oo,idx;
       for(int j=0;j<m;j++)
        {
            ll q=abs(v[i].first-v1[j].first)+abs(v[i].second-v1[j].second);
            if(q<ans)
            {
                ans=q;
                idx=j+1;
            }
        }
        cout<<idx<<endl;
   }
}


Measured memory_bytes: 3628
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)
#define REPIT(i,x) for(auto i{(x).begin()}; i != (x).end(); i++) 

#define PB push_back
#define MP make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef double dbl;
typedef vector<bool> Vb;
typedef vector<char> Vc;
typedef vector<double> Vd;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<string> Vs;
typedef vector<vector<int>> VVi;
typedef vector<vector<ll>> VVl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }
inline void YES() { cout << "YES" << endl; } inline void Yes() { cout << "Yes" << endl; }
inline void NO() { cout << "NO" << endl; } inline void No() { cout << "No" << endl; }

const int MOD = 1000000007;

using G = vector<vector<int>>;

G g;
int n, k;
Vi vv, vcnt;

//// BODY ////

void init()
{
	cin >> n >> k;
	g.resize(n);

	REP(_i, n - 1)
	{
		int a, b; cin >> a >> b; --a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	vv.resize(n, -1);
	vcnt.resize(n, 0);
}

void treeDP(int v, int par)
{
	int c = k;
	int fixed = 0;
	for (int u : g[v])
		if (vv[u] != -1)
	{
		c -= vcnt[u];
		++fixed;
	}

	vv[v] = max(0, c);
	vcnt[v] = 1 + fixed;

	for (int u : g[v])
		if (vv[u] == -1)
		{
			treeDP(u, v);
			++vcnt[v];
		}
}

int main()
{
	init();

	treeDP(0, -1);

	ll ans = 1;
	REP(i, n)
		ans = ans * vv[i] % MOD;

	cout << ans << endl;
}

Measured memory_bytes: 9984
N,M = [int(i) for i in input().split()]
big = []
small = []
flag = 0

for i in range(N):
    a = input()
    big.append(a)
for i in range(M):
    a = input()
    small.append(a)

for i in range(0,N-M+1):
    for j in range(0,N-M+1):
        if big[i][j] == small[0][0]:
            count = 0
            for k in range(M):
                for l in range(M):
                    #なぜこれだとだめなのか？
                    # if big[i+k][j+l] != small[k][l]:
                    #     continue
                    # else:
                    #     if k == M-1 and l == M-1:
                    #         flag = 1
                    #         break
                    if big[i+k][j+l] == small[k][l]:
                        count += 1
                    if k == M-1 and l == M-1 and count == M * M:
                        flag = 1

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


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int X;
int main() {
    cin >> X;
    vector<bool> beki(X+1, false);
    beki.at(1) = true;

    for(int i = 2; i <= X; ++i) {
        int v = i * i;
        while(v <= X) {
            beki.at(v) = true;
            v *= i;
        }
    }

    for(int j = X; j >= 1; --j) {
        if(beki.at(j)) {
            cout << j << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            String lines[] = br.readLine().split(" ");
            if ("?".equals(lines[1]))
                break;
            int a = Integer.parseInt(lines[0]);
            int b = Integer.parseInt(lines[2]);
            if ("+".equals(lines[1])){
                System.out.println(a+b);
            }else if ("-".equals(lines[1])){    
                System.out.println(a-b);
            }else if ("*".equals(lines[1])){ 
                System.out.println(a*b);
            }else if ("/".equals(lines[1])){   
                System.out.println(a/b);
            }
        }
    }
}

Measured memory_bytes: 17012
#include <bits/stdc++.h>
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 MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

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

    vector<int> A(N);
    rep(i, N) cin >> A[i];

    map<int, int> mp;
    rep(i, N) mp[ A[i] ]++;

    bool ans = true;
    for (auto p : mp) {
        if (p.second > 1) ans = false;
    }

    if(ans) puts("YES");
    else puts("NO");
}

Measured memory_bytes: 10368
n = int(input())
A = list(map(int,input().split()))
counter = 0
breaker = 0
while True:
	for i in range(n):
		if A[i]%2 == 0:
			A[i] = A[i] // 2
		else:
			breaker = 1
	if breaker == 0:
		counter += 1
	else:
		break
print(counter)

Measured memory_bytes: 3060
A = int(input())
B = int(input())
C = int(input())
x = int(input())
ans = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            total = 500*a + 100*b + 50*c
            if total==x:
                ans+=1
print(ans)

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

int main() {
    int N; cin >> N;
    vector<int> C(N);
    vector<int> S(N);
    vector<int> F(N);

    rep(i, N-1){
        cin >> C[i+1] >> S[i+1] >> F[i+1];
    }

    for (int i = 1; i <= N; i++){
        int t = 0;
        for (int j = i; j < N; j++){
            if(t <= S[j]){
                t = S[j] + C[j];
            } else {
                int x = F[j] - (t % F[j]);
                t += x + C[j];
                if(x == F[j]){
                    t -= F[j];
                }
            }
        }
        cout << t << endl;
    }

    return 0;
}

Measured memory_bytes: 3604
//Name: Square Searching
//Level: 2
//Category: 動的計画法,DP,累積和
//Note:

/*
 * 座標(0,0)と(r,c)をそれぞれ左上，右下に持つ矩形を考えて，その中の*の数を記憶しておく．
 * これを使うと任意の矩形内の*の数がO(1)で求められる．
 * 正方形の左上は任意に決められるのでN^2通り存在し，それに対応する右下の決め方は高々N通りである．
 * (正方形であることに注意)．
 * したがって，ナイーブに探索するとO(N^3)個の正方形について内部の*の数を数え，0個のもののサイズを覚えればよい．
 */
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int dp[1000][1000];
int N;

inline int get(int r, int c) {
    if(r < 0 || r >= N || c < 0 || c >= N) return 0;
    return dp[r][c];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    while(cin >> N) {
        if(N == 0) break;
        for(int i = 0; i < N; ++i) {
            string line;
            cin >> line;
            for(int c = 0; c < N; ++c) {
                dp[i][c] = get(i-1, c) + get(i, c-1) - get(i-1, c-1);
                if(line[c] == '*') dp[i][c]++;
            }
        }
        int ans = 0;
        for(int r = 0; r < N; ++r) {
            for(int c = 0; c < N; ++c) {
                for(int size = ans+1; size <= N; ++size) {
                    const int er = r + size - 1;
                    const int ec = c + size - 1;
                    if(er >= N || ec >= N) break;
                    const int marks = get(er, ec) - get(er, c-1) - get(r-1, ec) + get(r-1, c-1);
                    if(marks == 0) {
                        ans = max(ans, size);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 5116
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef long long int ll;
#define mod 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define m0(x) memset(x,0,sizeof(x))

int main(void){

	int a,b,c=0;
	scanf("%d%d",&a,&b);
	rep(i,2){
		if(a>b) {
			c+=a;
			a--;
		}
		else {
			c+=b;
			b--;
		}
	}
	printf("%d\n",c );
	return 0;
}

Measured memory_bytes: 128
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0]*(n+1)
ans = 0
for i in range(n):
    if a[i] >= c[i]:
        ans += c[i]
        a[i] -= c[i]
    else:
        ans += a[i]
        a[i] = 0
        
    if a[i] >= b[i]:
        ans += b[i]
    else:
        ans += a[i]
        c[i+1] = b[i]-a[i]
if a[n] >= c[n]:
    ans += c[n]
else:
    ans += a[n]
print(ans)

Measured memory_bytes: 82020
#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a < b && b < c) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

#include <iostream>
#include <vector>

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define MAX(a, b) ((a) < (b) ? (b) : (a))

const long long INF = 1LL << 60;
typedef long long ll;
const long long MOD = 1000000000 + 7;

bool is_ok(int T, ll a, ll b, vector<ll> hp) {
  ll num = 0;
  ll tmp;
  rep(i, hp.size()) {
    tmp = hp[i] - b * T;
    if (tmp > 0) num += (tmp + (a - b) - 1) / (a - b);
  }
  return num <= T;
}

int main() {
  int n;
  ll b, a;
  cin >> n >> a >> b;
  vector<ll> hp;
  rep(i, n) {
    ll tmp;
    cin >> tmp;
    hp.push_back(tmp);
  }
  sort(hp.begin(), hp.end());
  ll ng = 1;
  ll ok = hp.back();
  while (ok > ng) {
    ll mid = (ng + ok) / 2;
    if (is_ok(mid, a, b, hp)) {
      ok = mid;
    } else {
      ng = mid;
    }
    if ((ok + ng) / 2 == mid) break;
  }
  cout << ok << endl;
  return 0;
}

Measured memory_bytes: 1908