akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)


template<typename T>
T gcd(T n, T m){

    if(m > n)  return gcd(m, n);

    T r = n % m;
    if(r == 0) return m;
    else       return gcd(m, r);
}


int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll a, b; cin >> a >> b;
    ll g = gcd(a, b);

    ll s = sqrt(g) + 1;

    ll ans = 1;
    reps(i, 2, s+1){
        if(g % i == 0){
            ans++;
            while(g % i == 0) g /= i;
        }
    }

    if(g > 1) ans++;

    cout << ans << endl;



    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long  a,ans=1,mod=1000000007;
int main()
{
    cin>>a;
    for(int i=1;i<=a;i++)
	{
		ans*=i;
		ans%=mod;
	}
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long LL;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define X first
#define Y second

vector<LL> memo;

LL solve(int n) {
	if (n < 0) return 0;
	if (memo[n] != -1) return memo[n];
	if (n == 0) return memo[n] = 1;

	return memo[n] = solve(n - 1) + solve(n - 2) + solve(n - 3);
}

int main(void) {
	memo.resize(31, -1);
	int N;
	
	while (cin >> N, N) {
		cout << (solve(N) / 10 + 365) / 365 << endl;
	}

	return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <string>

using namespace std;

int main()	{
  string s;
  cin >> s;
  int n = s.length();
  int freq[27] = {0};
  for (int i = 0; i < n; i++)	{
    freq[int(s[i] - 'a')]++;
  }
  bool flag = false;
  for (int i = 0; i < 26; i++)	{
    if (freq[i] == 0)	{
      cout << char(i + 'a') << endl;
      flag = true;
      break;
    }
  }
  if (!flag)	{
    cout << "None" << endl;
  }
  return 0;
}

Measured memory_bytes: 3728
#include <iostream>

using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;

    for (int y=0; y<10000; y++) {
        if ( ( (int)((double)y*0.08) == a )
                &&( (int)((double)y*0.1) ==b) ) {
            cout << y;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

ll f(ll b, ll n) {
    if(n < b) return n;
    return f(b, n/b) + n % b;
}

int main(){
    ll n, s;
    cin >> n >> s;
    if(s == n) {
        cout << n+1 << endl;
        return 0;
    }
    REP(b, 2, 1e6+10) {
        if(f(b, n) == s) {
            cout << b << endl;
            return 0;
        }
    }
    ll ans = 1e18;
    REP(p, 1, 1e6) {
        ll q = s - p;
        // n = pb + q
        ll b = (n-q)/p;
        if(b >= 2 && q >= 0 && n == p * b + q && f(b, n) == s) {
            ans = min(ans, b);
        }
    }
    if(ans == 1e18) ans = -1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;

int n,t;
int a,b;
int ans;
int main()
{
	ans=100000;
	cin>>n>>t;
	rep(i,n)
	{
		cin>>a>>b;
		if(b<=t)ans=min(ans,a);
	}
	if(ans==100000)cout<<"TLE"<<endl;
	else cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int>P;
int color[100005]={0};
vector<P>node[100005];
int dfs(int pos,int from,int before_color);
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    node[a].push_back(P(b,i));
    node[b].push_back(P(a,i));
  }
  
  int maxim_point=1;
  for(int i=1;i<=n;i++){
    if(node[i].size()>node[maxim_point].size()){
      maxim_point=i;
    }
  }
  
  dfs(maxim_point,0,0);
  cout<<node[maxim_point].size()<<endl;
  for(int i=0;i<n-1;i++){
    cout<<color[i]<<endl;
  }
  return(0);
}

int dfs(int pos,int from,int before_color){
  int now_color=1;
  for(int i=0;i<node[pos].size();i++){
    int next=node[pos][i].first;
    int edge_num=node[pos][i].second;
    if(now_color==before_color){
      now_color++;
    }
    if(next!=from){
      color[edge_num]=now_color;
      dfs(next,pos,now_color);
      now_color++;
    }
  }
  return(0);
}


Measured memory_bytes: 9344
import java.util.Scanner;

public class Main
{

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int r = 1;
        int n = 1;
        for (int b = 0; b != 9; b++) {

            for (int i = 0; i != 9; i++) {
                System.out.println(r + "x" + n + "=" + r * n);
                n++;
            }
            n = 1;
            r++;
        }

    }

}



Measured memory_bytes: 25920
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;
typedef long long Int;
typedef pair<int, int> P;
typedef pair<int, P> T;
int u[108000];

int r(int x){
  if(x == u[x])return x;
  return u[x] = r(u[x]);
}

int unite(int x, int y){
  x = r(x);
  y = r(y);
  u[x] = y;
}

int n, x, y;
vector<P> xs, ys;
vector<T> edges;

int main(){
  for(int i = 0;i < 108000;i++)u[i] = i;
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> x >> y;
    xs.push_back(P(x, i));
    ys.push_back(P(y, i));
  }
  sort(xs.begin(), xs.end());
  sort(ys.begin(), ys.end());

  for(int i = 1;i < n;i++){
    int a, b, dist;
    a = xs[i-1].second;
    b = xs[i].second;
    dist = xs[i].first - xs[i-1].first;
    edges.push_back(T(dist,P(a, b)));
  
    a = ys[i-1].second;
    b = ys[i].second;
    dist = ys[i].first - ys[i-1].first;
    edges.push_back(T(dist,P(a, b)));
  }
  sort(edges.begin(), edges.end());
  Int res = 0;
  for(int i = 0;i < edges.size();i++){
    int a = edges[i].second.first;
    int b = edges[i].second.second;
    int d = edges[i].first;
    if(r(a) == r(b))continue;
    res += d;
    unite(a, b);
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 7528
// created_by  Rishi_Mohan

#include<bits/stdc++.h>

#define    ll           long long
#define    db1(x)       cout<<#x<<"="<<x<<'\n'
#define    db2(x,y)     cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define    db3(x,y,z)   cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define    rep(i,n)     for(int i=0;i<(n);++i)
#define    repA(i,a,n)  for(int i=a;i<=(n);++i)
#define    repD(i,a,n)  for(int i=a;i>=(n);--i)

using namespace std;

void solve()
{
   ll x;
   cin >> x;
   ll k = (x/500)*1000;
  // db1(k);
   x-=(x/500)*500;
  // db1(x);
    k += (x/5)*5;
  // db1(k);
   x-=(x/5)*5;
  // if(x<5) k+=5;
   cout << k ;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}

Measured memory_bytes: 256
import sys
import itertools
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(itertools.chain(*dp)) ** 2)

Measured memory_bytes: 58072
def factorial(num):
    if num==0 or num==1:
        return 1
    else:
        return num*factorial(num-1)

N,A,B=map(int,input().split())
v=list(map(int,input().split()))
v.sort()
maxsum=0
for i in range(0,A):
    maxsum+=v[N-1-i]
maxaverage=((maxsum*(10**6))//A)/(10**6)

s=v[N-A]
count1=0
count2=0
for i in range(0,A):
    if v[N-1-i]==s:
        count1+=1
for i in range(0,N):
    if v[i]==s:
        count2+=1
if count1!=A:
    way=factorial(count2)//(factorial(count1)*factorial(count2-count1))
    print(maxaverage)
    print(way)
else:
    way=0
    for i in range(A,min(count2,B)+1):
        way+=factorial(count2)//(factorial(i)*factorial(count2-i))
    print(maxaverage)
    print(way)


Measured memory_bytes: 3064
n,m = map(int,input().split())
ab = [0]*n
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab[a-1] += 1
    ab[b-1] += 1

flag = False

for i in ab:
    if i%2 == 1:
        flag = True
        break

if flag:
    print('NO')
else:
    print('YES')

Measured memory_bytes: 46296
# A - キャンディーと2人の子供

# それぞれ数個ずつキャンディーの入ったパックが3個ある
# 二人の子供に、キャンディーを等しい数ずつ分けられるか判定する


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

if a + b == c \
or a + c == b \
or b + c == a:
    print('Yes')
else:
    print('No')


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;
  cin >> N;
  ll MOD = 1e9 + 7;
  map<ll, ll> primes;
  for(int i = 2; i <= N; i++) {
    bool ok = true;
    for(int j = 2; j < i; j++) {
      if(i % j == 0) { ok = false; }
    }
    if(ok) { primes[i] = 0; }
  }
  for(auto x : primes) {
    // cout << x.first << endl;
    ll cnt = 0;
    ll tmp = x.first;
    while(1) {
      if(N / tmp == 0) { break; }
      cnt += N / tmp;
      tmp *= x.first;
    }
    primes[x.first] = cnt;
  }
  ll ans = 1;
  for(auto x : primes) {
    ans = (ans * (x.second + 1)) % MOD;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

bool all_same(string s) {
    FOR(i, 0, s.length() - 1) {
        if (s[i] != s[i + 1])return false;
    }
    return true;
}

int main() {
    init();

    string s;
    cin >> s;

    int ans = INF;
    FOR(i, 0, 26) {
        char c = 'a' + i;
        string t = s;
        int cnt = 0;
        while (!all_same(t)) {
            string next = "";
            FOR(j, 0, t.length() - 1) {
                if (t[j] == c || t[j + 1] == c)next += c;
                else next += t[j];
            }
            t = next;
            cnt++;
        }
        chmin(ans, cnt);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
N = int(input())
a = 1
b = 1
c = 1
for i in range(N):
  a = (a * 10) % (10**9 + 7)
  b = (b * 9) % (10**9 + 7)
  c = (c * 8) % (10**9 + 7)
print((a + c - (2 * b)) % (10**9 + 7))
  

Measured memory_bytes: 9160
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = (m); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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

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

template<class T> inline auto __lcm(T& a, T& b) 
{ return a * b / __gcd(max(a, b), min(a, b)); }

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

    rep(i, S.size()-1) {
        if (S[i] == S[i+1]) {
            print("Bad");
            return 0;
        }
    }

    print("Good");
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int N;
    cin >> N;
    int a, b;
    for (a = 1; a <= 9; ++a)
    {
        if (N % a == 0)
        {
            b = N / a;
            if (b <= 9)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)a;i<(int)b;++i)
int main(){
  int x,y,z;cin>>x>>y>>z;
  int cnt=x/(y+z);
  int a=x%(y+z);
  if(a<z)cnt--;
  cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
S = list(input())
if S[-1] == '<':
  S.append('>')
else:
  S.append('<')
output = 0
count = 0
num_list = []

if S[0] == '>':
  model = 0
else:
  model = 1
s_pre = S[0]
for i in range(len(S)):
  s = S[i]
  if s != s_pre or i == len(S)-1:
    num_list.append(count)
    count = 1
    s_pre = s
  else: 
    count += 1
if model == 0:
  output += num_list[0]*(num_list[0]+1)/2
  num_list = num_list[1:]

for i in range(len(num_list)//2):
  n_max = max(num_list[2*i], num_list[2*i+1]) #同じ場合考える
  n_min = min(num_list[2*i], num_list[2*i+1])
  output += n_max*(n_max+1)/2
  output += (n_min-1)*n_min/2
if len(num_list)%2 == 1:
  output += num_list[-1]*(num_list[-1]+1)/2
print(int(output))

Measured memory_bytes: 11700
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ll long long
#define P pair<int,int>
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MOD = 1000000007;
const int INF = 2002002002;
const ll LLINF = 9009009009009009009;
using namespace std;

int main() {
    fast_io
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    rep(i,n) cin >> v[i];

    int ans = 0;
    rep(n_l, n+1) {
        rep(n_r, n+1) {
            if (n_l + n_r > n || n_l + n_r > k) break;
            priority_queue<int, vector<int>, greater<int>> neg_v;
            int total = 0;
            rep(i,n_l) {
                total += v[i];
                if (v[i] < 0) neg_v.push(v[i]);
            }
            rep(i,n_r) {
                int ind = n - 1 - i;
                total += v[ind];
                if (v[ind] < 0) neg_v.push(v[ind]);
            }
            int rest_k = k - n_l - n_r;
            while (rest_k > 0 && !neg_v.empty()) {
                total -= neg_v.top();
                neg_v.pop();
                rest_k--;
            }
            ans = max(ans, total);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> A(Q);
  vector<int> B(N);
  for(int i = 0; i < N ; i++){
    B[i] = K - Q;
  }
  for(int i = 0; i < Q ; i++){
    cin >> A[i];
    B[A[i]-1]++;
  }
  for(int i = 0; i < N ; i++){
    if(B[i] > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

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

int main() {
  
  long long H,N;
  cin >> H;
  cin >> N;

  long long dam =0;
  vector <long long>vec(N);
  
  for( long long i = 0;i<N;i++){
    cin >> vec.at(i);
    dam += vec.at(i);
  }

  
  
  string res = "";

  if(H > dam){
    res = "No";
  }
  else{
    res = "Yes";
  }
  
  cout << res << endl;
}





Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int minR=sc.nextInt();
		int maxR=-1000000000;
		for(int i=1;i<n;i++){
			int R=sc.nextInt();
			maxR=Math.max(maxR,R-minR);
			minR=Math.min(minR, R);
		}
		System.out.println(maxR);
	}

}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> city(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    city.at(a - 1)++;
    city.at(b - 1)++;
  }
  
  for (int i = 0; i < N; i++) {
    cout << city.at(i) << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;


int main() {
	ll N, T, A;

	cin >> N;
	cin >> T >> A;
	vector<ll> H(N);

	double ans;
	ll a = 1;

	cin >> H[0];

	ans = abs((float)(A - (T-H[0]*0.006)));

	for (int i = 1; i < N; i++) {
		cin >> H[i];
		double temp = abs((double)(A - (double)(T-(double)(H[i]*0.006))));
		if (temp < ans) {
			ans = temp;
			a = i + 1;
		}
	}

	cout << a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  int H,W;

  cin >> H >> W ;

  vector<string> S(H);

  for(int i=0;i<H;i++) cin >> S.at(i);

  vector<int> dx={0,1,-1,0};
  vector<int> dy={1,0,0,-1};//上下左右4通りの座標変化

  bool can=true;

  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){

      if(S.at(i).at(j)=='.') continue;

      int count=0;
      
      for(int d=0;d<4;d++){
        int id=i+dy.at(d);
        int jd=j+dx.at(d);

        if(id<0||H<=id) continue;
        if(jd<0||W<=jd) continue;
        if(S.at(id).at(jd)=='#') count++;
      }

      if(count==0){can=false; break;}//#マスの中に、上下左右に#がないものがあった場合
    
    }
  }//全てのマスについて、その周囲のマスに存在する#の数に置き換え

  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;
 
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef long double ld;
typedef vector<ll>VI;
typedef pair<ll,ll>P;
#define VV(T) vector<vector<T>>
#define sz(x) int(x.size())
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
#define chmax(x,a) x=max(x,a)
#define chmin(x,a) x=min(x,a)
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX6 1001001//6
#define MAX7 10010010//7
#define SENTINEL 2000000000//9
const int MOD = 1000000007;
#define INF 1<<30
#define INFTY 1LL<<61
#define MAX_INT INT_MAX
#define Endl '\n'
#define CLR(mat) memset(mat, 0, sizeof(mat))
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}
template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}
using Edge=pair<int,ll>;
using Graph=vector<vector<ll> >;//ll or Edge
//const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// sort_reverse -> greater<long long>()
// vector型から重複を削除 list.erase(unique(ALL(list)),list.end());
// g++ -o a a.cpp -Wall -lm -std=c++17
//push_back -> emplace_back

int N,S;
int A[3010];
ll dp[3010][3010];//dp[i][j]:=i番目の数まで見たときに和がjとなる組み合わせ
const ll mod=998244353;
int main(){
   cin>>N>>S;
   rep(i,N)cin>>A[i];
   dp[0][0]=1;//
   for(int i=0;i<N;i++){
      for(int j=0;j<3001;j++){
         if(j-A[i]>=0)dp[i+1][j]+=dp[i][j-A[i]];
         dp[i+1][j]+=dp[i][j]*2%mod;
         dp[i+1][j]%=mod;
      }
   }
   cout<<dp[N][S]<<endl;
}

Measured memory_bytes: 74200
n,p = map(int, input().split())
As = list(map(int, input().split()))
def comb(n,k):
    y = 1
    x = 1
    if k == 0:
        return 1
    while k >= 1:
        x *= (n-k+1)
        y *= k
        k -= 1
    return x//y   
# 偶奇の問題
ps = [a%2 for a in As]
cnt_o = sum(ps)
cnt_e = n - cnt_o

n_o = 0
for i in range(p,cnt_o+1,2):
    n_o += comb(cnt_o,i)

print(n_o*2**cnt_e)

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int now = 0;
  int mi = 0;
  rep(i, n) {
    now += s[i] == '(' ? 1 : -1;
    amin(mi, now);
  }
  cout << string(-mi, '(');
  cout << s;
  cout << string(now - mi, ')') << endl;
}

Measured memory_bytes: 256
#define CIN_ONLY 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const double PI = 3.14159265358979323846;

ll comb[51][51];

int main()
{
	comb[0][0] = 1;
	for (int i = 1; i <= 50; ++i) {
		comb[i][0] = 1;
		for (int j = 1; j <= 50; ++j) {
			comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
		}
	}
	if (CIN_ONLY) {
		ios::sync_with_stdio(0);
		cin.tie(0);
	}
	int n, p;
	cin >> n >> p;
	int no = 0, ne = 0;
	for (int i = 0; i < n; ++i) {
		int a;
		scanf("%d", &a);
		if (a & 1) {
			++no;
		} else {
			++ne;
		}
	}
	ll ans = 0;
	for (int i = 0; i <= no; ++i) {
		if (!(i & 1) ^ p) {
			ans += comb[no][i];
		}
	}
	ans *= 1ll << ne;
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
import java.util.Arrays;

public class Main {
  private static void solve() {
    int n = ni();
    int[] x = new int[n + 1];
    int[] y = new int[n + 1];
    for (int i = 0; i < n; i ++) {
      x[i] = ni();
      y[i] = ni();
    }
    Arrays.sort(x);
    Arrays.sort(y);
    
    long ret = 0;
    for (int i = 0; i <= n; i ++) {
      if (y[i] < x[n - i]) {
        ret += (x[n - i] - y[i]) * 2;
      }
    }
    System.out.println(ret);
  }


  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}




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

ll dp[1005][10005];

struct S
{
    ll w,s,v;
    bool operator < (const S& b) const
    {
        return w+s > b.w+b.s;
    }
};

S ar[10005];
int main()
{
    int n;
    cin>>n;
    vector<S>vec;
    for(int i=1; i<=n; i++)
    {
        ll w,s,v;
        cin>>w>>s>>v;
        ar[i].w = w;
        ar[i].s = s;
        ar[i].v = v;
    }
    sort(ar+1,ar+n+1);
    for(int i=0; i<=1000; i++)
    {
        for(int j=0; j<=10000; j++) dp[i][j] = -INF;
    }

    for(int i=1; i<=n; i++) dp[i][ar[i].s] = ar[i].v;

    for(int i=1; i<=n-1; i++)
    {
        for(int j=0; j<=10000; j++)
        {
            if(dp[i][j]>=0 )
            {
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
                if(j-ar[i+1].w >= 0)
                {
                    ll t = min(ar[i+1].s,j-ar[i+1].w);
                    dp[i+1][t] = max(dp[i+1][t],dp[i][j]+ar[i+1].v);
                }
            }
        }
    }
    ll ans = 0;
    for(int i=0; i<=10000; i++) ans = max(ans,dp[n][i]);
    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 78464
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author rahdirigs
 */

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

template <typename T> void add(T& a, T b, int mod) {
	a += b;
	if (a >= mod)
		a -= mod;
}

template <typename T> void sub(T& a, T b, int mod) {
	a -= b;
	if (a < 0)
		a += mod;
}

class TaskM {
	static const int mod = 1e9 + 7;
public:
	void solve(std::istream& in, std::ostream& out) {
		int N, K;
		in >> N >> K;
		vector<int> a(N + 1);
		vector<vector<ll>> dp(N + 1, vector<ll> (K + 1, 0));
		for (int i = 1; i <= N; i++) in >> a[i];
		dp[0][0] = 1;
		for (int i = 1; i <= N; i++) {
			vector<ll> pref(K + 1, 0);
			pref[0] = dp[i - 1][0];
			for (int j = 1; j <= K; j++) add(pref[j], dp[i - 1][j] + pref[j - 1], mod);
			for (int j = 0; j <= K; j++) {
				dp[i][j] = pref[j];
				if (j - a[i] - 1 >= 0) sub(dp[i][j], pref[j - a[i] - 1], mod);
			}
		}
		out << dp[N][K];
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	TaskM solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 83004
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <deque>
using namespace std;

#define next '\n'
#define sp " "
#define print(x) cout << (x)
#define println(x) cout << (x) << next
#define stop return(0)
#define rep(i, n) for(int (i) = (0); (i) < (n); (++i))
#define FOR(i, start, end) for(int (i) = (start); (i) < (end); (++i))
#define foreach(e, elem) for(auto& (e) : (elem))
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define size(s) (s).size()
#define all(vec) (vec).begin(), (vec).end()
#define pb(e) push_back(e);
using ll = long long;
using ull = unsigned long long;

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

    int r = 0, b = 0;
    foreach(e, s){
        if(e == 'R'){
            r++;
        }else{
            b++;
        }
    }

    if(r > b){
        println("Yes");
    }else{
        println("No");
    }

}

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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const string YES = "POSSIBLE";
const string NO = "IMPOSSIBLE";

int main(){
    int n;
    cin >> n;
    vector<vi> g(n);
    rep1(i, n-1) {
        int p;
        cin >> p;
        --p;
        g[i].pb(p);
        g[p].pb(i);
    }
    vi x(n);
    rep(i, n) cin >> x[i];
    queue<int> q;
    vi d(n, -1);
    vi ord;
    q.push(0);
    d[0] = 0;
    ord.pb(0);
    while (!q.empty()) {
        int p = q.front(); q.pop();
        int di = d[p];
        for (int to : g[p]) {
            if (d[to] != -1) continue;
            q.push(to);
            d[to] = di + 1;
            ord.pb(to);
        }
    }
    reverse(all(ord));
    vi val(n, INF);
    rep(i, n) {
        int sum = 0;
        vector<bool> dp(x[ord[i]]+1);
        dp[0] = true;
        for (int to : g[ord[i]]) {
            if (to < ord[i]) continue;
            vector<bool> tdp(x[ord[i]]+1);
            repr(j, x[ord[i]]+1) {
                if (j-x[to]>=0) tdp[j] = (tdp[j] | dp[j-x[to]]);
                if (j-val[to]>=0) tdp[j] = (tdp[j] | dp[j-val[to]]);
            }
            dp = tdp;
            sum += x[to] + val[to];
        }
        int mx = x[ord[i]];
        while (mx >= 0) {
            if (dp[mx]) break;
            --mx;
        }
        if (mx >= 0) val[ord[i]] = sum - mx;
        else {
            cout << NO << endl;
            return 0;
        }
    }
    cout << YES << endl;
    return 0;
}


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

#define INF 1000000

// xの累乗円のコインを生成
void make_multiplier(int x, int N, vector<int>& coins) {
    int num = x;
    while(num <= N) {
        coins.push_back(num);
        num *= x;
    }
}

int main() {
    int N;
    cin >> N;
    // DPテーブルを生成、初期化
    int dp[100010];
    for(int i = 0;i < 100010;i++) dp[i] = INF;
    dp[0] = 0;

    // コイン生成
    vector<int> coins = {1};
    make_multiplier(6, N, coins);
    make_multiplier(9, N, coins);

    sort(coins.begin(), coins.end());
    unique(coins.begin(), coins.end());

    // i番目までのコインを使ってj円引き出すときの最小回数
    int m = coins.size();
    for(int i = 0;i < m;i++) {
        int j = 0;
        while(j + coins.at(i) <= N) {
            if(dp[j + coins.at(i)] > dp[j] + 1) dp[j + coins.at(i)] =  dp[j] + 1;
            j++;
        }
    }

    cout << dp[N] << endl; // N円引き出すときの最小枚数
}

Measured memory_bytes: 640
using System;
class Program {
  static void Main(string[] args) {
    int N = int.Parse(Console.ReadLine());

    int ans = 0;
    while (N > 0) {
      ans += N % 10;
      N /= 10;
    }

    Console.WriteLine(ans == 1 ? 10 : ans);
  }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b;
  cin>>a>>b;
  int c;
  if(b/10<1){
    c=10*a+b;
  }
  if(1<b/10&&b/10<10){
    c=100*a+b;
  }
  if(b==100){
    c=1000*a+b;
  }
  for(int i=1;i<500;i++){
    if(i*i==c){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
}

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

int A, B, C, D;

int main() {
  scanf("%d%d%d%d", &A, &B, &C, &D);
  int amount = 0;
  amount += A < B ? A : B;
  amount += C < D ? C : D;
  printf("%d\n", amount);
  return 0;
}

Measured memory_bytes: 256
// J4180449 三宅亮輔
// 問題名
// - search
// 問題URL
// - https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_C
// 所要時間
// - 30分
// 学んだこと
//  std::setの使いかたを学んだ
//
//  荷物を積める作業で累積和を二分探索すればさらに計算量を減らせそうだと思った

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

typedef long long ll;
set<string> s;
int N;
int main() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        string a, b;
        cin >> a >> b;
        if(a == "insert")
            s.insert(b);
        else
            cout << ((s.count(b) > 0) ? "yes" : "no") << endl;
    }
}


Measured memory_bytes: 32104
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
 
#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)
 
typedef long long ll;
typedef pair<int, int> pii;

int n, k;

const int MAX = 1121;
int pp[MAX];
vector<int> primes;

void erat()
{
	memset(pp, -1, sizeof(pp));

	pp[0] = pp[1] = 0;
	for (int i = 2; i < MAX; i++)
		for (int j = 2*i; j < MAX; j += i)
			pp[j] = 0;

	rep(i, MAX)
		if (pp[i])
			primes.push_back(i);
}

const int K_MAX = 16;
const int P_MAX = 190;

ll dp[MAX][K_MAX][P_MAX];

ll solve(int s, int c, int i)
{
	if (s == n && c == k) return dp[s][c][i] = 1;
	if (s >= n || c == k) return 0;
	if (dp[s][c][i] != -1) return dp[s][c][i];
	if (!(i < primes.size())) return dp[s][c][i] = 0;

	int cnt = 0;
	cnt += solve(s+primes[i], c+1, i+1);
	cnt += solve(s, c, i+1);
	return dp[s][c][i] = cnt;
}

int main()
{
	erat();
	const int psz = primes.size();
	while (cin >> n >> k, n|k) {
		memset(dp, -1, sizeof(dp));
		cout << solve(0, 0, 0) << endl;

		/*
		memset(dp, 0, sizeof(dp));
		for (int s = n; s >= 0; s--) {
			for (int c = k; c >= 0; c--) {
				for (int i = psz-1; i >= 0; i--) {
					if (s == n && c == k) {
						dp[s][c][i] = 1;
					} else {
						dp[s][c][i] = 0;
						if (s+primes[i] <= n)
							dp[s][c][i] += dp[s+primes[i]][c+1][i+1];
						dp[s][c][i] += dp[s][c][i+1];
					}
				}
			}
		}
		cout << dp[0][0][0] << endl;
		*/
	}
	return 0;
}

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

typedef long long ll;
typedef long double Double;
#define rep(i,n) for(int i = 0; i < (int)(n) ; i++)

// chmax, chmin
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;
}

class UnionFind {
  std::vector<int> p;

public:
  UnionFind(int n) : p(n, -1) {}

  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }

  bool same(int x, int y) { return root(x) == root(y); }

  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) std::swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    return true;
  }
};


void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){
    int ans = N - 1;
    UnionFind uf(N);
    for(int i = 0 ; i < M ; i++){
        A[i]--;
        B[i]--;
        if(uf.unite(A[i], B[i])){
            ans--;
        }
    }
    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, M, std::move(A), std::move(B));
    return 0;
}



Measured memory_bytes: 5432
#include <stdio.h>
#include <math.h>

int main(void)
{
	int n;
	double debt=100000.0;

	scanf("%d",&n);
	while(n--){
		debt*=1.05;
		debt=ceil(debt/1000)*1000;
	}
	printf("%.0f\n",debt);

	return 0;
}

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

int main() {
  int X; cin >> X;
  
  int shimoni = X % 100;
  int cnt = 0;
  while (shimoni > 0) {
    if (shimoni >= 5) {
      shimoni -= 5;
      cnt++;
    } else if (shimoni >= 4) {
      shimoni -= 3;
      cnt++;
    } else if (shimoni >= 3) {
      shimoni -= 3;
      cnt++;
    } else if (shimoni >= 2) {
      shimoni -= 2;
      cnt++;
    } else if (shimoni >= 1) {
      shimoni -= 1;
      cnt++;
    }
  }
  cout << (X/100 >= cnt ? "1" : "0") << endl;
  return 0;
}

Measured memory_bytes: 256
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std; 

int  dp[1001][20005] ; 

inline void solve(){ 
    fill(dp[0]+1,dp[0]+20005,1000000000);
    dp[0][0] = 0 ; 
    int  health , n ; 
    cin >> health >> n ; 
    for (int i=1;i<=n;i++){ 
        int  a, b; 
        cin >> a >> b; 
        for (int j=0;j<=20000;j++){ 
            if(a > j) dp[i][j] = dp[i-1][j] ; 
            else dp[i][j] = min(dp[i-1][j],dp[i][j-a]+b); 
        } 
    } 
    cout << *min_element(dp[n]+health,dp[n]+20001) << endl; 
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<int,int> P;

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define repr(i,b,a) for(int i=int(b);i>=(a);i--)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x,p/2);
	if(p%2==1)res=res*x;
	return res;
}

int main()
{
	ll x;
	cin>>x;


	repi(a,-1000,1001){
		repi(b,-1000,1001){
			if(power(a,5) - power(b,5)==x){
				cout<<a<<" "<<b<<endl;
				return 0;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3584
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int gcd(int x, int y){
    int r = x % y;
    while(r != 0){
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> c(m);
    rep(i, m){
        cin >> c[i];
    }
    SORT(c);
    int dp[25][50050]; //dp[i][j] i番目まででj円払うのに必要な枚数
    rep(i, m){
        dp[i][0] = 0;
    }
    rep(i, m){
        rep(j, n+1){
            if(i == 0){
                dp[i][j] = j;
            }else if(j >= c[i]){
                dp[i][j] = min(dp[i-1][j], dp[i][j-c[i]] + 1);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[m-1][n] << endl;
    return 0;
}


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

#define ll long long int
#define endl '\n'
#define inf 1e18
ll a[100005],b[100005],c[100005];
void testCase()
{
    
   // ll t; cin>>t; while(t--)
    {
      ll n;
      cin>>n;

      for(int i=1;i<=n;i++)
      {
          cin>>a[i]>>b[i]>>c[i];
      }
      ll ans=0;
      for(int i=2;i<=n;i++)
      {
          a[i]=max(a[i]+b[i-1],a[i]+c[i-1]);
          b[i]=max(b[i]+a[i-1],b[i]+c[i-1]);
          c[i]=max(c[i]+b[i-1],c[i]+a[i-1]);
      }
      cout<<max({a[n],b[n],c[n]});
    }       
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    testCase();
    return 0;
}

Measured memory_bytes: 5916
k = int(input())
ans = 0
import math
from functools import reduce

def gcd(*num):
    return reduce(math.gcd, num)

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)
print(ans)

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

#define ll long long
#define N 100010
const ll p = (ll)1e9 + 7;
int n, cnt[200];
char s[N];

int main()
{
	while (scanf("%d", &n) != EOF)
	{
		scanf("%s", s + 1);
		memset(cnt, 0, sizeof cnt);
		for (int i = 1, len = strlen(s + 1); i <= len; ++i)
			++cnt[s[i] - 'a'];
		ll res = 1;
		for (int i = 0; i < 26; ++i)
			res = (res * (cnt[i] + 1)) % p;
		printf("%lld\n", (res - 1 + p) % p);
	}
	return 0;
}


Measured memory_bytes: 384
// C - Ubiquity
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define MOD 1000000007

// a^n mod m を計算する(繰り返し二乗法,二分累乗法:O(logn)) (再帰版)
ll modpow(ll a,ll n){return n?modpow(a*a%MOD,n/2)*(n%2?a:1)%MOD:1;}

int main(){
	int N; cin>>N;
	ll n10 = modpow(10, N), n9 = modpow(9, N), n8 = modpow(8, N);
	ll ans = n10 - (2 * n9) % MOD;
	ans %= MOD;
	ans += n8;
	ans %= MOD;
	cout<< (ans + MOD) % MOD <<endl;
}


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

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

    int64_t n; cin >> n;
    int64_t cnt = 0;
    if (n % 2 == 0) {
        for (int64_t pwr = 5; pwr <= n / 2; pwr *= 5)
            cnt += n / 2 / pwr;
    }

    cout << cnt << '\n';
    return 0;
}


Measured memory_bytes: 256
def main():
	n = int(input())
	a = list(map(int, input().split()))
	printlist(a)
	insertionSort(a, n)

def insertionSort(a, n):
	for i in range(1,n):
		v = a[i]
		j = i - 1
		while j >= 0 and a[j] > v:
			a[j + 1] = a[j]
			j -= 1
		a[j+1] = v
		printlist(a)

def printlist(a):
	values = map(str, a)
	print(' '.join(values))

main()


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

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

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

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    int N = input();

    vector< int > x(N), y(N), h(N);
    range(i, 0, N) cin >> x[i] >> y[i] >> h[i];

    range(cx, 0, 101) range(cy, 0, 101) {
        i64 H = -1;
        range(i, 0, N) {
            if (h[i] == 0) continue;
            H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
        }

        bool f = true;
        range(i, 0, N) {
            if (h[i] != max(H - abs(x[i] - cx) - abs(y[i] - cy), 0ll)) f = false;
        }

        if (f) {
            cout << cx << " " << cy << " " << H << endl;
            return;
        }
    }
}

signed main(int argc, char *argv[]) {
    solver();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
    int N,M,C;
    cin >> N >> M >> C;
    vector<int> B(M);
    vector<vector<int>> A(N,vector<int>(M));
    for(int i=0;i<M;i++) cin >> B.at(i);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)cin >> A.at(i).at(j);
    }
    int count=0;
    for(int i=0;i<N;i++){
        int sum=0;
        for(int j=0;j<M;j++){
            sum+=A.at(i).at(j)*B.at(j);            
        }
        if(sum+C>0)count++;
    }
    cout << count << endl;

}

Measured memory_bytes: 256