akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] a = new int[n+1];
        
        for(int i=1; i<=n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }
        
        List<Integer> list = new ArrayList<>();
        int[] in = new int[n+1];
        int count = 0;
        for(int i=n; i>0; i--) {
            count = 0;
            int j=1;
            while(i*j <= n) {
                count += in[i*j];
                j++;
            }
            if(count % 2 != a[i]) {
                in[i]++;
                list.add(i);
            }
        }
        
        System.out.println(list.size());
        for(int x : list) {
            System.out.println(x+" ");
        }
    }
}


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

int main() {
	int w, h;
	do {
		cin >> h >> w;
		if (h == 0 && w == 0)
			break;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if ((i % 2 == 1 && j % 2 == 1) || (i % 2 == 0 && j % 2 == 0))
					cout << "#";
				else
					cout << ".";
			}
			cout << endl;
		}
		cout << endl;
	} while (true);
	return 0;
}


Measured memory_bytes: 3104
#include <stdio.h>

int main(void){
    int NUM[10000];
    int n,i,j;
    int a = 0;


    scanf("%d",&n);

    for(i = 0; i<n; i=i+1){
        scanf("%d",&NUM[i]);
    }
    for (j = 0; j < n-1; j=j+1){
        if (NUM[j] == NUM[j+1]){
            NUM[j+1] = 0;
            a = a+1;
        }
    }

    printf("%d",a);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vi64 = vector<int64_t>;
using vvi64 = vector<vi64>;
#define rep(i, n) for (int64_t i = 0; i < (n); ++i)
#define repe(i, n) for (int64_t i = 0; i <= (n); ++i)
#define reps(i, s, n) for (int64_t i = (s); i < (n); ++i)
#define repse(i, s, n) for (int64_t i = (s); i <= (n); ++i)
#define repr(i, n) for (int64_t i = (n); i >= 0; --i)
#define all(xs) (xs).begin(), (xs).end()
#define pp_vec(xs) rep (i, (xs).size()) if { (i) cout << endl; cout << (xs)[i] << " "; };
const int64_t inf = (int64_t)1e18;
const int64_t mod = (int64_t)1e9 + 7;


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

  int N, M; cin >> N >> M;
  vi acc(N + 2, 0);
  rep (i, M) {
    int L, R; cin >> L >> R;
    acc[L]++; acc[R + 1]--;
  }
  int ans = 0;
  reps (i, 1, N + 2) {
    acc[i] += acc[i - 1];
    if (acc[i] == M) ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x7f7f7f7f;

int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int n1=(m+k)/2;
    int n2=(n+k)/2;
    int n3=(n+m)/2;
    int sum=0;
    int flag=0;
    while(!(n&1)&&!(m&1)&&!(k&1))
    {
        sum++;
        int n1=(m+k)/2;
        int n2=(n+k)/2;
        int n3=(n+m)/2;
        n=n1;
        m=n2;
        k=n3;
        if(sum>1000000)
        {
            flag=1;
            break;
        }
    }
    if(flag==1)
        printf("-1\n");
    else
        printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 256
N, M = map( int, input().split() )

H = list( map( int, input().split() ) )

L = [-1] * N
for i in range( M ):
  a, b = map( int, input().split() )
  if H[ a - 1 ] > H[ b - 1 ]:
    L[ b - 1 ] = a
  elif H[ a - 1 ] < H[ b - 1 ]:
    L[ a - 1 ] = b
  else:
    L[ b - 1 ] = a
    L[ a - 1 ] = b
    

cnt = 0
for i in L:
  if i < 0:
    cnt += 1
print( cnt )

Measured memory_bytes: 20140
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR1(i,n) for(int (i)=1;(i)<(n);(i)++)
#define eFOR(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define eFOR1(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i) sort((i).begin(),(i).end(), greater<int>());
#define F first
#define S second
constexpr auto INF = 1000000000;
constexpr auto LLINF = 9223372036854775807;
constexpr auto mod = 1000000007;
int main() {

	int n;
	cin >> n;
	VI  b(n), c(n, 0);
	int m = 0;
	FOR(i, n) {
		cin >> b[i];
		c[b[i] - 1]++;
		m = max(m, b[i]);
	}
	bool cant = 0;
	FOR(i, n)if (b[i] > i + 1)cant = 1;
	if (cant)cout << -1 << endl;
	else {
		stack<int> ans;
		FOR(i,n) {
			while (!c[m - 1])m--;
			for (int j = m - 1; j >= 0; j--) {
				if (b[j] == j + 1) {
					ans.push(j + 1);
					b.erase(b.begin() + j);
					c[j]--;
					break;
				}
			}
		}
		FOR(i, n) {
			cout << ans.top() << endl;
			ans.pop();
		}
	}

	return 0;
}


Measured memory_bytes: 256
n = int(input())
l = [input() for i in range(n)]
l.sort()
c = 1
ans = []
m = 0
for i in range(n-1):
    if l[i] == l[i+1]:
        c += 1
    else:
        if c > m:
            ans.clear()
            ans.append(l[i])
            m = c
        elif c == m:
            ans.append(l[i])
        c = 1
if m == 1:
    ans.append(l[-1])
elif c > m:
    ans.clear()
    ans.append(l[-1])
    m = c
elif c == m:
    ans.append(l[-1])
for i in ans:
    print(i)

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

int main()
{
    int n;cin>>n;
    string s;
    int a[5];
    memset(a,0,sizeof a);
    while(n--){
        cin>>s;
        if(s=="AC") a[1]++;
        else if(s=="WA") a[2]++;
        else if(s=="TLE") a[3]++;
        else if(s=="RE") a[4]++;
    }
    cout<<"AC x "<<a[1]<<endl;
    cout<<"WA x "<<a[2]<<endl;
    cout<<"TLE x "<<a[3]<<endl;
    cout<<"RE x "<<a[4]<<endl;
    return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
int main(void){
int n,i,ai,max,min;
double sum;
sum=0.0;
max=-1000000;
min=1000000;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&ai);
if(ai<min){
min=ai;
}
if(max<ai){
max=ai;
}
sum=sum+ai;
}
printf("%d %d %.0lf\n",min,max,sum);
return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define esort(s) sort((s).begin(),(s).end())

typedef long long ll;
typedef pair<int,int> ipair;
typedef vector<vector<int>> vvi;

const int INF = 1000000000;
const ll LINF = 1000000000000000000;
const double PI = acos(-1.0);
const double EPS = 1e-10;

// ZeroSumRange の考え
int main(){
    int N,K;
    cin >> N >> K;
    vector<int> A(N),S(N+1,0);
    rep(i,N){
        cin >> A[i];
        A[i]--;
        A[i] %= K;
        // cout << A[i] << " ";
    }
    S[0] = 0;
    rep(i,N){
        S[i+1]=(S[i]+A[i])%K; // 累積和を用いる
    }
    map<int,ll> M; // Sの同一値の個数をmap
    M[0]=1; // S[0]に0が入っている
    ll ans=0;
    rep(i,N){
        if(i+1-K>=0) M[S[i+1-K]]--; // K以上離れていれば同一値の個数から減らす
        ans += M[S[i+1]]++; // 個数xとして xC2 と同じ計算を行える
    }
    /* 距離K以下という条件を以下では組み込めない */
    // for(auto itr = M.begin(); itr != M.end(); ++itr) {
    //     cout << "key: " << itr->first << "  value: " << itr->second << "\n";
    //     ll tmp = itr->second;
    //     ans+=tmp*(tmp-1)/2;
    // }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 14336
def main():
    N, X, Y = map(int, input().split())
    count_list = [0] * N
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            distance = min(j-i, abs(j-Y) + abs(i-X) + 1)
            count_list[distance] += 1
    
    for i in range(1, N):
        print(count_list[i])

if __name__ == '__main__':
    main()

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

int n,m;

int main(){
  int i,j=0;
  cin >> n >> m;
  j=n+m;
  if(n-m>j)j=n-m;
  if(n*m>j)j=n*m;

  cout <<j<< endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); ++i)
#define pb push_back
#define all(v) v.begin(),v.end()
#define sort_1(v) sort(v.begin(),v.end())
#define sort_2(v) sort(v.begin(),v.end(),greater<ll>())
#define reverse(v) reverse(v.begin(),v.end())
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> s(n);
	vector<int> b;
	ll sum = 0;
	rep(i,n){
		cin >> s[i];
		sum += s[i];
		if(s[i]%10 != 0) b.pb(s[i]);
	}
	sort_1(b);
	if(sum%10 != 0){
		cout << sum << endl;
		return 0;
	}else{
		if(b.size() != 0){
			cout << sum - b[0] << endl;
			return 0;
		}else{
			cout << 0 << endl;
			return 0;
		} 
		return 0;
	}
}

Measured memory_bytes: 3644
#
# abc061 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 3
1 2
2 3
1 4"""
        output = """2
2
1
1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 5
1 2
2 1
1 2
2 1
1 2"""
        output = """5
5"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """8 8
1 2
3 4
1 5
2 8
3 7
5 2
4 1
6 8"""
        output = """3
3
2
2
2
1
1
2"""
        self.assertIO(input, output)


def resolve():
    N, M = map(int, input().split())
    ans = [0] * N
    for i in range(M):
        a, b = map(int, input().split())
        ans[a-1] += 1
        ans[b-1] += 1
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 16148
n = int(input())
h = list(map(int, input().split()))

max_res = 0
tmp_res = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        tmp_res += 1
    else:
        if tmp_res >= max_res:
            max_res = tmp_res
        tmp_res = 0

print(max(max_res, tmp_res))

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
string s;
int K; 
cin >> s >> K; 

string S[31415]; 
for(int i = 1; i <= 5; i++){
  for(int j = 1; j <= s.size() 
      && j+i <= s.size()+1; j++){
S[5000 * (i-1) + j] = s.substr(j-1, i); 
  }
}
sort(S, S+25000);
unique(S, S+25000);

cout << S[K] << endl; 
}

Measured memory_bytes: 1664
import Foundation

let input_line: String = readLine()!
let split: [String] = input_line.components(separatedBy: " ") //ブランクで区切られている場合

let x = split[0]
let length = x.count
var ans = ""
for i in 0..<length{
    ans += "x"
}
print(ans)


Measured memory_bytes: 13716
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second

#include<bits/stdc++.h>
using namespace std;

int n,t,i,mini,a,b;

int main(){
    ios_base::sync_with_stdio(false);

    cin>>n>>t; mini=999999999;
    for(i=0;i<n;i++){
        cin>>a>>b;
        if(t>=b){
            if(a<mini)mini=a;
        }
        //cout<<a<<" "<<mini<<endl;
    }

    if(mini==999999999)cout<<"TLE\n";
    else cout<<mini<<"\n";

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int l = 0, r, ans = 0;
string s;
bool flag = true;

int main()
{
    ios::sync_with_stdio(false);
    cin >> s;
	int len = s.length();
    r = len-1;
	while(l <= r)
	{
		while(s[l] == 'x') l++;
		while(s[r] == 'x') r--;
		if(l >= r) break;
		if(s[l] != s[r]) {flag = false; break;}
		while(s[l] == s[r]) l++, r--;
	}
	if(flag == false) { printf("-1\n"); return 0; }
	l = 0; r = len-1;
	int ll, rr;
	while(l <= r)
	{
		ll = 0;
		rr = 0;
		while(s[l] == 'x') l++, ll++;
		while(s[r] == 'x') r--, rr++;
		ans += abs(ll - rr);
		while(s[l] == s[r]) l++, r--;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int chk(int x, int d) {
	return x % (d+d) < d;
}

void solve(){
	int h, w, d; scanf("%d%d%d", &h, &w, &d);
	char S[5] = "RYGB";
	rep(i, h) {
		rep(j, w) {
			int c1 = (i + j + 10000);
			int c2 = (i - j + 10000);
			int x = chk(c1, d) << 1 | chk(c2, d);
			printf("%c", S[x]);
		}
		puts("");
	}
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		// printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

const long long INFLL = 1LL << 60;
const int INFI = 1000000000;


int main() {
    int N,K; cin >> N >> K;
    long long ans = K*pow(K-1,N-1);
    cout <<  ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <string.h>
#include <map>
#include <stack>
#include <iomanip>
#include <chrono>
#include <random>
#include <math.h>
#include <time.h>
#include <assert.h>
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) x.begin(),x.end() 
#define PII pair <int,int>
#define N 100005
#define MOD 1000000007
#define INF 1000000000000000000
using namespace std;

int main()
{
	int n, A[N];
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> A[i];
	}
	int ans = 1; 
	for (int i = 1; i < n; ++i)
	{
		bool ok = true;	
		for (int j = i - 1; j >= 0; --j)
		{
			if(A[j] > A[i])
			{
				ok = false;
				break;
			}
		}
		if(ok)
			ans++;
	}
	cout << ans;	
}



Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var x = int.Parse(line[1]);
        line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        Array.Sort(a);
        for (int i = 0; i < n; i++)
        {
            x -= a[i];
            if (x == 0) { Console.WriteLine(i + 1); goto end; }
            else if (x < 0) { Console.WriteLine(i); goto end; }
        }
        if (x == 0) Console.WriteLine(n);
        else Console.WriteLine(n - 1);
        end:;
    }
}


Measured memory_bytes: 11220
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll inf = 1e9+7;

ll N, A, B;
ll h[100010];
bool C(ll mid){//ここに条件を書く
    ll cnt = 0;
    REP(i,0,N){
        cnt += max<ll>((h[i] - mid * B + A - B - 1) / (A - B), 0);
        if(cnt>mid) break;
    }
    return cnt <= mid;
}


ll Nibutan(ll lb, ll ub){
    while(ub-lb>1){
        int mid=(lb+ub)/2;
        if(C(mid)) ub=mid;
        else lb=mid;
    }
    return ub;
}

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

    REP(i,0,N){
        cin>>h[i];
    }
    sort(h,h+N);
    reverse(h,h+N);
    ll ans = Nibutan(0, inf);//lb = 0 , ub = infなど
    p(ans);

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long n,m,sum=0,a=0;
  cin >> n;
  vector <long> A(n);
  for(long i=0;i<n-1;i++){
    cin >> a;
    A[a-1]++;
  }
  for (long i=0;i<n;i++){
    cout << A[i] << endl; 
  }
}

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

typedef long long ll;

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a;
    string b;
    cin >> a >> b;
    int ans = 1;
    for(int i = 0; i < a.size(); i++) {
        if(a[i] != b[i]) ans = 0;
    }

    if(ans) cout << "Yes\n";
    else cout << "No\n";
    

    return 0;
}

Measured memory_bytes: 3636
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    A, B = MAP()
    print("Yes" if A != 2 and B != 2 else "No")


if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#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>

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 1000000007
#define EPS 1e-10

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;

string s;

int main(){
	while (getline(cin, s)){
		if (s == ".")break;
		bool f = 1, g = 0;
		vector<char> vc;
		vc.clear();
		REP(i, s.size()){
			if (s[i] == '('){
				vc.push_back(s[i]);
			}
			if (s[i] == '['){
				vc.push_back(s[i]);
			}
			if (s[i] == ')'){
				if (!vc.empty()){
					if (vc[vc.size() - 1] == '[')f = 0;
					else vc.pop_back();
				}
				else f = 0;
			}
			if (s[i] == ']'){
				if (!vc.empty()){
					if (vc[vc.size() - 1] == '(')f = 0;
					else vc.pop_back();
				}
				else f = 0;
			}
		}
		if ((vc.empty()&&g)||(vc.empty() && f))cout << "yes" << endl; 
		else cout << "no" << endl;
	}
}

Measured memory_bytes: 1196
from collections import deque

S = list(input())
Q = int(input())

d = deque(S)

hd = []
bc = []
cnt = 0
mm = 0

for i in range(Q):
    q = list(input().split())

    if q[0]=="1":
        cnt += 1
    
# f:奇数 cnt:偶数 先頭    
# f:奇数 cnt:奇数 後方    
# f:偶数 cnt:偶数 後方
# f:奇数 cnt:偶数 先頭
#   
    elif q[0]=="2":
        f = int(q[1])
        c = q[2]
        mm += 1

        if (f+cnt)%2==0:
            d.append(c)
        else:
            d.appendleft(c)

if cnt%2==0:
    for i in range(len(S)+mm):
        # print(i,d)
        print(d.popleft(),end='')
else:
    for i in range(len(S)+mm):
        print(d.pop(),end='')
print()
















Measured memory_bytes: 8296
s = input()
q = int(input())
for i in range(q):
    o = list(map(str,input().split()))
    a,b = int(o[1]),int(o[2])
    if o[0] == "replace":
        s = s[:a] + o[3] +s[b+1:]
    elif o[0] == "reverse":
        c = s[a:b+1] 
        s = s[:a] + c[::-1] + s[b+1:]
    else:
        print(s[a:b+1])
    
        


Measured memory_bytes: 5612
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

import javax.swing.*;

import static java.util.Arrays.binarySearch;
import static java.util.Arrays.copyOfRange;
import static java.util.Arrays.sort;

public class Main {

    public static void main(String[] args) throws Exception {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;

        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }
}

class Task {

    private static int mod = (int)1e9 + 7;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        Map<String, Boolean> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = in.next();
            map.put(s, true);
        }
        out.println(map.keySet().size());
    }



}

class InputReader {

    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(nextLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

}

Measured memory_bytes: 67188
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 200200;
char s[N];
int n;
ll ans;

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%s", s);
	n = strlen(s);
	int cnt = 0;
	char lst = 'B';
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == 'A') {
			if (lst == 'B')
				ans += cnt;
			else {
				cnt = 0;
				lst = 'B';
			}
		} else if (s[i] == 'B') {
			if (lst == 'C') {
				lst = 'B';
				cnt++;
			} else {
				lst = 'B';
				cnt = 0;
			}
		} else {
			if (lst == 'B') {
				lst = 'C';
			} else {
				lst = 'C';
				cnt = 0;
			}
		}
	}
	printf("%lld\n", ans);

	return 0;
}


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

using namespace std;

template<typename T>
long long modpow(const T n,const T p,const T mod);
template<typename T>
long long modinv(const T n,const T mod);
template<typename T>
bool chmax(T &a,const T &b);
template<typename T>
bool chmin(T &a,const T &b);

long long inf=1000000007;

int main(){
	long long n;
	cin>>n;
	vector<vector<long long>> tyoten(n);
	vector<long long> hen(n-1,0);
	vector<pair<long long,long long>> connect(n-1);
	vector<set<long long>> tyotencol(n);

	for(long long i=0;i<n-1;i++){
		long long a,b;
		cin>>a>>b;
		a--;b--;
		tyoten.at(a).push_back(i);
		tyoten.at(b).push_back(i);

		connect.at(i).first=a;
		connect.at(i).second=b;
	}

	long long k=-1;

	for(auto a:tyoten){
		chmax(k,(long long)a.size());
	}

	cout<<k<<endl;

	for(long long i=0;i<n;i++){
		long long color=1;
		for(long long j=0;j<tyoten.at(i).size();j++){
			while(true){
				long long presize=tyotencol.at(i).size();
				tyotencol.at(i).insert(color);
				if(presize!=tyotencol.at(i).size()) break;
				color++;
			}

			if(hen.at(tyoten.at(i).at(j))==0){
				hen.at(tyoten.at(i).at(j))=color;
				tyotencol.at(connect.at(tyoten.at(i).at(j)).first).insert(color);
				tyotencol.at(connect.at(tyoten.at(i).at(j)).second).insert(color);
			}else{
				tyotencol.at(i).erase(color);
			}
		}
	}

	for(auto a:hen) cout<<a<<endl;

	return 0;
}

template<typename T>
long long modpow(const T n,const T p,const T mod){
	if(p==0) return 1;
	if(p%2==0){
		long long a=modpow(n,p/2,mod);
		return a*a%mod;
	}
	if(p%2==1) return (modpow(n,p-1,mod)*n)%mod;
	cerr<<"ERROR"<<endl;
	return 1;
}

template<typename T>
long long modinv(const T n,const T mod){
	return modpow(n,mod-2,mod);
}

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

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


Measured memory_bytes: 25512
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int x[N], y[N], d[N];

int main(){
	int h, w, D;
  cin >> h >> w >> D;
  for(int i=0;i<h;i++){
	for(int j=0;j<w;j++){
	  int t;
      cin >> t;
      x[t] = i;
      y[t] = j;
    }
  }
  for(int i = D+1; i<=h*w; i++){
    d[i] = d[i-D] + abs(x[i]-x[i-D]) + abs(y[i]-y[i-D]);
  }
  int q;
  cin >> q;
  while(q--){
    int l, r;
    cin >> l >> r;
    cout << d[r]-d[l] << '\n';
  }return 0;
}

Measured memory_bytes: 4612
#include<bits/stdc++.h>
using namespace std;
int n,ans,A[100005];
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)scanf("%d",&A[i]);
	sort(A+1,A+n+1);
	if(n&1)printf("0");
	else printf("%d",A[(n>>1)+1]-A[n>>1]);
	return 0;
}

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

int main()
{
ll a ;
double  b ;
cin >> a >> b ;
ans=a*(ll)(b*100+0.000001)/100LL;
cout << ans << endl;
return 0;
}

Measured memory_bytes: 3692
<?php
  $n = trim(fgets(STDIN)) ;
$b = explode(' ',trim(fgets(STDIN))) ;
$sum=$b[0]+$b[$n-2];
for($i=0;$i<$n-2;$i++){
  $sum += min($b[$i],$b[$i+1]) ;
}
echo $sum ;

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define ll int int
#define iton for(int i=0;i<n;i++)
#define itok for(int i=0;i<k;i++)
#define jton for(int j=0;j<n;j++)
int  main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s,t;
    cin>>s>>t;
    int m= t.length();
    int n= s.length();
    int dp[m+1][n+1];
    
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
        {   
            if (i == 0 || j == 0)
            dp[i][j] = 0;
            else if(s[j-1] == t[i-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
            }
        }
    }
    
    int index = dp[m][n]; 
  
   
   char lcs[index+1]; 
   lcs[index] = '\0'; 
  
   int i = m, j = n; 
   while (i > 0 && j > 0) 
   { 
      
      if (t[i-1] == s[j-1]) 
      { 
          lcs[index-1] = t[i-1];  
          i--; j--; index--;     
      }
      else if (dp[i-1][j] > dp[i][j-1]) 
         i--; 
      else
         j--; 
   } 
   cout<<lcs;
}


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

int main(){
  int n,m,ans =1;
  cin >> n >> m;
 
  for(int i=0;i<m;i++){
    ans *= 2;
  }
  
  cout << ans*(1900*m+100*(n-m)) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);};};
const ll MOD = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<62;


class UnionFind {
public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> Parent;
    //作るときはParentの値を全て-1にする
    //こうすると全てバラバラになる
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//親をとってきたい]
    }
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらひっくり返しちゃう。
        if (size(A) < size(B)) swap(A, B);
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        return true;
    }
};

int main(void){

    int n,m;
    cin>>n>>m;
    UnionFind uni(n);

    int x,y,z;
    rep(i,m){
        cin>>x>>y>>z;
        x--;y--;
        uni.connect(x,y);
    }
    int ans=0;
    rep(i,uni.Parent.size()){
        if(uni.Parent[i]<0)ans++;
    }

    cout<<ans<<endl;




}

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

int main(){
    int N,M,X;
    scanf("%d %d %d",&N,&M,&X);

    int* A = new int[N+1];
    for(int i=0;i<=N;i++){
        A[i]=0;
    }

    int cost;
    for(int i=0;i<M;i++){
        scanf("%d",&cost);
        for(int j=1;j<N;j++){
            if(cost==j){
                A[j]=1;
            }
        }
    }

    int cost_0=0;
    for(int i=X+1;i<=N;i++){
        cost_0+=A[i];
    }

    int cost_N=0;
    for(int i=0;i<=X-1;i++){
        cost_N+=A[i];
    }

    if(cost_0<cost_N){
        printf("%d\n",cost_0);
    }
    else{
        printf("%d\n",cost_N);
    }

    return 0;
}

Measured memory_bytes: 256
import sys
N = int(input())
T = [list(map(int, input().split())) for i in range(N)]

x, y = 0, 0
t = 0
for i in range(N):
    t1 = T[i][0] - t
    x1 = T[i][1]
    y1 = T[i][2]
    if t1 < abs(x1 - x) + abs(y1 - y):
        print('No')
        sys.exit()
    t1 -= abs(x1 - x) + abs(y1 - y)
    if t1 % 2 != 0:
        print('No')
        sys.exit()
    t = T[i][0]
    x = x1
    y = y1
print('Yes')

Measured memory_bytes: 27380
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define Rep(n) for (ll _ = 0; _ < (ll)(n); _++)
#define fs first
#define sc second

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}
template <class S> void print(vector<S> &v){for(ll i=0; i<(ll)v.size(); i++){cerr << v[i] << ' ';}cerr << endl;}
template <class S> void print(vector<vector<S>> &v) {for (ll i = 0; i < (ll)v.size(); i++) {for (ll j = 0; j < (ll)v[i].size(); j++) {cerr << v[i][j] << ' ';}cerr << endl;}}

int main(){
	int n; cin >> n;
	vector<int> a(n);
	int s=0;
	rep(i,n){
		cin >> a[i];
		s ^= a[i];
	}
	rep(i,n){
		cout << (s ^ a[i]) << ' ';
	}
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653

int main(){
	vector<vector<ll>> dp(2100,vector<ll>(2100));
	ll n; cin >> n;
	vector<vector<ll>> al(n,vector<ll>(2));
	REP(i,n){
		cin >> al.at(i).at(0);
		al.at(i).at(1) = i;
	}
	sort(al.begin(), al.end()); reverse(al.begin(), al.end());
	REP(i,2100) REP(j,2100){
		if (i==0 && j==0){
			continue;
		}
		else if (i+j>n){
			continue;
		}
		else if (i==0){
			dp[i][j] = dp[i][j-1]+al[i+j-1][0]*abs(n-j-al[i+j-1][1]);
		}
		else if (j==0){
			dp[i][j] = dp[i-1][j]+al[i+j-1][0]*abs(al[i+j-1][1]-i+1);
		}
		else {
			ll x = dp[i][j-1]+al[i+j-1][0]*abs(n-j-al[i+j-1][1]);
			ll y = dp[i-1][j]+al[i+j-1][0]*abs(al[i+j-1][1]-i+1);
			dp[i][j] = max(x,y);
		}
	}
	ll ans = 0;
	FOR(i,0,n){
		ans = max(ans,dp[i][n-i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 38260
<?php
  list($lifePoint, $attackPattern) = explode(' ', trim(fgets(STDIN)));
  $hitPoints = explode(' ', trim(fgets(STDIN)));
  $isWin = 'No';
  foreach ($hitPoints as $point) {
    $lifePoint -= $point;
    if ($lifePoint <= 0) {
      $isWin = 'Yes';
    }
  }
  echo $isWin;
?>

Measured memory_bytes: 12792
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
const int N=55;
using namespace std;
typedef long long ll;
int n,m,ans;
vector<int>sw[N];
int p[N],temp[N];
bool vis[N];
 
void dfs(int x)
{
    if(x==n+1)
    {
        memset(temp,0,sizeof(temp));
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]) continue;
            for(int j=0;j<sw[i].size();j++)
            {
                int b=sw[i][j];
                temp[b]++;
            }
        }
        for(int i=1;i<=m;i++) if(temp[i]%2!=p[i]) return ;
        ans++;
        return ;
    }
    dfs(x+1);
    vis[x]=true;
    dfs(x+1);
    vis[x]=false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int k;
        scanf("%d",&k);
        for(int j=0;j<k;j++)
        {
            int t;
            scanf("%d",&t);
            sw[t].push_back(i);
        }
    }
    for(int i=1;i<=m;i++) scanf("%d",&p[i]);
    dfs(1);
    printf("%d\n",ans);
    return 0;
}
 


Measured memory_bytes: 256
import itertools
import math
import statistics


def main():
    N = int(input())
    city_lst = [list(map(int, input().split())) for _ in range(N)]
    d_lst = [0] * math.factorial(N)

    for i, route in enumerate(itertools.permutations(range(N))):
        for j in range(len(route) - 1):
            d = math.sqrt((city_lst[route[j + 1]][0] - city_lst[route[j]][0])
                          ** 2 + (city_lst[route[j + 1]][1] - city_lst[route[j]][1]) ** 2)
            d_lst[i] += d

    print(f"{statistics.mean(d_lst):.10f}")


if __name__ == "__main__":
    main()


Measured memory_bytes: 11964
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#include <queue>

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

const float PI = 3.1415926;
static const int INFTY = (1<<30);

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
  REP(i,1,10)
    REP(j,1,10)
    cout << i<<'x'<<j<<'='<<i*j<<endl;
  return 0;
}

Measured memory_bytes: 1116
use proconio::input;

fn main() {
  input! {
      a: u64,
      b: String
  }
  
  let b:Vec<&str> = b.split(".").collect();
  let c = b[0].parse::<u64>().unwrap();
  let e = a * c;
  if b.len() == 1 {
  	println!("{}", e);
  } else {
    let d = b[1].parse::<u64>().unwrap();
    let f = a * d / 100;
 	println!("{}", e + f);   
  }
}

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

int main() {
  string N;
  
  cin >> N;
  
  if ( (N[0] == N[1] && N[1] == N[2]) || (N[1] == N[2] && N[2] == N[3] ))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3572
n = int(input())
a = list(map(float, input().split()))
ans = 0
if n == 1:
    ans = a[0]
else:
    dp = [[0]*(n//2+1) for _ in range(n)]
    dp[0][0] = a[0]
    dp[0][1] = 1-a[0]

    for i in range(1, n):
        dp[i][0] = dp[i-1][0]*a[i]
        for j in range(1, n//2+1):
            dp[i][j] = dp[i-1][j]*a[i] + dp[i-1][j-1]*(1-a[i])
    ans = sum(dp[-1])
print(ans)

Measured memory_bytes: 147720
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define _h cout<<"here"<<endl;
#define fill(a,v) memset(a,v,sizeof(a));
#define all(v) v.begin(),v.end()
#define rep(i,n) for(int i=0;i<n;i+=1)
#define prarr(a,n) rep(i,n) cout<<a[i]<<" \n"[i==n-1];// printf("%s\n"," " );
#define ff first
#define ss second
#define pu push_back
const int inf = 1e9+10;
const ll INF = 1e16+10;
const int MOD = 1e9+7;
const int MAXN = 2e5+10;

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> v;
    rep(i,n){
        int in;
        cin>>in;
        v.pu(in);
    }
    int count=0;
    rep(i,n){
        if(v[i]>=k){
            count++;
        }
    }
    cout<<count<<endl;
}


Measured memory_bytes: 1400
// #include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <string>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <ctime>
#include <cassert>
#include <fstream>
#include<unordered_map>
#include <stack>
#include <random>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

template<typename T>
void vdeb(std::vector<T> &da) {
    for (int i = 0;i < da.size();i++) {
        if (i == da.size() - 1) std::cout << da[i];
        else std::cout << da[i] << ' ';
    }
    std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
    for (int i = 0;i < da.size();i++) vdeb(da[i]);
    std::cout << std::endl;
}

using namespace std;

ll cal(ll r){
    return r*r*r*r*r;
}

int main(){
    ll x; cin >> x;
    vector<ll> da(1000);
    rip(i,1000,0) da[i] = cal(i);
    // vdeb(da);
    rip(i,1000,0){
        rip(j,1000,i){
            if(da[j]-da[i] == x){
                cout << j MM i << endl;
                return 0;
            }
            if(da[i]+da[j] == x){
                cout << i MM -j << endl;
                return 0;
            }
        }
    }
}

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

using namespace std;
#define N 100010
ll n,w,f[N];
int main(){
    cin>>n>>w;
    for(int i=0;i<N;i++)f[i]=1e17; f[0]=0;
    for(int u=0;u<n;u++){
     ll a,b;cin>>b>>a;
     for(int i=N-1;i-a>=0;i--){
      f[i]=min(f[i],f[i-a]+b);   
     }
    }
    ll ans=0;
    for(int i=0;i<N;i++)if(f[i]<=w)ans=i;
    cout<<ans<<endl;
 return 0;   
}

Measured memory_bytes: 1024
n = int(input())
s1 = input()
s2 = input()

mod = 10**9 + 7

# dp[i][j] : i番目まで見たときに、i番目の要素が j = 0 だと縦に、
# j = 1 だと横にブロックが並んでいた時の色の塗りかた (mod 10**9+7)
dp = [[0 for j in range(2)] for i in range(n+1)]

if s1[0] == s2[0]:
    dp[0][0] = 3
    i = 0
else:
    dp[1][1] = 3 * 2
    i = 1
while i < n - 1:
    if s1[i] == s2[i]:
        if s1[i+1] == s2[i+1]:
            dp[i+1][0] = dp[i][0] * 2 % mod
            i += 1
        else:
            dp[i+2][1] = dp[i][0] * 2 % mod
            i += 2
    else:
        if s1[i+1] == s2[i+1]:
            dp[i+1][0] = dp[i][1] % mod
            i += 1
        else:
            dp[i+2][1] = dp[i][1] * 3 % mod
            i += 2

print((dp[n-1][0] % mod + dp[n-1][1] % mod) % mod)

Measured memory_bytes: 3064
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(4);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
   ll w,h;
   cin>>w>>h;
   V<P> d;
   for(int i=0;i<h+w;i++){
       ll a;cin>>a;
       d.emplace_back(a,(w<=i));
   }
   sort(all(d));
   h++;w++;
   ll ans=0;
   for(int i=0;i<d.size();i++){
       if(d[i].se){
           ans+=w*d[i].fi;
           h--;
       }else{
           ans+=h*d[i].fi;
           w--;
       }
   }
   cout<<ans<<"\n";
}

Measured memory_bytes: 6512
/******************************************
*    AUTHOR:         CHIRAG AGARWAL       *
*    INSTITUITION:   BITS PILANI, PILANI  *
******************************************/
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL; 
typedef long double LD;
const int MAX=1e5+5;

map<pair<int,int>,int> mpbl; 
map<pair<int,int>,int> mprd;
set<int> degbl[MAX];
set<int> degrd[MAX];
set<pair<int,int> > dg;
vector<int> te;

void addbl(int a,int b)
{
	if(a>b)
	{
		swap(a,b);
	}
	degbl[a].insert(b);//added an edge between a,b in the blue graph
	degbl[b].insert(a);
	mpbl[make_pair(a,b)]++;

	if(mprd[make_pair(a,b)]>0)
	{
		dg.insert(make_pair(a,b));
	}
}


void addrd(int a,int b)
{
	if(a>b)
	{
		swap(a,b);
	}
	degrd[a].insert(b);
	degrd[b].insert(a);
	mprd[make_pair(a,b)]++;
	if(mpbl[make_pair(a,b)]>0)
	{
		dg.insert(make_pair(a,b));
	}
}

void erasebl(int a,int b)
{
	if(a>b)
	{
		swap(a,b);
	}
	degbl[a].erase(degbl[a].find(b));
	degbl[b].erase(degbl[b].find(a));
	mpbl[make_pair(a,b)]--;
}


void eraserd(int a,int b)
{
	if(a>b)
	{
		swap(a,b);
	}
	degrd[a].erase(degrd[a].find(b));
	degrd[b].erase(degrd[b].find(a));
	mprd[make_pair(a,b)]--;
}



int main() 
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		addbl(a,b);
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		addrd(a,b);
	}

	int cnt=0;
	
	while(dg.size())
	{
		pair<int,int> tmp=*(dg.begin());
		dg.erase(dg.begin());
		int a=tmp.first;
		int b=tmp.second;
		if(a>b)
		{
			swap(a,b);
		}
		if(!mprd[make_pair(a,b)]||!mpbl[make_pair(a,b)])
		{
			continue;
		}
		erasebl(a,b);
		eraserd(a,b);
		
		if(degrd[a].size()+degbl[a].size()>degbl[b].size()+degrd[b].size())
		{
			swap(a,b);
		}
		te.clear();

		for(set<int>::iterator it=degrd[a].begin();it!=degrd[a].end();it++)
		{
			te.push_back(*it);
			eraserd(*it,a);
		}

		for(int i=0;i<te.size();i++)
		{
			addrd(b,te[i]);
		}

		te.clear();

		for(set<int>::iterator it=degbl[a].begin();it!=degbl[a].end();it++)
		{
			te.push_back(*it);
			erasebl(*it,a);
		}
		for(int i=0;i<te.size();i++)
		{
			addbl(b,te[i]);
		}
		cnt++;
	}
	if(cnt==(n-1))
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 60288
n,w = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(n)]
#dp[i][j]はi番目まででj(j<=w)になるもの
dp = [[0]*(w+1) for i in range(n)]
for k in range(w+1):
  if k >= wv[0][0]:
    dp[0][k] = wv[0][1]
  else:
    continue
for i in range(n-1):
  for j in range(w+1):
    if j >= wv[i+1][0]:
      dp[i+1][j] = max(dp[i][j-wv[i+1][0]]+wv[i+1][1],dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]
print(dp[n-1][w])

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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef map<ll, ll> mii;
const int MOD = 1e9 + 7;

#define fastIO() \
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define mp make_pair 

int main() {
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<vi> dp(n, vi(n, 0));
    for (int i = 0; i < n; ++i) dp[i][i] = a[i];
    for (int l = 2; l <=n; ++l) {
        for (int i = 0; i + l - 1 < n; ++i) {
            int j = i + l - 1;
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]);
        }
    }
    cout << dp[0][n - 1] << endl;    
    return 0;
}


Measured memory_bytes: 70656
package main

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

var sc = bufio.NewScanner(os.Stdin)

func swap(a int64, b int64) (int64, int64) {
	return b, a
}

func GCD(a int64, b int64) int64 {
	if b > a {
		a, b = swap(a, b)
	}
	if b == 0 {
		return a
	} else {
		return GCD(a%b, b)
	}
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextLong() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(),10,64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


func main() {
	sc.Split(bufio.ScanWords)
	ans := 1
	N := nextLong()
	P := nextLong()
	var times int64
	times=1
	if N==1{
		fmt.Printf("%d\n", P)
		return
	}
	for i:=2; i<=int(math.Sqrt(float64(P)));i++{
		var tmp int64
		tmp=1
		times=0
		for{
			times++
			tmp*=int64(i)
			if tmp*int64(i)>=P || times==N-1{
				break
			}
		}
		if(times==N-1 && P%tmp==0){
		ans = int(math.Max(float64(ans),math.Min(float64(i), float64(GCD(P/tmp,int64(i))))))
		}
	}
	fmt.Printf("%d\n", ans)
}


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

int main() {
	int k;
	int a, b;
	int ret = 0;

	cin >> k >> a >> b;

	for (int i = a; i <= b; i++) {
		if ((i % k) == 0) {
			ret = 1;
			i = b;
		}
	}

	if (ret == 1) {
		cout << "OK" << endl;
	} else {
		cout << "NG" << endl;
	}

	return 0;
}


Measured memory_bytes: 3632
#include <iostream>

int main()
{
    int a, b;
    std::cin >> a >> b;
    if (a < b) {
        std::cout << "a < b\n";
    } else if (a > b) {
        std::cout << "a > b\n";
    } else {
        std::cout << "a == b\n";
    }

    return 0;
}


Measured memory_bytes: 3092
#include<iostream>
using namespace std;
int gcd(int a, int b){
	int t;
	if(a < b){t=a;a=b;b=t;}
	t = b;
	b = a % b;
	a = t;
	if(b == 0){
		return a;
	}else{
		gcd(a,b);
	}
}
int lcm(double a, double b){
	return (a * b) / (gcd(a,b));
}
int main(){
	int a,b;
	while(cin >> a >> b)
	cout << gcd(a,b) << ' ' << lcm(a,b) << '\n';
	return 0;
}

Measured memory_bytes: 1156
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.next().split("");
        int w = sc.nextInt();
        
        String result = "";
        for (int i = 0; i < s.length; i+=w) result += s[i];
        System.out.println(result);
    }
}


Measured memory_bytes: 39604
use proconio::input;

fn main() {
  input! {
    n: usize,
    a: [i64; n],
  }
  let mut b: Vec<(i64, usize)> = vec![(0, 0); n];
  for (i, &val) in a.iter().enumerate() {
    b[i] = (val, i);
  }
  b.sort(); b.reverse();
  let mut dp = vec![vec![0i64; n+1]; n+1];

  for i in 0..n {
    for j in 0..i+1 {
      dp[i+1][j] = std::cmp::max(dp[i+1][j], dp[i][j] + b[i].0 * ((b[i].1 as i64 - (n - (i-j) - 1) as i64) as i64).abs());
      dp[i+1][j+1] = std::cmp::max(dp[i+1][j+1], dp[i][j] + b[i].0 * ((b[i].1 as i64 - j as i64)).abs());
    }
  }
  println!("{}", dp[n].iter().fold(0i64, |x, &y| std::cmp::max(x, y)));
}

Measured memory_bytes: 33396