akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<algorithm>
#include <stdio.h>
#include <string>
#include <map>
//#include <bits/stdc++.h>
using namespace std;
/*inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}*/
typedef long long ll;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int a[100004],b[100004],k[1000001];
int main() {
    int n,x;
    while (cin >> n) {
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int ans=0;
        for (int i = 1; i <= n; i++) {
            cin >> x, b[i] = a[i] - x;
            if(b[i]>=0)
                ans+=b[i];
        }
        cout<<ans<<endl;
}
    return 0;
}

Measured memory_bytes: 2304
#include<iostream>
#include <stdio.h>
using namespace std;
int main(){
	int sum = 0;
	char ch;
	while(true){
		while((ch = getchar()) != '\n') sum += ch - '0';
		if(sum == 0) break;
		else{
			printf("%d\n",sum);
			sum = 0;
		}
	}
	return 0;
}


Measured memory_bytes: 3212
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//Blue_card
		int how_b = sc.nextInt();
		String blue[] = new String[how_b];
		for(int i=0 ; i<blue.length ; i++) {
			blue[i] = sc.next();
		}
		//Red_card
		int how_r = sc.nextInt();
		String red[] = new String[how_r];
		for(int i=0 ; i<red.length ; i++) {
			red[i] = sc.next();
		}
		int ans=0;
		int get_money;
		
		for(int j=0 ; j<blue.length ; j++) {
			get_money=0;
			for(int i=0 ; i<blue.length ; i++) {
				if(blue[j].equals(blue[i])) {
					get_money++;
				}
			}
			for(int i=0 ; i<red.length ; i++) {
				if(blue[j].equals(red[i])) {
					get_money--;
				}
			}
			if(ans < get_money) {
				ans = get_money;
			}
		}
		System.out.print(ans);
	}

}


Measured memory_bytes: 21716
#include <iostream>
using namespace std;
int main() {
	int n, a[100],i,j,tmp,alice,bob;
	alice = 0;
	bob = 0;
	cin >> n;
	for (i = 0;i < n;i++) {
		cin >> a[i];
	}
	for (i = 0;i < n;i++) {
		for (j = i + 1;j < n;j++) {
			if (a[i] > a[j]) {
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}
	}
	if (n % 2 == 0) {
		for (i = 0;i < n;i++) {
			if ((i + 1) % 2 == 0) {
				alice += a[i];
			}
			else {
				bob += a[i];
			}
		}
		cout << alice - bob << endl;
	}
	else {
		for (i = 0;i < n;i++) {
			if ((i + 1) % 2 == 0) {
				bob += a[i];
			}
			else {
				alice += a[i];
			}
		}
		cout << alice - bob << endl;
	}
}


Measured memory_bytes: 256
#include<stdio.h>
int gcd(int x, int y);
int lcm(int x, int y, int g);
int main()
{
    int g,l,x,y;
    while (scanf("%d%d",&x,&y) != EOF){
    g=gcd(x,y);
    l=lcm(x,y,g);
    //printf("最大公約数は%dです\n最小公倍数は%dです\n",g,l);
    printf("%d %d\n",g,l);
    }
    return 0;
}
int gcd(int x, int y)
{
    int a,b,c,GCD;
    if(x > y){
            a=x;
            b=y;
            for(;;){
                c = a % b;
                if(a % b == 0){
                    GCD=b;
                    break;
                }
                a=b;
                b=c;
            }
        }
        else if(x < y){
            a=y;
            b=x;
            for(;;){
                c = a % b;
                if(a % b == 0){
                    GCD=b;
                    break;
                }
                a=b;
                b=c;
            }
        }
        else if(x == y){
            GCD=x;
        }
        return GCD;
}
int lcm(int x, int y, int g)
{
    int LCM;
    LCM=(x/g)*(y/g)*g;
    return LCM;
}

Measured memory_bytes: 0
import Foundation

struct Vec2 {
    var x:Double;
    var y:Double;
}

func Distance(a:Vec2, b:Vec2)->Double {
    let v = Vec2(x:a.x - b.x, y:a.y - b.y)
    return sqrt(v.x * v.x + v.y * v.y)
}

func CalcHVec(h:Double, m:Double, length:Double) -> Vec2 {
    let pi2 = Double.pi * 2.0
    let hrad = pi2 * h / 12.0
    let mrad = (pi2 / 12.0) * m / 60.0

    return Vec2(x:cos(hrad + mrad) * length, y:sin(hrad + mrad) * length)
}

func CalcMVec(m:Double, length:Double) -> Vec2 {
    let pi2 = Double.pi * 2.0
    let mrad = pi2 * m / 60.0

    return Vec2(x:cos(mrad) * length, y:sin(mrad) * length)
}

let args = readLine()?.split(separator: " ") ?? []

let a = Double(args[0]) ?? 0  // 時針長さ
let b = Double(args[1]) ?? 0  // 分針長さ
let h = Double(args[2]) ?? 0
let m = Double(args[3]) ?? 0

let hvec = CalcHVec(h: h, m: m, length: a)
let mvec = CalcMVec(m: m, length: b)
let result = Distance(a: hvec, b: mvec)

print(result)

Measured memory_bytes: 13916
// https://atcoder.jp/contests/abc151/tasks/abc151_d
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(size_t i = 0; i < (n); ++i)
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main()
{
    using grid = pair<int, int>;
    int H, W;
    cin >> H >> W;
    vector<vector<char>> S(H, vector<char>(W));
    REP(i, H) REP(j, W) cin >> S[i][j];
    
    int ans = -1;
    REP(sx, H) REP(sy, W)
    {
        if ('#' == S[sx][sy])
            continue;

        vector<vector<int>> cnts(H, vector<int>(W, -1));
        cnts[sx][sy] = 0;
        queue<grid> q;
        q.push(grid(sx, sy));
        int cntmax = -1;
        while (!q.empty())
        {
            grid cur = q.front();
            q.pop();

            for (int i = 0; i < 4; ++i)
            {
                int nx = cur.first + dx[i];
                int ny = cur.second + dy[i];

                if (nx >= 0 && nx < H && ny >= 0 && ny < W && S[nx][ny] == '.' && cnts[nx][ny] == -1)
                {
                    cnts[nx][ny] = cnts[cur.first][cur.second] + 1;
                    cntmax = max(cntmax, cnts[nx][ny]);
                    q.push(grid(nx, ny));
                }
            }
        }
        ans = max(ans, cntmax);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
int n,h,t;
struct Weapon{
	int a,b;
}w[100001];
bool Cmpare(Weapon a,Weapon b){
	return a.b<b.b;
}
int main() {
	scanf("%d%d",&n,&h);
	int am=0,bm=0;
	for (int i=1;i<=n;i++){
	scanf("%d%d",&w[i].a,&w[i].b);
	am=max(am,w[i].a);
	bm=max(bm,w[i].b);}
	sort(w+1,w+1+n,Cmpare);
	for (int i=n;i>=1;i--){
	if (h<=0) break;
	if (w[i].b>=am) h-=w[i].b,t++;}
	if (h>0) while (h>0) {h-=am;t++;}
	cout<<t;
	return 0;
}

Measured memory_bytes: 1024
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second
#define mp make_pair
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 60;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N;
string S;
int A[int(1e6 + 5)], B[int(1e6 + 5)];

int Prepare(int num){
	for (int i = 0; i < S.length(); i++){
		if (S[i] == '('){
			B[num]++;
		}else{
			if (B[num] == 0) A[num]++;
			else B[num]--;
		}
	}
	return 0;
}

int main(){
	cin >> N;
	for (int i = 0; i < N; i++){
		cin >> S; Prepare(i);
	}

	vector <Pii> P1, P2;
	for (int i = 0; i < N; i++){
		if (A[i] - B[i] <= 0){
			P1.push_back(mp(A[i], B[i]));
		}else{
			P2.push_back(mp(B[i], A[i]));
		}
	}

	if (P1.size() > 0) sort(P1.begin(), P1.end());
	if (P2.size() > 0) sort(P2.begin(), P2.end(), greater<Pii>());

	int Score = 0;
	for (int i = 0; i < P1.size(); i++){
		Score -= P1[i].fi;
		if (Score < 0){
			No(); return 0;
		}
		Score += P1[i].se;
	}
	for (int i = 0; i < P2.size(); i++){
		Score -= P2[i].se;
		if (Score < 0){
			No(); return 0;
		}
		Score += P2[i].fi;
	}

	if (Score == 0) Yes();
	else No();

  return 0;
}


Measured memory_bytes: 19016
<?php
//error_reporting(0);
//$N = trim(fgets(STDIN));
list($N,$X) = explode(" ",trim(fgets(STDIN)));
//$X  = explode(" ",trim(fgets(STDIN)));
$tot = 0;
for($i=0;$i<$N;$i++) {
  $m[] = trim(fgets(STDIN));
  $tot += $m[$i];
}
$md = min($m);
printf("%d\n",$N+($X - $tot)/$md);


Measured memory_bytes: 3956
#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank,size):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)

########################################
n = int(input())
a = list(map(int,input().split()))

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ

b = [0]*(n+1) #b[i]:iがaにおいて何番目か
for i in range(n):
    b[a[i]]=i

ans = 0
for i in range(n,0,-1):
    k = b[i]
    left = 0
    right = 0
    if k-1>=0 and a[k-1]>a[k]:
        left =  size[find(k-1,par)]
        unite(k-1,k,par,rank,size)
    if k+1<=n-1 and a[k+1]>a[k]:
        right = size[find(k+1,par)]
        unite(k+1,k,par,rank,size)
    ans += (left+1)*(right+1)*a[k]

print(ans)
    

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

using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<string> svec;

#define IN_LL(in) ll in; cin >> in
#define IN_STR(in) string in; cin >> in
#define IN_VEC(in, size) vec in; for(int i = 0; i < (size); ++i){int ____cur; cin >> ____cur; in.push_back(____cur); } 0
#define IN_SVEC(in, size) svec in; for(int i = 0; i < (size); ++i){int ____cur; cin >> ____cur; in.push_back(____cur); } 0

#define OUT(out) cout << (out)
#define OUT_VEC(out) for(ll i = 0; i < (out).size(); ++i) cout << (out)[i]

string func(ll t_hp, ll t_at, ll a_hp, ll a_at){
	bool turn = false;
	while(t_hp > 0 && a_hp > 0){
		turn = !turn;
		if(turn){
			a_hp -= t_at;
		}else{
			t_hp -= a_at;
		}
	}
	return turn ? "Yes" : "No";
}

int main(void){
	IN_LL(a);
	IN_LL(b);
	IN_LL(c);
	IN_LL(d);
	
	string res = func(a,b,c,d);
	
	OUT(res);
	return 0;
}


Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Collections;
//using System.Linq;
//using System.Text;
//using System.Threading.Tasks;

//namespace _1_A
//{
class Program
{
    static void Main(string[] args)
    {
        ArrayList harray = new ArrayList();
        ArrayList warray = new ArrayList();
        int dat = 0, hid = 0, mig = 0;
        int[] iarray = new int[2];
        string inp = Console.ReadLine();
        string[] oup = inp.Split(' ');
        iarray[0] = int.Parse(oup[0]);
        iarray[1] = int.Parse(oup[1]);

        while (dat < 300)
        {
            if (iarray[0] == 0 && iarray[1] == 0)
                break;
            harray.Add(iarray[0]);
            warray.Add(iarray[1]);
            dat++;
            inp = Console.ReadLine();
            oup = inp.Split(' ');
            iarray[0] = int.Parse(oup[0]);
            iarray[1] = int.Parse(oup[1]);
        }

        int cnt = 0;
        for (; cnt < dat; ++cnt)
        {
            hid = Convert.ToInt32(harray[cnt]);
            mig = Convert.ToInt32(warray[cnt]);
            for (int i = 0; i < hid; i++)
            {
                for (int j = 0; j < mig; j++)
                {
                    if (((i + 2) % 2) == 0 && ((j + 2) % 2) == 0)
                        Console.Write("#");
                    else if (((i + 2) % 2) == 0 && ((j + 2) % 2) == 1)
                        Console.Write(".");
                    else if (((i + 2) % 2) == 1 && ((j + 2) % 2) == 0)
                        Console.Write(".");
                    else if (((i + 2) % 2) == 1 && ((j + 2) % 2) == 1)
                        Console.Write("#");


                }
                Console.WriteLine();
            }
            Console.WriteLine();

        }

        //Console.Read();
    }
}
//}

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

int main() {
    int A, B, K; cin >> A >> B >> K;

    int cnt = 0, ans = 0;
    for (int i = 100; i > 0; i--) {
        if (A%i == 0 && B%i == 0) cnt++;
        if (cnt == K) {
            ans = i; break;
        }
    }

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

Measured memory_bytes: 256
A, B, C = map(int, input().split())

# 高橋くんは、お気に入りの自販機の音を、1回 A円 で聞くことができる。
# 高橋くんは、B円 持っている。
# C回 聞くと満足するので、B円 で 最大C回 まで聞けるだけ聞く。
# 高橋くんは、お気に入りの音を何回出来るか出力

i = B // A
if i > C:
    print(C)
else:
    print(i)

Measured memory_bytes: 9160
class Dice():
    def __init__(self, up, back, right, left, front, down):
        self.up = up
        self.down = down
        self.right = right
        self.left = left
        self.front = front
        self.back = back
    
    def north(self):
        temp = self.up
        self.up = self.back
        self.back = self.down
        self.down = self.front
        self.front = temp
    
    def south(self):
        temp = self.up
        self.up = self.front
        self.front = self.down
        self.down = self.back
        self.back = temp
        
    def east(self):
        temp = self.up
        self.up = self.left
        self.left = self.down
        self.down = self.right
        self.right = temp
    
    def west(self):
        temp = self.up
        self.up = self.right
        self.right = self.down
        self.down = self.left
        self.left = temp
        
    def operate(self, op):
        if op == "N":
            self.north()
        elif op == "S":
            self.south()
        elif op == "E":
            self.east()
        elif op == "W":
            self.west()
        
        
up, back, right, left, front, down = map(int, input().split())
dice = Dice(up, back, right, left, front, down)

op_str = input()

for op in op_str:
    dice.operate(op)

print(dice.up)


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
typedef int int__;
#define int long long
#define pb push_back
#define pi pair<int,int>
#define vpi vector<pi>
#define vi vector<int>
#define vvi vector<vi>
#define fi first
#define se second
#define forn(i, n)for(int i=0;i<int__(n);i++) 
#define sz(a)int__(a.size())
template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a){return out << "(" << a.first << ", " << a.second << ")";}
template<class A>ostream& operator<<(ostream& out,const vector<A>&v){out<<"[";forn(i,sz(v)){if(i)out<<", ";out<<v[i];}return out<<"]";}
const int MAX = 1e9 + 100;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int Mod(int x){const int mm=1e9 + 7;x%=mm;if(x<0)x+=mm;return x;}
int Pow(int x,int n){if(n==0)return 1;int t=Pow(x,n/2);t=Mod(t*t);if(n&1)t=Mod(t*x);return t;}
#define watch(x) cout << #x << " : " << x << endl;
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

int dp[3005][3005][2] = {0};

int__ main() {
	fast;
	int n,k; cin >> n >> k;

	vvi dp(n+1, vi (k+1,0));
	vi a(n+1);

	for(int i=1;i<=n;i++) cin >> a[i];

	dp[0][0] = 1;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=k;j++) dp[i-1][j] = Mod(dp[i-1][j-1] + dp[i-1][j]);

		for(int j=0;j<=k;j++) {
			int l = max(0LL,j-a[i]);
			dp[i][j] = Mod(dp[i][j] + dp[i-1][j]);
			if(l > 0) dp[i][j] = Mod(dp[i][j] - dp[i-1][l-1]);
		}
	} 

	cout << dp[n][k] << endl;
}

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

using namespace std;

#define fore(i, s, e) for(int i = s; i < e; i++)

typedef long long ll;

int main() {
    string s; cin >> s;
    ll r = 0;
    int a = 0;
    fore(i, 0, s.size()) {
        if(s[i] == 'W') r += i - a++;
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
 
using namespace std;
 
 
int main(){
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  int ten = 1, sum = 0, cnt[2019] = {};
  long long ans = 0;
  for(int i = 0; i < s.size(); i++){
    cnt[sum]++;
    sum += (s[i] - '0') * ten;
    sum %= 2019;
    ans += cnt[sum];
    ten = (ten * 10) % 2019; 
  }
  cout << ans << endl;
}

Measured memory_bytes: 3732
// In The Name OF Allah
// Mehrkish Makuei
// Islamic Republic Of Iran

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

typedef long long ll;
#define Mehrkish ios::sync_with_stdio(false),		cin.tie(0),		cout.tie(0)
#define pb push_back

const int maxx = 2e5 + 19;
int n, m, a[maxx], c[maxx], b[maxx], ans, jvb, sum, z, l, x, y, k, minn = 99999999;
string s[10], t, w;
bool flag = true;
vector <ll> v;

void Input(){
	cin >> n >> m;
}

void Solve(){
	ans = ( n * 3 ) + m;
	ans /= 2;
	cout << ans << endl;
}


int main(){
	Mehrkish;
	Input(),	Solve();
	return 0;
}


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

using namespace std;

int main() {
    int K, A, B;
    cin >> K >> A >> B;

    for (int i = A; i <= B; ++i) {
        if (i % K == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}


Measured memory_bytes: 3584
#include<iostream>

using namespace std;

int N;
int A[210];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)cin >> A[i];

	int res = 0;

	while (true) {
		bool exist_odd = false;
		for (int i = 0; i < N; ++i) {
			if (A[i] % 2 != 0)exist_odd = true;
		}

		if (exist_odd) break;

		for (int i = 0; i < N; ++i) {
			A[i] /= 2;
		}
		++res;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};

int h,w;
bool isrange(int x,int y){
    return 0<=x and x < h and 0<=y and y < w;
}
int main(){
    cin >> h >> w;
    vector<string>s(h);
    rep(i,h){
        cin >> s[i];
    }
    rep(i,h){
        rep(j,w){
            if(s[i][j] == '#'){
                bool flag = false;
                rep(k,4){
                    int x = i+dx[k];
                    int y = j+dy[k];
                    if(isrange(x,y) and s[x][y] =='#'){
                        flag = true;
                    }
                }
                if(!flag){
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout <<"Yes" << endl;
    return 0;
}

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

int main(){
    int h, n, a;
    int ans = 0;
    cin >> h >> n;
    for(int i = 0; i < n; i++){
        cin >> a;
        ans += a;
    }

    cout << (ans >= h ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007
#define endl "\n"
#define pb push_back
#define f() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int main() {
  f();
  int n,d;
  cin>>n>>d;

  cout<<(ceil(n/float(2*d+1)))<<endl;
  return 0;
}

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

signed main() {
  double N;
  cin >> N;
  
  double A = N / 1.08;
  int B = ceil(A);
  int C = floor(A);
  
  if( (int)(B * 1.08) == N ){
    cout << (int)B << endl;
  }else if( (int)(C * 1.08) == N ){
    cout << (int)C << endl;
  }else{
    cout << ":(" << endl;
  }

  
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int[][] bingo = new int[3][3];
            bingo[0] = CPUtils.readIntArray(3, in);
            bingo[1] = CPUtils.readIntArray(3, in);
            bingo[2] = CPUtils.readIntArray(3, in);
            int N = in.nextInt();
            int nums[] = CPUtils.readIntArray(N, in);
            Arrays.sort(nums);
            boolean answer = false;

            for (int row = 0; row < 3; row++)
            {
                int cnt = 0;
                for (int col = 0; col < 3; col++)
                {
                    int found = Arrays.binarySearch(nums, bingo[row][col]);
                    if (found >= 0) cnt++;
                }
                if (cnt == 3) answer = true;
            }
            for (int row = 0; row < 3; row++)
            {
                int cnt = 0;
                for (int col = 0; col < 3; col++)
                {
                    int found = Arrays.binarySearch(nums, bingo[col][row]);
                    if (found >= 0) cnt++;
                }
                if (cnt == 3) answer = true;
            }

            int el0_0 = bingo[0][0];
            int el1_1 = bingo[1][1];
            int el2_2 = bingo[2][2];
            if (Arrays.binarySearch(nums, el0_0) >= 0 && Arrays.binarySearch(nums, el1_1) >= 0 && Arrays.binarySearch(nums, el2_2) >= 0)
                answer = true;

            el0_0 = bingo[0][2];
            el1_1 = bingo[1][1];
            el2_2 = bingo[2][0];

            if (Arrays.binarySearch(nums, el0_0) >= 0 && Arrays.binarySearch(nums, el1_1) >= 0 && Arrays.binarySearch(nums, el2_2) >= 0)
                answer = true;

            if (answer)
                out.print("Yes");
            else
                out.print("No");
        }

    }

    static class CPUtils
    {
        public static int[] readIntArray(int size, Scanner in)
        {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
            {
                array[i] = in.nextInt();
            }
            return array;
        }

    }
}



Measured memory_bytes: 21844
#include <iostream>

int main() {
    int n, x;

    while (true) {
        std::cin >> n >> x;
        if (n == 0 && x == 0) break;

        int count = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int k = x - i - j;
                if (j < k && k <= n) {
                    count += 1;
                }
            }
        }
        std::cout << count << std::endl;
    }
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int H, A; cin >> H >> A;

    int ans = 0;
    while (true) {
        if (0 >= H) {
            cout << ans << endl;
            return 0;
        }
        ++ans;
        H -= A;
    }
}

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

int main()
{
    string S; cin >> S;
    int len = S.length();
    ll bitnum = len - 1;
    ll ans = 0;
    for (int i = 0; i < (1 << bitnum); ++i) {
        ll index = 0;
        ll ti = 0;
        string tmps; tmps.push_back(S[index]);
        index++;
  
        for (int j = 0; j < bitnum; ++j) {
            if ((i>>j) & 0x01) {
                ans += stol(tmps);
                tmps.clear();
                tmps.push_back(S[index]);
                index++;
            }
            else {
                tmps.push_back(S[index]);
                index++;
             }
        }
        tmps.push_back(S[index]);
        ans += stol(tmps);
    }    
    cout << ans << endl;
    
}


Measured memory_bytes: 3640
s=input()
size=len(s)
even=s[0::2]
odd=s[1::2]
e_0=even.count("0")
e_1=even.count("1")
o_0=odd.count("0")
o_1=odd.count("1")
print(min(size-e_0-o_1,size-e_1-o_0))

Measured memory_bytes: 3188
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])

    return res


def resolve():
    n = int(input())
    L = prime_factorization(n)
    res = 0
    for v, ex in L:
        i = 1
        while ex >= 0:
            if ex - i < 0:
                break
            ex -= i
            res += 1
            i += 1

    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9480
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int n;
unordered_set<int>s;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n;
	int f=0;
	for(int i=0;i<n;i++){
		int k;
		cin>>k;
		if(s.find(k)==s.end()){
			s.insert(k);
		}
		else f=1;
	}
	if(f==1)puts("NO");
	else puts("YES");
	return 0;
}

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

#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define NP next_permutation
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;

const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;

template<class T> bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T> void decimal(T a){cout<<fixed<<setprecision(a);}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}

void YesNo(bool a){if(a) out("Yes"); else out("No");}
void yesno(bool a){if(a) out("yes"); else out("no");}
void YESNO(bool a){if(a) out("YES"); else out("NO");}
ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){ll c=1; while(b>0){if(b&1){c=a*c %mod;}a=a*a %mod;b>>=1;}return c;}
vi calc(ll x){vi res; while(x>0){res.eb(x%10);x/=10;}reverse(all(res)); return res;}

void solve() {
  int n,m; cin>>m>>n;
  out(n*(n-1)/2+m*(m-1)/2);
}

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


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

int main(){
	int f=1;
	string s;
	cin >> s;
	for(int i=1; i<s.size(); i++){
		if(s[i]==s[i-1])f=0;
	}
	if(f==1)cout<<"Good"<<endl;
	else cout<<"Bad"<<endl;
	return 0;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
int main()
{
    int k,a,b;
    cin>>k;
  	cin>>a>>b;
    bool bo=false;
    for(int i=a;i<=b ;i++)
    {
         if(i%k==0)
         {
              bo=true;
           	  break;
         }
    }
    if(bo==true)
    {
         cout<<"OK";
    }
    else
    {
         cout<<"NG";
    }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
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; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
long long MOD = 1000000007;


template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }


int main(){
    int N, M ,C;
    cin >> N >> M >> C;

    vector<int>B(M);
    rep(i,M)cin >> B[i];

    int ans = 0;
    rep(i,N){

        long long a = 0;
        rep(i,M){
            int A;
            cin >> A;
            a += A*B[i];
        }
        a += C;
        if(a >0)ans ++;
    }
    cout << ans << endl;
}



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

using namespace std;

struct UnionFind {
    vector<int> d; // (d.at(i) >= 0): index of the parent of the element i, (-d.at(i) > 0): size of the set whose root is element i.

    UnionFind(int size = 0) : d(size, -1) {}
    
    // Return the root of element i.
    int find(int i) {
        return d.at(i) < 0 ? i : d.at(i) = find(d.at(i));
    }

    // Unite the set element i belongs to to the set element j does.
    bool unite(int i, int j) {
        i = find(i);
        j = find(j);
        
        if(i == j) return false;
        if(d.at(i) > d.at(j)) swap(i, j);
        d.at(i) += d.at(j);
        d.at(j) = i;
        return true;
    }
    
    // Return true if element i belongs to the set element j does.
    bool same(int i, int j) {
        return find(i) == find(j);
    }
    
    // Return the size of the set element i belongs to.
    int size(int i) {
        return -d.at(find(i));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, k;

    cin >> n >> m >> k;

    vector<int> nof(n + 1);
    int x, y;

    UnionFind uf(n + 1);

    for(int i = 0; i < m; ++i) {
        cin >> x >> y;
        uf.unite(x, y);
        ++nof.at(x);
        ++nof.at(y);
    }

    vector<int> ans(n + 1);

    for(int i = 1; i <= n; ++i) {
        ans.at(i) = uf.size(i) - 1 - nof.at(i);
    }

    for(int i = 0; i < k; ++i) {
        cin >> x >> y;
        if(uf.same(x, y)) {
            --ans.at(x);
            --ans.at(y);
        }
    }

    for(int i = 1; i < n; ++i) {
        printf("%d ", ans.at(i));
    }
    printf("%d\n", ans.at(n));

    return 0;
}

Measured memory_bytes: 2048
// https://atcoder.jp/contests/abc105/tasks/abc105_d
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define isvisiblechar(c) (0x21 <= (c) && (c) <= 0x7E)
#define cin scanner
#define cout printer
namespace {
class MaiScanner {
  public:
    template <typename T> void input_integer(T &var) {
        var = 0;
        T sign = 1;
        int cc = getchar_unlocked();
        for (; cc < '0' || '9' < cc; cc = getchar_unlocked())
            if (cc == '-')
                sign = -1;
        for (; '0' <= cc && cc <= '9'; cc = getchar_unlocked())
            var = (var << 3) + (var << 1) + cc - '0';
        var = var * sign;
    }
    inline int c() { return getchar_unlocked(); }
    inline MaiScanner &operator>>(int &var) {
        input_integer<int>(var);
        return *this;
    }
    inline MaiScanner &operator>>(long long &var) {
        input_integer<long long>(var);
        return *this;
    }
    inline MaiScanner &operator>>(string &var) {
        int cc = getchar_unlocked();
        for (; !isvisiblechar(cc); cc = getchar_unlocked())
            ;
        for (; isvisiblechar(cc); cc = getchar_unlocked())
            var.push_back(cc);
        return *this;
    }
    template <typename IT> void in(IT begin, IT end) {
        for (auto it = begin; it != end; ++it)
            *this >> *it;
    }
};
class MaiPrinter {
  public:
    template <typename T> void output_integer(T var) {
        if (var == 0) {
            putchar_unlocked('0');
            return;
        }
        if (var < 0)
            putchar_unlocked('-'), var = -var;
        char stack[32];
        int stack_p = 0;
        while (var)
            stack[stack_p++] = '0' + (var % 10), var /= 10;
        while (stack_p)
            putchar_unlocked(stack[--stack_p]);
    }
    inline MaiPrinter &operator<<(char c) {
        putchar_unlocked(c);
        return *this;
    }
    inline MaiPrinter &operator<<(int var) {
        output_integer<int>(var);
        return *this;
    }
    inline MaiPrinter &operator<<(long long var) {
        output_integer<long long>(var);
        return *this;
    }
    inline MaiPrinter &operator<<(char *str_p) {
        while (*str_p)
            putchar_unlocked(*(str_p++));
        return *this;
    }
    inline MaiPrinter &operator<<(const string &str) {
        const char *p = str.c_str();
        const char *l = p + str.size();
        while (p < l)
            putchar_unlocked(*p++);
        return *this;
    }
    template <typename IT> void join(IT begin, IT end, char sep = ' ') {
        for (bool b = 0; begin != end; ++begin, b = 1)
            b ? *this << sep << *begin : *this << *begin;
    }
};
} // namespace
MaiScanner scanner;
MaiPrinter printer;

int main(void) {
    int N, M, t;
    cin >> N >> M;
    // A[left, right) が M の倍数
    unordered_map<int, int> mp;
    mp[0]++;
    ll sum = 0, ans = 0;
    REP(i, N) {
        cin >> t;
        sum += t;
        ans += (mp[sum % M]++);
    }
    cout << ans << '\n';

    return 0;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    n%=10;
    if(n==3)cout<<"bon"<<endl;
    else if(n==0||n==1||n==6||n==8)cout<<"pon"<<endl;
    else cout<<"hon"<<endl;
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
int main(){
        ll t;
        cin >> t;
        map <string, int> mp;
        while (t--){
                string s;
                cin >> s;
                auto findit = mp.find(s);
                if (findit  == mp.end()){
                        mp.insert(make_pair(s, 1));
                }
                else {
                        mp[s] += 1;
                }
        }
        ll max=0;
        for (auto i=mp.begin(); i != mp.end(); i++){
                if ( max < i->second ){
                        max = i->second;
                } 
        }

        
        for (auto i=mp.begin(); i != mp.end(); i++){
                if ( max == i->second ){
                        cout << i->first << endl;
                } 
        }
        return 0;

}



Measured memory_bytes: 25216
#include <stdio.h>
#include <string.h>

int
main(int argc, char *argv[])
{
  char s[201];
  scanf("%s", s);
  
  int n = strlen(s);
  
  printf("%c%d%c\n", s[0], n - 2, s[n - 1]);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

int n;
int cum[24*60*60+10];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  while (cin >> n, n) {
    ZERO(cum);
    REP(i,n) {
      REP(j,2) {
        int hh,mm,ss;
        char c;
        cin >> hh >> c >> mm >> c >> ss;
        if (j == 0) {
          cum[hh*3600+mm*60+ss]++;
        } else {
          cum[hh*3600+mm*60+ss]--;
        }
      }
    }
    int ans = cum[0];
    REP(i,24*60*60) {
      cum[i+1] += cum[i];
      CHMAX(ans,cum[i+1]);
    }
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 3752
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}


fn f(s: &Vec<i32>) -> bool{

    


    return true;
}

use std::iter::Iterator;
use std::cmp;


fn main() {
    input! {
       n : i32,
       a : i32,
       b : i32,
    }

    let mut ans = a * n;

    if ans > b {
        ans = b;
    }

    println!("{}", ans);


}


Measured memory_bytes: 4352
#include <iostream>
#include <math.h>
using namespace std;
int main(int argc, char* argv[])
{
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	if (abs(A-C)<=D){
		cout<<"Yes"<<endl;
		return 0;
	}
	if (abs(A-B)<=D && abs(B-C)<=D){
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	return 0;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;
    bool ok = true;
    if(n%2 == 1) ok = false;
    rep(i,n/2){
        if(s[i] != s[i+n/2]) ok = false;
    }
    cout << (ok ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 3644
/* ****revpro**** */
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl     '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii      map<ll,ll>
using namespace std;

#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define N  100005
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  
#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update> 
void solve()
{
  ll ans=0;
  ll n,k;
  cin>>n>>k;
  rep(i,k,n+2)
  {
    ll tmp=n*(n+1)/2-(n-i)*(n-i+1)/2-i*(i-1)/2+1;
    // cout<<tmp<<endl;
    ans+=tmp%hell;
    ans%=hell;
  }
  cout<<ans<<endl;
}
signed main()
{
  
    /***********************************/
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 generator (seed);

  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int TESTS=1;
//  cin>>TESTS;
  while(TESTS--)
  {
    solve();
    
  }
  TIME
  return 0;
}

Measured memory_bytes: 3824
//naru-hodo
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<time.h>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#define ff first
#define ss second
#define ll long long
#define lli long long int
#define ull unsigned long long int
#define loop(i,x,n) for(ll int i=x; i<=n; i++)
#define rloop(i,x,n) for(ll int i=x; i>=n; i--)
using namespace std;
int main(){
    lli n, c;
    cin>>n>>c;
    lli wt[n], v[n];
    loop(i,0,n-1) cin>>wt[i]>>v[i];
    lli mx[n+1][c+1];
    loop(i,0,n){
        loop(j,0,c){
            if(i==0 || j==0) mx[i][j]=0;
            else if(j-wt[i-1]>=0){
                mx[i][j]=max(mx[i-1][j-wt[i-1]]+v[i-1], mx[i-1][j]);
            }
            else mx[i][j] = mx[i-1][j];
        }
    }
    cout<<mx[n][c];
    return 0;
}

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

using namespace std;

template <typename T>
T random(T lo, T hi) {
  std::random_device rd;
  std::uniform_int_distribution<T> uid(lo, hi);
  return uid(rd);
}

class RollingHash {
 private:
  const uint64_t mod = (UINT64_C(1) << 61) - 1;
  static inline uint64_t base = random(UINT64_C(10007), UINT64_C(1) << 28);
  std::vector<uint64_t> hashes, pows;

  inline uint64_t add(uint64_t a, uint64_t b) const {
    a += b;
    if (a >= mod) a -= mod;
    return a;
  }

  inline uint64_t sub(uint64_t a, uint64_t b) const {
    if (a < b) a += mod;
    a -= b;
    return a;
  }

  inline uint64_t mul(uint64_t a, uint64_t b) const {
    uint64_t ah = a >> 31, al = a & ((UINT64_C(1) << 31) - 1), bh = b >> 31,
             bl = b & ((UINT64_C(1) << 31) - 1), m = ah * bl + al * bh,
             v = (ah * bh << 1) + (m >> 30) +
                 ((m & ((UINT64_C(1) << 30) - 1)) << 31) + al * bl;
    v = (v & ((UINT64_C(1) << 61) - 1)) + (v >> 61);
    return v;
  }

 public:
  template <typename T>
  RollingHash(const T &S) : hashes(S.size() + 1, 0), pows(S.size() + 1, 0) {
    pows[0] = 1;
    for (size_t i = 0; i < S.size(); i++) {
      pows[i + 1] = mul(pows[i], base);
      hashes[i + 1] = add(mul(hashes[i], base), S[i]);
    }
  }

  template <typename T>
  RollingHash(const T &S, const uint64_t base)
      : hashes(S.size() + 1, 0), pows(S.size() + 1, 0) {
    pows[0] = 1;
    for (size_t i = 0; i < S.size(); i++) {
      pows[i + 1] = mul(pows[i], base);
      hashes[i + 1] = add(mul(hashes[i], base), S[i]);
    }
  }

  // S[l, r)
  uint64_t slice(int l, int r) const {
    return sub(hashes[r], mul(hashes[l], pows[r - l]));
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
  vector<int> S(N), T(N);
  for (int i = 0; i < N; i++) {
    S[i] = A[i] ^ A[(i + 1) % N];
    T[i] = B[i] ^ B[(i + 1) % N];
  }
  for (int i = 0; i < N; i++) {
    S.emplace_back(S[i]);
  }
  RollingHash rhs(S), rht(T);
  for (int i = 0; i < N; i++) {
    if (rhs.slice(i, i + N) == rht.slice(0, N)) {
      cout << i << ' ' << (A[i] ^ B[0]) << '\n';
    }
  }
  return 0;
}


Measured memory_bytes: 17000
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
const int mod = 1000000007;

signed main() {
	int n; cin >> n;
	map<int, int>M;
	int ans = 0;
	for (int i = 2; i*i <= n; i++) {
		while (n % i == 0) {
			M[i]++; n /= i;
		}
	}
	if (n != 1)M[n]++;
	for (auto itr = M.begin(); itr != M.end(); itr++) {
		int e = itr->second;
		int now = 1;
		while (now <= e) {
			e -= now; now++; ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3632
H, W = map(int, input().split())
a = [input() for _ in range(H)]

W_bList = []
H_bList = []

#Width から黒のある列をリスト化する
for i in range(W):
    w = []
    for j in range(H):
        w.append(a[j][i])  

    #print("W",i, w)
    if len(set(w)) == 2 or set(w) == set("#"):
        W_bList.append(i)

#Hight から黒のある行をリスト化する
for i in range(H):
    h = []
    for j in range(W):
        h.append(a[i][j])  

    #print("H", i, h)
    if len(set(h)) == 2 or set(h) == set("#"):
        H_bList.append(i)

#リストから答えとなる部分だけを抜き出す
#print(W_bList, H_bList)

for hl in H_bList:

    ans = ""
    
    for wl in W_bList:
        ans += str(a[hl][wl])

    print(ans)


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

using namespace std;

//#define FILE_IO

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    int v[4];
    for(int i = 0; i < 4; i++)
        scanf("%d", &v[i]);
    for(int i = 1; i < 4; i++)
        v[i] = min(v[i], 2 * v[i - 1]);

    int N;
    cin >> N;

    long long ans = 0;
    if(v[3] < v[2] * 2)
        ans = 1LL * v[3] * (N / 2) + (N % 2 == 0 ? 0 : v[2]);
    else
        ans = 1LL * v[2] * N;

    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

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

const int MOD = 1e9+7;
const int MAX = 111;

ll pow(ll x, ll n) {
  if (n == 0) return 1;
  if (n&2) return (x*pow(x*x%MOD, n/2)) % MOD;
  return pow(x*x%MOD, n/2);
}

ll dp[MAX][8];

// p[k][0] → 端に追加しないパターンの数
// p[k][1] → 端に追加する、しないのパターンの総数
ll p[10][2];
int W, H, K;

void init() {
  p[0][0] = 1; // 横線を追加しない
  p[0][1] = 0; // 横線を追加する
  FOR (i, 1, 10) {
    p[i][0] = (p[i-1][0] + p[i-1][1])%MOD;
    p[i][1] = p[i-1][0]; // 追加するときは前の追加しないものと同数
  }
  REP (i, 10) (p[i][1] += p[i][0]) %= MOD;
}

int main() {

  init();

  cin >> H >> W >> K;
  K--;

  if (W == 1) {
    cout << 1 << endl;
    return 0;
  }
  dp[0][0] = 1;
  FOR (i, 1, W) dp[0][i] = 0;

  FOR (h, 1, H+1) {
    dp[h][0] = (dp[h-1][1]*p[W-2][0]%MOD + dp[h-1][0]*p[W-2][1]%MOD) % MOD;
    FOR (i, 1, W-1)
      dp[h][i] = (dp[h-1][i-1]*p[i-1][0]%MOD*p[W-i-1][0]%MOD
                  +dp[h-1][i+1]*p[i][0]%MOD*p[W-i-2][0]%MOD
                  +dp[h-1][i]*p[i-1][1]%MOD*p[W-i-2][1]%MOD ) %MOD;
    dp[h][W-1] = (dp[h-1][W-2]*p[W-2][0]%MOD + dp[h-1][W-1]*p[W-2][1]%MOD) % MOD;

    /*
    REP (j, W) cout << dp[h][j] << " ";
    cout << endl;
    */
  }

  cout << dp[H][K] << endl;
  return 0;

}

Measured memory_bytes: 256