akhauriyash/Code-Regression huggingface dataset:
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    set<int>s;
    rep(i,n)s.insert(a[i]);
    cout<<s.size()<<"\n";
}


Measured memory_bytes: 256
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys


@njit((i8[:], i8), cache=True)
def sum(tree, i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8, i8), cache=True)
def add(tree, size,  i, x):
    while i <= size:
        tree[i] += x
        i += i & -i


@njit((i8[:], i8, i8), cache=True)
def range_sum(tree, l, r):
    return sum(tree, r) - sum(tree, l)


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())

    bit = np.array([0] + sys.stdin.buffer.readline().split(), np.int64)
    for i in range(1, n+1):
        if i + (i & -i) < n + 1:
            bit[i + (i & -i)] += bit[i]

    for y in sys.stdin.buffer.readlines():
        q, p, x = map(int, y.split())
        if q:
            print(range_sum(bit, p, x))
        else:
            add(bit, n, p+1, x)


if __name__ == "__main__":
    main()


Measured memory_bytes: 148296
import sys
import os
a, b = map(int,input().split())
if a*b <= 0:
    print("Zero")
    sys.exit()
if a > 0 and b > 0:
    print("Positive")
    sys.exit()
if (b-a)%2==0:
    print("Negative")
else:
    print("Positive")


Measured memory_bytes: 2940
# coding: utf-8
# Here your code !

import math

def func():
    '''
    ?¨??????\???"minimum maximum number"(minimum, maximum, number????????¶??°)???????????????
    minimum ~ maximum???????????????????????????number????´???°????????°?????°??????
    '''

    try:
        numbers = [ int(item) for item in input().rstrip().split(" ")]  #??\???????????????????????????
    except:
        return inputError()

    (minimum, maximum, number) = (item for item in numbers)
    if(number<1):
        return inputError()

    count=0
    devs = devisor(number)  #?´???°?????????????±???????
    while(True):
        try:
            num=devs.pop()  #?´???°???????????????????´????1?????????
            if( (num >= minimum) and (num <= maximum) ):
                count+=1
        except: #devs???????´??????¨?????????????????????????????´???
            break
    
    print(count)

def devisor(num):
    '''
    num????´???°???????????¨????????????
    loop?????°??????num????´??????°????§£???????????????????????§????´???°?????????????¨???????????????????
    num???1?????????????????\??????????????´???????????????????????????
    ???????°???°???????????\??????????????´?????????int(num)??§??´??°???????????????????´???°????±???????
    '''
    
    result=set()
    if(num<1):
        return result

    num=int(num)
    for i in range(2,int(math.sqrt(num))+2):
        if(num % i == 0):                           #i???num????´???°?????´???
            subdevisor = devisor(num/i)        #num/i????´???°????±???????
            result.update(subdevisor)               #num/i????´???°???result?????????
            while(True):
                try:
                    result.add(i*subdevisor.pop())  #i??¨(num/i????´???°)?????????result?????????
                except:
                    break
            break
        elif(i==int(math.sqrt(num))+1):
            result.update({1,num})                  #num?????????????????§??§?´???°??????????????????????????°???1??¨num???result????????? (num????´???°)
    
    return result

def inputError():
    '''
    print("input Error")
    return -1
    '''

    print("input Error")
    return -1
    
func()

Measured memory_bytes: 7820
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w = inpl()
if h == 1 or w == 1:
    print(1)
    quit()
if h%2 and w%2:
    print(h*w//2+1)
else:
    print(h*w//2)

Measured memory_bytes: 66156
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
const int inf = 1e9 + 10;
const int maxN = 1005; 
int pos, p[2][maxN], a[maxN], N, tot, ans[maxN];
ll res[2];
void solve() {
	//for(int i = 1; i <= p[pos][0]; ++i) {
	//	cout << p[pos][i]<<' '<<a[p[pos][i]]<<"******"<<endl;
	//}
	for(int i = 1; i < p[pos][1]; ++i) ans[++tot] = 1;
	for(int i = N; i > p[pos][p[pos][0]]; --i) ans[++tot] = i - (p[pos][1] - 1);
	for(int i = 1; i < p[pos][0]; ++i) {
		int sz = (p[pos][i + 1] - p[pos][i]) / 2;
		for(int j = sz + 1; j > 1; --j) ans[++tot] = j;
	}
}
int main() {
	a[0] = -inf;
	int idx = 0;
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i) {
		scanf("%d", &a[i]);
		if(a[i] > a[idx]) idx = i;
	}
	if(a[idx] <= 0) {
		pos = 0; res[0] = a[idx];
		p[0][++p[0][0]] = idx;
	} else {
		for(int i = 1; i <= N; i += 2) 
			if(a[i] > 0) res[0] += a[i], p[0][++p[0][0]] = i;
		for(int i = 2; i <= N; i += 2)
			if(a[i] > 0) res[1] += a[i], p[1][++p[1][0]] = i;
		pos = (res[0] > res[1]) ? 0 : 1;
	}
	solve();
	printf("%lld\n%d\n", res[pos], tot);
	for(int i = 1; i <= tot; ++i) printf("%d\n", ans[i]);
	return 0;
}

Measured memory_bytes: 256
A,B,C,K=map(int,input().split())
ans=0
sub=K
if A>K:
    ans+=1*K
    sub-=K
else:
    ans+=1*A
    sub-=A
if sub!=0:
    if B>sub:
        sub=0
    else:
        sub-=B
if sub!=0:
    ans-=sub
print(ans)


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

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

  string s[100] = {};
  for(int i = 0; i < n; i++){
    cin >> s[i];
  }

  sort(s, s + n);
  string ans;
  for(int i = 0; i < n; i++){
    ans += s[i];
  }
  cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b,c;
    cin>>a>>b;
    c=a+b;
    int d;
    d=stoi(c);

    float e;
    e=(int)sqrt(d);
    if(e*e==d)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;



    return 0;
}


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

	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	// #ifndef ONLINE_JUDGE
 //    freopen("input.txt" , "r" , stdin);
	// freopen("output.txt" , "w" , stdout);
	// #endif

	int n,mx=0;
	cin>>n;
	vector<int>v[n+1];
	vector<pair<int,int>>v1;
	int m[n+1];
	map<pair<int,int>,int>mp;
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
		int k=max(v[a].size(),v[b].size());
		mx=max(mx,k);
		v1.push_back({a,b});
	}
	m[1]=0;
	queue<int>q;
	q.push(1);
	bool vis[n+1]={false};
	vis[1]=true;
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		int j=1;
		for(int i=0;i<v[p].size();i++)
		{
			if(!vis[v[p][i]])
			{
				if(m[p]==j)
					j++;
				if(j==mx+1)
					j=1;
				m[v[p][i]]=j;
				mp[{p,v[p][i]}]=j;
				vis[v[p][i]]=1;
				q.push(v[p][i]);
				j++;
			}
		}
	}
	cout<<mx<<endl;
	for(int i=0;i<n-1;i++)
	{
		int x=v1[i].first;
		int y=v1[i].second;
		if(mp[{x,y}]!=0)
			cout<<mp[{x,y}]<<endl;
		else
			cout<<mp[{y,x}]<<endl;
	}

	
	
}


Measured memory_bytes: 13560
import math
n, m = map(int, input().split())
x = abs(n-m)
r = 0
if x == 0:
  r = (math.factorial(n) * math.factorial(m)) * 2
elif x == 1:
  r = (math.factorial(n) * math.factorial(m))
else:
  r = 0
  
print(r % (10 ** 9 + 7))


Measured memory_bytes: 5184
#include <stdio.h>

int main() {
  int n, p, i, flag;
  int have[50];
  int turn;

  while(1) {
    scanf("%d %d", &n, &p);
    if(n == 0 && p == 0) break;

    for(i = 0; i < n; i++) {
      have[i] = 0;
    }
    turn = 0;
    flag = 0;
    while(1) {
      if(p == 0) {
	p += have[turn];
	have[turn] = 0;
      } else {
	have[turn]++;
	p--;
	if(p == 0) {
	  flag = 1;
	  for(i = 0; i < n; i++) {
	    if(i == turn) continue;
	    if(have[i] >= 1) {
	      flag = 0;
	      break;
	    }
	  }
	  if(flag) {
	    printf("%d\n", turn);
	    break;
	  }
	}
      }
      turn++;
      if(!(turn < n)) turn = 0;
    }
  }
  return 0;
}

Measured memory_bytes: 408
#!/snap/bin/pypy3

def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))

    dp = [False for _ in range(K + 1)]

    for i in range(K + 1):
        tmp_result = False
        for a in A:
            if i - a < 0:
                break
            elif not dp[i-a]:
                tmp_result = True
                break
        dp[i] = tmp_result

    print("First" if dp[-1] else "Second")


if __name__ == '__main__':
    main()


Measured memory_bytes: 45040
#include<stdio.h>

int use[11];
int count;
int dis[11][11];
int dp[20][20][11];
int x[11],y[11];

int mindis(int start){
  int i;
  int tmp,min;
  int flag;
  min = 0;
  flag =0;
  for(i=1;i<=count;i++){
    if(!use[i]){
      use[i] = 1;
      tmp = mindis(i) + dis[start][i];
      use[i] = 0;
      if(!min)min = tmp;
      else if(min > tmp)min = tmp;
      flag = 1;
    }
  }
  if(flag)return min;
  else return 0;
}

int main(void){
  char map[20][20];
  int i,j,k;
  int w,h;
  int min;
  int flag1,flag2;

  while(1){
    scanf("%d %d",&w,&h);
    if(!w && !h)break;

    count = 0;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	scanf(" %c ",&map[i][j]);
	if(map[i][j]=='o'){
	  x[0] = j;
	  y[0] = i;
	}
	else if(map[i][j]=='*'){
	  x[count+1] = j;
	  y[count+1] = i;
	  count++;
	} 
      }
    }

    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	for(k=0;k<=count;k++){
	  dp[i][j][k] = -1;
	}
      }
    }

    flag1 = 1;
    for(k=0;k<=count;k++){
      dp[y[k]][x[k]][k] = 0;

      flag2 = 1;
      while(flag2){

	flag2 = 0;
	for(i=0;i<h;i++){
	  for(j=0;j<w;j++){
	    if(dp[i][j][k]>=0){
	      
	      if(i+1<h && map[i+1][j]!='x'){
		if(dp[i+1][j][k]<0 || dp[i+1][j][k]>dp[i][j][k]+1){
		  dp[i+1][j][k] = dp[i][j][k] + 1;
		  flag2 = 1;
		}
	      }
	      if(j+1<w && map[i][j+1]!='x'){
		if(dp[i][j+1][k]<0 || dp[i][j+1][k]>dp[i][j][k]+1){
		  dp[i][j+1][k] = dp[i][j][k] + 1;
		  flag2 = 1;
		}
	      }
	      if(i-1>=0 && map[i-1][j]!='x'){
		if(dp[i-1][j][k]<0 || dp[i-1][j][k]>dp[i][j][k]+1){
		  dp[i-1][j][k] = dp[i][j][k] + 1;
		  flag2 = 1;
		}
	      }
	      if(j-1>=0 && map[i][j-1]!='x'){
		if(dp[i][j-1][k]<0 || dp[i][j-1][k]>dp[i][j][k]+1){
		  dp[i][j-1][k] = dp[i][j][k] + 1;
		  flag2 = 1;
		}
	      }
	    }
	  }
	}
      }
      if(!k){
	for(i=1;i<=count;i++){
	  if(dp[y[i]][x[i]][k] < 0)flag1 = 0;
	}
      }
    
      if(!flag1)break;

      for(i=0;i<=count;i++){
	if(i!=k)dis[k][i] = dp[y[i]][x[i]][k];
	else dis[k][i] = 0;
      }

    }

    if(!flag1){
      printf("-1\n");
    } else {
      for(i=1;i<=count;i++)use[i] = 0;
      use[0] = 1;
      min = mindis(0);
      printf("%d\n",min);
    }
  }
  return 0;
}

Measured memory_bytes: 436
using System;

namespace ABC133
{
    class B
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int D = int.Parse(input[1]);

            // 入力を二次元配列にすべて格納
            int[,] X = new int[N, D];
            for (int i = 0; i < N; i++)
            {
                input = Console.ReadLine().Split(' ');
                for (int d = 0; d < D; d++)
                {
                    X[i, d] = int.Parse(input[d]);
                    //Console.WriteLine("x" + "[" + i + d + "]" + " : " + X[i, d]);
                }
            }

            // 経路を計算
            //int[] Ans = new int[N];
            int count = 0;
            for (int i = 0; i < N - 1; i++)
            {
                for (int k = i + 1; k < N; k++)
                {
                    double ans = 0;
                    for (int d = 0; d < D; d++)
                    {
                        ans += Math.Pow(Math.Abs(X[i, d] - X[k, d]), 2);
                    }
                    ans = Math.Sqrt(ans);
                    //Console.WriteLine("ans : " + ans);
                    if ((int)ans == ans)
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
int c[10][10];
int C[10];
int a[10];
void solve(int n){
    a[0]=1;
    if(n==10){
        int tmp=0;
        for(int i=1;i<10;i++){
            tmp += c[a[i]][a[i-1]];
            C[a[i]]=min(C[a[i]],tmp);
        }
    }
    else{
        int cou[10];
        for(int i=0;i<10;i++)cou[i]=0;
        for(int i=0;i<n;i++)cou[a[i]]=1;
        for(int i=0;i<10;i++){
            if(cou[i]==0){
                a[n]=i;
                solve(n+1);
            }
        }
    }
}
int main(){
    int h,w;
    cin >> h >> w;
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++)cin >> c[i][j];
        C[i]=c[i][1];
    }
    solve(1);
    int x;
    int ans=0;
    for(int i=0;i<h;i++)for(int j=0;j<w;j++){
        cin >> x;
        if(x>1 || x==0)ans+=C[x];
    }
    cout << ans;
}

Measured memory_bytes: 3596
n, m = map(int, input().split())
heights = list(map(int, input().split()))

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

for i in range(m):
    a, b = map(int, input().split())
    neighbors[a - 1].append(b - 1)
    neighbors[b - 1].append(a - 1)

count = 0
for i in range(n):
    hanamaru = True
    for j in neighbors[i]:
        if heights[i] > heights[j]:
            continue
        else:
            hanamaru = False
            break
    if hanamaru is True:
        count += 1

print(count)


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<double, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;

template<typename T>
static inline void chmin(T & ref, const T  value) {
	if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
	if (ref < value) ref = value;
}

const ll mod = 1000000007;

int main() {
	ll n, q;
	cin >> n >> q;
	vector<ll> ss(n), ts(n), xs(n);
	vector<t3> qs;
	rep(i, n) {
		cin >> ss[i] >> ts[i] >> xs[i];
		qs.emplace_back(-xs[i] + ss[i] - 0.5, xs[i], 1);
		qs.emplace_back(-xs[i] + ts[i] - 0.5, xs[i], -1);
	}
	vector<ll> ds(q);
	rep(i, q) {
		cin >> ds[i];
		qs.emplace_back(ds[i], i, 0);
	}
	sort(qs.begin(), qs.end());
	set<ll> m;
	vector<ll> ans(q);
	for (auto p : qs) {
		double a;
		ll b, c;
		tie(a, b, c) = p;
		if (c == 0) {
			if (m.size()) {
				ans[b] = *m.begin();
			}
			else {
				ans[b] = -1;
			}
		}
		else if (c == 1) {
			m.insert(b);
		}
		else {
			m.erase(b);
		}
	}
	for (auto p : ans) {
		cout << p << endl;
	}
	return 0;
}


Measured memory_bytes: 34364
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n, a[200005];

int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	if(n % 2){
		for(int i = n; i >= 1; i -= 2)
			printf("%d ",a[i]);
		for(int i = 2; i <= n; i += 2)
			printf("%d ",a[i]);
	}
	else{
		for(int i = n; i >= 1; i -= 2)
			printf("%d ",a[i]);
		for(int i = 1; i <= n; i += 2)
			printf("%d ",a[i]);
	}
	printf("\n");
	return 0;
}
	

Measured memory_bytes: 2816
#include<stdio.h>
int main(void){
  int A,B,C,K;
  scanf("%d%d%d%d",&A,&B,&C,&K);
  if(A>=K){printf("%d\n",K);}
  else if(K<=A+B){printf("%d\n",A);}
  else if(K<=A+B+C){printf("%d\n",A-(K-A-B));}
  return 0;
}

Measured memory_bytes: 1732
def main():
    import sys
    from collections import defaultdict,deque
    sys.setrecursionlimit(10**5+2)

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(list)
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A].append(B)
        dic[B].append(A)
    
    L=[-1]*(N+1)
    R=[-1]*(N+1)


    d = deque()
    d.append((1,1))
    while len(d):
        now,count=d.popleft()
        for goto in dic[now]:
            if L[goto]==-1 or count<L[goto]:
                L[goto]=count
                R[goto]=now
                d.append((goto,count+1))

    if any(x+1 for x in R[2:]):
        print('Yes')
        for x in R[2:]:
            print(x)
    else:
        print('No')
    


main()

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

using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X, i) ((X>>i)&1)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define r_all(a) (a).rbegin(), (a).rend()
#define in(x) cin>>x
#define ina(x, n) rep(x_i,n) cin>>x[x_i]
#define outa(x, n) rep(x_i,n) cout<<x[x_i]<<" \n"[x_i==n-1]

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;
typedef priority_queue<ll> pq;

const int MOD = 1e9+7;
const int INF = (1<<30);
const ll INFL = (1L<<62);

int main() {
  int n; cin >> n;
  ll a, b;
  cin >> a >> b;
  rep(i,n-1) {
    ll A, B; cin >> A >> B;
    if (b*A == a*B) continue;
    if (a <= A && b <= B) {
      a = A; b = B;
      continue;
    }
    if (a >= A && b <= B) {
      if (a % A) a += A - (a % A);
      b = (a / A) * B;
      continue;
    }
    if (a <= A && b >= B) {
      if (b % B) b += B - (b % B);
      a = (b / B) * A;
      continue;
    }

    ll a1 = a, b1, a2, b2 = b;

    if (a % A) a1 += A - (a % A);
    b1 = (a1 / A) * B;

    if (b % B) b2 += B - (b % B);
    a2 = (b2 / B) * A;

    if (a1 < a || b1 < b) {
      a = a2; b = b2;
    } else if (a2 < a || b2 < b) {
      a = a1; b = b1;
    } else if (a1+b1 < a2+b2) {
      a = a1; b = b1;
    } else {
      a = a2; b = b2;
    }    
    // cout << "\t" << a << ", " << b << endl;
  }
  cout << a + b << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
const int MAX = 10000;
int main(void){
  int N;
  bool isPrime[10001];
  FOR(i,2,10001) isPrime[i]=true;
  for(int i=2; i<=10000; i++){
    if(isPrime[i]){
      for(int k=2; i*k<=10000; k++){
        isPrime[i*k]=false;
      }
    }
  }
  while(cin>>N){
    int count=0;
    for(int i=2; i<N; i++){
      if(isPrime[i]&&isPrime[N+1-i]){
        count++;
      }
    }
    cout<<count<<endl;
  }
  return 0;
}

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

ll solve(int N) {
    ll res = 0;
    ll a = 0, b = 0, both = 0;
    vector<string> A(N);
    rep(i,N) {
        string s; cin >> s;
        A.at(i) = s;
        int n = s.size();
        for (int j = 0; j < n-1; j++) {
            if (s[j] == 'A' && s[j+1] == 'B') res++, j++;
        }
        if (s[0] == 'B' && s[n-1] == 'A') both++;
        else if (s[0] == 'B') b++;
        else if (s[n-1] == 'A') a++;
    }
    if (a < b) {
        if (both >= b - a) a += b - a, both -= b - a;
        else a += both, both = 0;
    } else if (a > b) {
        if (both >= a - b) b += a - b, both -= a - b;
        else b += both, both = 0;
    }
    res += min(a,b);
    if (both >= 2) res += both / 2;
    return res;
}

ll solve2(int N) {
    vector<string> A(N);
    vector<int> a, b, ab;
    rep(i, N) {
        string S; cin >> S;
        A[i] = S;
        int e = S.size() - 1;
        if (S[0] == 'B' && S[e] == 'A') ab.push_back(i);
        else if (S[0] == 'B') b.push_back(i);
        else if (S[e] == 'A') a.push_back(i);
    }
    string T;
    set<int> used;
    if (a.size() > 0) {
        used.insert(a.back());
        T += A[a.back()]; a.pop_back();

    } 
    while (ab.size() > 0) {
        used.insert(ab.back());
        T += A[ab.back()]; ab.pop_back();
    }
    if (b.size() > 0) {
        used.insert(b.back());
        T += A[b.back()]; b.pop_back();
    }

    while (b.size() > 0 && a.size() > 0) {
        used.insert(a.back());
        used.insert(b.back());
        T += A[a.back()]; a.pop_back();
        T += A[b.back()]; b.pop_back();
    }

    rep(i,N) {
        if (used.count(i) == 0) T += A[i];
    }
    
    ll res = 0;
    for (int i = 0; i < T.size() - 1; i++) {
        if (T[i] == 'A' && T[i+1] == 'B') res++, i++;
    }
    return res;
}

int main() {
    int N; cin >> N;
    cout << solve2(N) << endl;
}


Measured memory_bytes: 4148
def main():
    s=input()
    a,b=-1,-1
    if len(s)==2:
        if s[0]==s[1]:
            a,b=1,2
    else:
        for i in range(len(s)-2):
            if s[i]==s[i+1] or s[i]==s[i+2]:
                a,b=i+1,i+3
                break
    print(a,b,sep=' ')

if __name__=='__main__':
    main()
        
    

                


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

int main() {
  int N, q = 0;
  cin >> N;
  
  for (int i = 0; i < N; i ++) {
    int A, p = 0;
    cin >> A;
    
    if (A%2 == 1)
      break;
    
    while (A%2 == 0) {
      p ++;
      A /= 2;
      if (A%2 == 1 || p == q)
        break;
    }
    
    q = p;
    
  }
  
  cout << q << endl;
}

Measured memory_bytes: 256
t = [int(input()) for i in range(5)] 
k = int(input())

c = t
have = False
for i in range(0,5):
    for j in range(0,5):
        if j != i:
            if abs(t[i] - c[j]) > k:
                have = True
    
if have:
    print(":(")
else:
    print("Yay!")

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pf(n) printf("%d\n",n)
#define pff(a,b) printf("%d  %d\n",a,b);
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1001001001;
const double PI = acos(-1);

int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];
	
	sort(a.begin(), a.end());
	ll sum = 0;
	rep(i, n) sum += a[i];
	//pf(sum);
	for (int i = n - 1; i >= 0; i--) {
		sum -= a[i];
		//pff(sum, a[i]);
		if (a[i] > sum * 2) {
			pf(n - i);
			return 0;
		}
	}


	return 0;
}

Measured memory_bytes: 4008
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define all(a) (a).begin(),(a).end()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define vecout(a) rep(i,a.size()){cout << a[i];cout << (i == a.size() - 1 ? "\n":" ");}
#define rep(i,x) for(int i = 0;i<x;i++)
#define REP(i,x) for(ll i = 1;i<=x;i++)
#define mp make_pair
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const dou pi = 3.14159265358;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
template<class T> inline bool change(T a,T b){if(a > b){swap(a,b);return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a / gcd(a,b) * b;
}

//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const ll cmax = 1000000;
ll fac[cmax], finv[cmax], inv[cmax];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < cmax; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logm)
ll modpow(ll n,ll m,ll MOD){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}
ll mypow(ll n,ll m){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n);
        m >>= 1;
        n *= n;
    }
    return res;
}

ll num(ll n){//10^n~10^1
    ll res = 0;
    rep(i,n){
        res += mypow(10,i);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> vec(N);
    vecin(vec);
    vector<ll> num;//広義単調増加で区切る
    ll cnt = 1;
    rep(i,N - 1){
        if(vec[i] <= vec[i + 1])cnt++;
        else{
            num.emplace_back(cnt);
            cnt = 1;
        }
    }
    if(cnt)num.emplace_back(cnt);
    //vecout(num);
    ll s = num.size();
    ll pos = 0,ans = 1000,kab = 0;
    rep(i,s){
        ll low = vec[pos],high = vec[pos + num[i] - 1];
        kab = ans / low;
        ans %= low;
        ans += kab * high;
        kab = 0;
        //cout << ans << "\n";
        pos += num[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<iterator>
#include<unordered_map>
#include<algorithm>
#include<cmath>

using namespace std;

int main(){
    int h,w,m;
    cin >> h >> w >> m;
    map<pair<int,int>,int> mp;
    vector<int> row(h,0);
    vector<int> col(w,0);
    int mx1 = 0, mx2 = 0;
    int rw=0,cl=0;
   
    for(int i = 0; i < m; ++i){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        mp[{a,b}]++;
        row[a]++;
        col[b]++;
        if(mx1 < row[a]){
            mx1 = row[a];
            rw = a;
        }
        if(mx2 < col[b]){
            mx2 = col[b];
            cl = b;
        }
    }
    int ans = 0;
    for(int i = 0; i < w; i++)
	{
	    if(mp[{rw,i}] == 0)
	        ans = max(ans, row[rw]+col[i]);
	    else
	        ans = max(ans, row[rw]+col[i]-1);
	}
	for(int i = 0; i < h; i++)
	{
	    if(mp[{i,cl}]==0)
	        ans = max(ans, row[i]+col[cl]);
	    else
	        ans = max(ans, row[i]+col[cl]-1);
	}
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 61840
# C - pushpush
def main():
    from collections import deque
    n = int(input())
    a = list(map(int, input().split()))
    ans = deque(maxlen=2*10**5)

    for i in range(n):
        if n % 2 == 0:
            if i % 2 == 0:
                ans.append(str(a[i]))
            else:
                ans.appendleft(str(a[i]))
        else:
            if i % 2 == 0:
                ans.appendleft(str(a[i]))
            else:
                ans.append(str(a[i]))

    else:
        print(' '.join(ans))


if __name__ ==  "__main__":
    main()

Measured memory_bytes: 38056
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            final int n = Integer.parseInt(br.readLine());
            if (n == 0) { break; }
            
            Map<String, Long> data = new LinkedHashMap<>();
            Map<String, Long> out = new HashMap<>();
            for (int i=1; i <= n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String e = st.nextToken();
                Long p = Long.parseLong(st.nextToken());
                Long q = Long.parseLong(st.nextToken());
                Long total = data.getOrDefault(e, 0L) + p * q;
                data.put(e, total);
                if (total >= 1_000_000L) {
                    if (out.putIfAbsent(e, total) == null) {
                        System.out.println(e);
                    }
                }
            }
            if (out.size() == 0) {
                System.out.println("NA");
            }
        }
    }
}

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

int main()
{
    int n,k;
    char s[50];
    cin>>n;
    cin.getline(s,50);
    cin.getline(s,50);
    cin>>k;
    char kk=s[k-1];
    int lens=strlen(s);
    for(int i=0;i<lens;i++)
        s[i]=(s[i]==kk?kk:'*');
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll a,b,c;
int main(){
	scanf("%lld%lld%lld",&a,&b,&c);
    printf("%lld",b+c-min(a,b+c));
}

Measured memory_bytes: 128
/*-------property of the half blood prince-----*/

#include <bits/stdc++.h>
#include <dirent.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define MIN(X,Y) X<Y?X:Y
#define MAX(X,Y) X>Y?X:Y
#define ISNUM(a) ('0'<=(a) && (a)<='9')
#define ISCAP(a) ('A'<=(a) && (a)<='Z')
#define ISSML(a) ('a'<=(a) && (a)<='z')
#define ISALP(a) (ISCAP(a) || ISSML(a))
#define MXX 10000000000
#define MNN -MXX
#define ISVALID(X,Y,N,M) ((X)>=1 && (X)<=(N) && (Y)>=1 && (Y)<=(M))
#define LLI long long int
#define VI vector<int>
#define VLLI vector<long long int>
#define MII map<int,int>
#define SI set<int>
#define PB push_back
#define MSI map<string,int>
#define PII pair<int,int>
#define PLLI pair<LLI,LLI>
#define PDD pair<double,double>
#define FREP(i,I,N) for(int (i)=(int)(I);(i)<=(int)(N);(i)++)
#define eps 0.0000000001
#define RFREP(i,N,I) for(int (i)=(int)(N);(i)>=(int)(I);(i)--)
#define SORTV(VEC) sort(VEC.begin(),VEC.end())
#define SORTVCMP(VEC,cmp) sort(VEC.begin(),VEC.end(),cmp)
#define REVV(VEC) reverse(VEC.begin(),VEC.end())
#define INRANGED(val,l,r) (((l)<(val) || fabs((val)-(l))<eps) && ((val)<(r) || fabs((val)-(r))<eps))
#define INRANGEI(val,l,r) ((val)>=(l) && (val)<=(r))
#define MSET(a,b) memset(a,b,sizeof(a))
using namespace std;
using namespace __gnu_pbds;

//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction


//typedef tree < int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

int main(){
    int l1,r1,l2,r2;
    cin>>l1>>r1>>l2>>r2;
    int mnn = min(l1,l2);
    int mxx = max(r1,r2);
    int cnt = 0;
    FREP(i,mnn,mxx){
        if(INRANGEI(i,l1,r1) && INRANGEI(i,l2,r2))cnt++;
    }
    cnt--;
    cout<<max(0,cnt)<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc,char **argv)
{
  int n;
  float x;
  char u[4];
  int ix;
  float sum = 0.0;
  
  scanf("%d",&n);
  for( ix = 0; ix < n; ix++ ){
    scanf("%f %s",&x,u);
    if( strstr(u,"JPY") ){
      sum += x;
    }
    else if( strstr(u,"BTC") ){
      sum += x * 380000.0;
    }
  }
  printf("%f\n",sum);
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()

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

int n,t[102];
double ans,dp[40005],v[102];

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

	REP(i,40005) dp[i]=INF;

	cin>>n;
	REP(i,n) cin>>t[i+1];
	REP(i,n) cin>>v[i+1];
	int tm=0;
	REP(i,n+2) {
		t[i]*=2;
		FOR(j,tm,tm+t[i]+1) {
			dp[j]=min(dp[j],v[i]);
		}
		tm+=t[i];
	}
	FOR(i,1,tm+1) {
		dp[i]=min(dp[i],dp[i-1]+0.5);
	}
	for(int i=tm-1;i>=0;i--) {
		dp[i]=min(dp[i],dp[i+1]+0.5);
	}
	REP(i,tm) {
		ans+=(dp[i]+dp[i+1])*0.25;
	}
	printf("%.10f\n",ans);

	return 0;
}


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

int main(){
	int x1,y1,x2,y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << x2 -( y2 - y1) << endl;
	cout <<y2 + x2-x1 <<endl;
cout <<	x1 - y2 + y1 <<endl;
cout << y1 + x2 - x1  << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;

    map<ll, ll> mp;
    rep(i, n) {
        ll a;
        cin >> a;
        mp[a]++;
    }

    vl v;
    for(auto p : mp) {
        if(p.second >= 4) {
            rep(i, 2) {
                v.pb(p.first);
            }
        }
        else if(p.second >= 2) {
            v.pb(p.first);
        }
    }
    sort(rall(v));
    
    if(v.size() < 2) {
        out(0);
        re0;
    }

    out(v[0]*v[1]);
    re0;
}

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

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    vector<int> P(N);
    for (int i=0; i<N; i++) {
        cin >> S[i] >> P[i];
    }
    
    
    
    for (int i=0; i<N; i++) {
        string st_mem = S[0];
        int mem = 0;
        
        for (int i=0; i<N; i++) {
            if (S[i] < st_mem) {
                st_mem = S[i];
                mem = i;
                continue;
            }
            if (S[i] == st_mem) {
                if (P[i] > P[mem]) {
                    st_mem = S[i];
                    mem = i;
                }
            }
        }
        
        cout << mem + 1 << endl;
        S[mem] = "zzzzzzzzzz";
    }
    
    
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <map>
#include<cmath>
#include <queue>
#include <numeric>
#include <cassert>
#include<map>
#include<bitset>

using lli = long long int;
lli inf = 1000000007;
using namespace std;


void solve() {
	int N, K;
	cin >> N >> K;
	// 100 1 = 100
	// 100 2 = 100

	lli ans = 0;
	lli min = 0;
	lli max = 0;
	for (int i = 0; i < K; i++) {
		max += (N - i);
		max %= inf;
		min += i;
		min %= inf;
	}

	// cout << min << " " << max << endl;

	for (int i = 0; i <= (N + 1 - K); i++) {
		ans += (max - min + inf + 1);
		ans %= inf;
		max += (N - K - i) + inf;
		max %= inf;
		min += (K + i);
		min %= inf;
	}
	cout << ans << endl;
}

int main()
{
	solve();
	return 0;
}

Measured memory_bytes: 3592
#include<stdio.h>
int main()
{
   int x,y;
   scanf("%d%d", &x, &y);

   if((x==4||x==6||x==9||x==11)&&(y==4||y==6||y==9||y==11)){
        printf("Yes\n");
   }
   else if((x==1 || x==3 || x==5 || x==7 || x==8 || x==10 || x==12)&&(y==1 || y==3 || y==5 || y==7 || y==8 || y==10 || y==12)){
        printf("Yes");
   }
   else
    printf("No\n");

    return 0;

}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ff              first
#define ss              second
#define int             long long int
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define vv(type)		vector<vector<type>>
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define db(x) 			cout<<x<<" "
#define db1(x) 			cout<<x<<'\n'
#define db2(x,y) 		cout<<x<<" "<<y<<'\n'
#define db3(x,y,z) 		cout<<x<<" "<<y<<" "<<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)
#define so(a) 			sort(a.begin(),a.end())
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
// to find all local maximaa and minima in O(n)
//	 for (int i=1;i<=n;i++)
//        {
//            if (i==1 || i==n || (p[i-1]<p[i])!=(p[i]<p[i+1]))
//           ans.push_back(p[i]);
//        }
int dx[] = { -1, 1, -1, 0, 0, -1, 1, 1 };
int dy[] = { -1, -1, 1, -1, 1, 0, 0, 1 };
int gcd(int a, int b)
{
	if (!b)
		return a;
	return gcd(b, a % b);
}
int modular_expo(int x, int y, int m)
{
	int ans = 1;
	while (y)
	{
		if (y & 1)
			ans = (ans % m * x % m) % m;
		x = (x % m * x % m) % m;
		y /= 2;
	}
	return ans % m ;
}
int power(int x, int y)
{
	int ans = 1;
	while (y)
	{
		if (y & 1)
			ans = (ans * x);
		x *= x;
		y /= 2;
	}
	return ans;
}
void solve()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, w, v = 0;
	cin >> n >> w;
	vector<vector<int>>item(n, vector<int>(2));
	rep(i, n)
	{
		cin >> item[i][1] >> item[i][0];
		v += item[i][0];
	}
	vector<vector<int>>dp(n + 1, vector<int>(v + 1, 0));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= v; j++)
		{
			if (i == 1)
				dp[i][j] = INT_MAX;
			else
			{
				dp[i][j] = dp[i - 1][j];
				if (j >= item[i - 1][0])
					dp[i][j] = min(dp[i][j], item[i - 1][1] + dp[i - 1][j - item[i - 1][0]]);
			}
		}
		if (i == 1)
		{
			dp[i][0] = 0;
			dp[i][item[i - 1][0]] = item[i - 1][1];
		}
	}
	int ans = 0;
	rep(i, v + 1)
	if (dp[n][i] <= w)
		ans = i;
	db1(ans);
}

int32_t main()
{
	solve();
	return 0;
}


Measured memory_bytes: 83132
#include<cstdio>
#include<cstring>
#define mod 1000000007
#define maxn 1005
#define LL long long
int n,m,lr,ud,v,ev,eh;
LL k;
char s[maxn][maxn];
int powmod(int a,LL n)
{
	int res=1;
	while(n)
	{
		if(n&1ll) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		n>>=1ll;
	}
	return res;
}
void swap(int &a,int &b) { int t=a; a=b; b=t; }
struct mat { int a[2][2]; };
mat operator * (mat a,mat b)
{
	mat c;
	memset(c.a,0,sizeof(c.a));
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;
	return c;
}
mat operator ^ (mat a,LL n)
{
	mat res;
	memset(res.a,0,sizeof(res.a));
	res.a[0][0]=res.a[1][1]=1;
	while(n)
	{
		if(n&1ll) res=res*a;
		a=a*a;
		n>>=1ll;
	}
	return res;
}
int main()
{
	scanf("%d%d%lld",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='#') { v++,ev+=(s[i-1][j]=='#'),eh+=(s[i][j-1]=='#'); }
	for(int i=1;i<=n;i++) lr+=(s[i][1]=='#'&&s[i][m]=='#');
	for(int i=1;i<=m;i++) ud+=(s[1][i]=='#'&&s[n][i]=='#');
	if(ud&&lr) { printf("1\n"); return 0; }
	if(!ud&&!lr) { printf("%d\n",powmod(v,k-1)); return 0; }
	if(lr) { swap(ud,lr); swap(ev,eh); swap(n,m); }
	mat ans,tmp;
	ans.a[0][0]=ans.a[0][1]=ans.a[1][1]=0,ans.a[1][0]=1;
	tmp.a[0][0]=ud,tmp.a[0][1]=ev,tmp.a[1][0]=0,tmp.a[1][1]=v;
	ans=(tmp^(k-1))*ans;
	printf("%d\n",(ans.a[1][0]-ans.a[0][0]+mod)%mod);
}

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

int main() {
  int weight_a, weight_b, weight_c, weight_d;
  scanf("%d %d %d %d", &weight_a, &weight_b, &weight_c, &weight_d);
  if(weight_a + weight_b > weight_c + weight_d) {
    printf("Left\n");
  } else if(weight_a + weight_b < weight_c + weight_d) {
    printf("Right\n");
  } else {
    printf("Balanced\n");
  }
  return 0;
}


Measured memory_bytes: 128
N = int(input())
P = [int(x) for x in input().split()]
L = [0] * (N + 2)
R = [N + 1] * (N + 2)
I = list(range(N + 1))
for i in range(N):
  I[P[i]] = i
ans = 0
ST = [0] * (N + 2)
def cnt(i):
  ret = 0
  while i:
    ret += ST[i]
    i -= i & (-i)
  return ret
def update(i):
  while i <= N + 1:
    ST[i] += 1
    i += i & (-i)
def ls(idx):
  b = cnt(idx)
  if b == 0:
    return 0
  s = 0
  t = idx
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) < b:
      s = m
    else:
      t = m
  return t
def rs(idx):
  b = cnt(idx)
  s = idx
  t = N + 1
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) > b:
      t = m
    else:
      s = m
  return t
for i in range(N, 0, -1):
  index = I[i]
  idx = index + 1
  L[idx] = ls(idx)
  R[idx] = rs(idx)
  L[R[idx]] = idx
  R[L[idx]] = idx
  update(idx)
  ans += i * ((idx - L[idx]) * (R[R[idx]] - R[idx]) + (L[idx] - L[L[idx]]) * (R[idx] - idx))
print(ans)

Measured memory_bytes: 57420
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;

int main(){
	string s;
	string t="keyence";
	cin>>s;
	if(s==t){
		cout<<"YES"<<endl;
		return 0;
	}
	for(int i=0;i<s.size();i++){
		for(int j=i;j<s.size();j++){
			string u;
			for(int k=0;k<s.size();k++){
				if(!(k>=i&&k<=j))u.push_back(s[k]);
			}
			if(u==t){
				cout<<"YES"<<endl;
				return 0;
			}
		}	
	}
	cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

ll phi(ll n) {
    ll sum = n;
    ll k = n;
    for (ll i = 2; i * i <= n; i++) {
        if (k % i == 0) {
            sum = (sum / i) * (i - 1);
        }
        while (k % i == 0) {
            k = k / i;
        }
    }
    if (k > 1) {
        sum = (sum / k) * (k - 1); 
    }
    return sum;  
}

int main() {
    ll n;
    cin >> n;
    cout << phi(n) << endl;
}

Measured memory_bytes: 3116
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <bitset>
#include <numeric>
#include <math.h>
#include <tuple>
#include <queue>
#include <set>

using namespace std;

long long gcd(long long a, long long b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

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

    int N;

    cin >> N;

    vector<long long> A(N);

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

    vector<long long> L(N);
    vector<long long> R(N);

    L[0] = A[0];
    R[N-1] = A[N-1];

    for(int i = 1; i < N; i++){
        L[i] = gcd(L[i-1], A[i]);
        R[N-i-1] = gcd(R[N-i], A[N-i-1]);
    }

    vector<long long> gcd_1left(N);
    gcd_1left[0] = R[1];
    gcd_1left[N-1] = L[N-2];

    for(int i = 1; i < N-1; i++){
        gcd_1left[i] = gcd(L[i-1], R[i+1]);
    }
    
    cout << *max_element(gcd_1left.begin(), gcd_1left.end()) << endl;

    return 0;
}


Measured memory_bytes: 3456
n, m = map(int, input().split())
L = []
R = []

for i in range(m):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)

left = max(L)
right = min(R)
ans = right - left + 1
print(ans if ans >= 0 else 0)

Measured memory_bytes: 10996
# while True:
#     cnt = 0
#     n, x = map(int, input().split())

#     if n == 0 and x == 0:
#         break
#     else:
#         for i in range(n):
#             for j in range(n):
#                 if i == j:
#                     continue
#                 else:
#                     for k in range(n):
#                         if i == j and j == k:
#                             continue
#                         else:
#                             if i + j + k == x:
#                                 cnt += 1

#     print("{}".format(cnt))


# 間違い
# square1001の回答が一番近い
# 範囲をめっちゃ間違えてた

while True:
    cnt = 0
    n, x = map(int, input().split())

    if n == 0 and x == 0:
        break
    else:
        for i in range(1, n + 1):
            for j in range(1, i):
                for k in range(1, j):
                    if i + j + k == x:
                        cnt += 1
    print("{}".format(cnt))



Measured memory_bytes: 5596
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
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;
}

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

    int W, H, x, y;
    cin >> W >> H >> x >> y;

    std::cout << setprecision(10) << (double)W * H / 2 << ' ';
    if (2 * x == W && 2 * y == H) {
        std::cout << 1 << '\n';
    } else {
        std::cout << 0 << '\n';
    }

    return 0;
}

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

int main() {
    int n, x;
    cin >> n >> x;
    
    if (x == 1 || x == 2*n-1) {
        cout << "No" << endl;
        return 0;
    }
    
    cout << "Yes" << endl;
    if (n == 2) {
        cout << "1\n2\n3\n";
        return 0;
    }
    
    int center[4];
    if (x == 2) {
        center[0] = 4;
        iota(center+1, center+4, 1);
    } else {
        iota(center, center+3, x-1);
        center[3] = x-2;
    }
    
    vector<int> ans(2*n-1);
    
    int c = 1;
    for (int i = 1; i <= 2*n-1; i++) {
        if (i >= n-1 && i <= n+2) continue;
        while (count(center, center+4, c)) c++;
        ans[i-1] = c;
        c++;
    }
    copy(center, center+4, ans.begin()+n-2);
    
    for (auto e: ans) cout << e << endl;

    
    return 0;
}


Measured memory_bytes: 2304