akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8
#N, m, d = map(int,input().split())
#N = int(input())
s = input()
#s = list(map(str,input().split()))
#a, b = map(int,input().split())
#P = list(map(int,input().split()))
w = int(input())
ans = ""
if w==1:
    ans = s
else:
    for i in range(len(s)):
        if (i+1)%w==1:
            ans += s[i]
    
print(ans)

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

int main(){
  string S, T, U;
  int A, B;
  
  cin >> S >> T ;
  cin >> A >> B ;
  cin >> U;
  
  if (S == U) {
    --A;
  } else {
    --B;
  }
  
  cout << A << " " << B << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<P ,ll> P3;
typedef pair<P ,P> PP;
const ll MOD = ll(1e9)+7;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-6;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int main() {
    ll n, k;
    double ans = 0.0;
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        ll cnt = 0, m=i;
        while(m < k){
            m *= 2;
            cnt++;
        }
        double a = 2.0, tmp = 1.0;
        while(cnt > 0){
            if(cnt&1LL){
                tmp /= a;
            }
            a *= a;
            cnt >>= 1;
        }
        ans += tmp/n;
    }
    printf("%.12lf\n",ans);
    return 0;
}

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

int main() {
    int n,l;
    cin >> n >> l;
    int taste = 0;
    for (int i = 0; i < n; i++) {
        taste += l + i;
    }
    if (l <= 0 && l+n-1 >= 0) {
        cout << taste << endl;
    }
    else if (l > 0) {
        cout << taste - l << endl;
    }
    else cout << taste - (l+n-1) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int abs(int a){
  if(a<0){
    return (-1)*a;
  }else{
    return a;
  }
}
int gcd(int a, int b)
{
    long long int c;
    if (a < b) {
        a+=b; b=a-b; a-=b;
    }
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
int main(){
  int n,start;
  scanf("%d%d",&n,&start);
  int x[n];
  int i;
  for(i=0;i<n;i++){
    scanf("%d",&x[i]);
  }
  int ans = abs(x[0] - start);

  for(i=1;i<n;i++){
    if(ans==0){
      ans=abs(x[i]-x[i-1]);
    }
    ans = gcd(ans,abs(x[i]-x[i-1]));
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

const int CN = 210;

class fs{
  public: int to,nxt;
    void init(int t,int n) {to = t;nxt = n;}
}E[CN * CN];
int hd[CN],ecnt = 0;
void add(int x,int y) {E[++ecnt].init(y,hd[x]);hd[x] = ecnt;}

int n,ans = -1,ind[CN];

int dep[CN]; queue<int> Q;
int bfs(int s){
    memset(dep,0,sizeof(dep)); 
    Q.push(s); dep[s] = 1;
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        for(int k = hd[u];k;k=E[k].nxt){
            int v = E[k].to;
            if(dep[v] == dep[u]) return -1;
            if(!dep[v]) dep[v] = dep[u] + 1,Q.push(v);
        }
    }
    int mx = 0;
    for(int i=1;i<=n;i++) mx = max(mx, dep[i]);
    return mx;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            char c; cin>>c;
            if(c == '1') add(i,j),ind[j]++;
        }

    int mn = 0x3f3f3f3f;
    for(int i=1;i<=n;i++) mn = min(mn, ind[i]);
    for(int st=1;st<=n;st++) ans = max(ans, bfs(st));
    printf("%d",ans);

    return 0;
}

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

int main(){
	int N;
	cin >> N;
	vector<int> A(N,0);
	vector<int> B(N-1);
	for(auto &i:B)cin >> i;
	int ans=0;
	for(int i=0;i<N;i++){
		if(i==0)A[i]=B[i];
		else if(i==N-1)A[i]=B[N-2];
		else A[i]=min(B[i-1],B[i]);
	}
	cout << accumulate(A.begin(),A.end(),0) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int expr(string& s, int& i);
int term(string& s, int& i);
int fact(string& s, int& i);
int invt(string& s, int& i);
int bina(string& s, int& i);

int expr1(string &s, int& i){
  int val = expr(s, i);
  while(s[i]=='-'&&s[i+1]=='>'){
    i+=2;
    int x = expr(s, i);
    if(val&&!x) val = 0;
    else val = 1;
  }
  return val;
}

int expr(string &s, int &i){
  int val = term(s, i);
  while(s[i]=='+'){
    i++;
    val |= term(s, i);
  }
  return val;
}

int term(string& s, int& i){
  int val = fact(s, i);
  while(s[i]=='*'){
    i++;
    int x = fact(s, i);
    val &= x;
  }
  return val;
}

int invt(string& s, int& i){
  if(isdigit(s[i])) return fact(s, i);
  while(s[i]=='-'){
    i++;
    int x = fact(s, i);
    return !x;
  }
}

int fact(string& s, int& i){
  if(s[i]=='-') return invt(s, i);
  if(isdigit(s[i])) return bina(s, i);
  i++;
  int ret = expr1(s,i);
  i++;
  return ret;
}

int bina(string& s, int& i){
  return s[i++]-'0';
}

int C(string S, string T){
  //  cout << S << " " << T << endl;
  rep(i,(1<<11)-1){
    string s,t; s = S; t = T;
    rep(j, s.size()){
      if(s[j] < 'a' || s[j] > 'k') continue;
      s[j] = ((i>>(s[j]-'a'))&1)+'0';
    }
    rep(j, t.size()){
      if(t[j] < 'a' || t[j] > 'k') continue;
      t[j] = ((i>>(t[j]-'a'))&1)+'0';
    }
    //    cout << s << " " << t << endl;
    int p = 0, q = 0;
    if(expr(s, p) != expr(t,q)) return 0;
  }
  return 1;
}

int main(){
  string S;
  while(cin >> S, S != "#"){
    int pos;
    rep(i,S.size()){
      if(S[i]=='T') S[i] = '1';
      if(S[i]=='F') S[i] = '0';
      if(S[i]=='=') pos = i;
    }
    cout << (C(S.substr(0,pos), S.substr(pos+1))?"YES":"NO") << endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <vector>

using namespace std;

class range {
private:
  struct Iterator {
    int val;
    int operator*() {return val;}
    bool operator!=(Iterator &itr) {return val < itr.val;}
    void operator++() {++val;}
  };
  Iterator i, n;
public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  Iterator &begin() {return i;}
  Iterator &end() {return n;}
};

template<class T> T at(vector<T> v, int i) {return v[(i % (int)v.size() + v.size()) % v.size()];}

long long a[100000];
long long aa[20][100000];

int main() {
  int n;
  long long m, c;
  cin >> n >> m >> c;
  for (int i : range(n)) cin >> a[i];
  for (int i : range(n)) aa[0][i] = a[i];
  for (int i : range(19)) {
    int p = 1 << i;
    for (int j : range(n)) {
      aa[i + 1][j] = aa[i][j];
      int dis = min(j + p, n - 1) - j;
      aa[i + 1][j] = max(aa[i + 1][j], aa[i][j + dis] - c * dis);
      dis = j - max(j - p, 0);
      aa[i + 1][j] = max(aa[i + 1][j], aa[i][j - dis] - c * dis);
    }
  }
  int low = 0, high = n + 1;
  while (low + 1 < high) {
    int mid = (low + high) / 2;
    long long sum = 0;
    for (int k : range(n)) {
      long long mx = 0;
      for (int i : range(20)) {
        if (mid & 1 << i) {
          int dis = min(k + (mid & -1 << (i + 1)), n - 1) - k;
          mx = max(mx, aa[i][k + dis] - c * dis);
          dis = k - max(k - (mid & -1 << (i + 1)), 0);
          mx = max(mx, aa[i][k - dis] - c * dis);
        }
      }
      sum += mx;
    }
    if (sum >= m) high = mid;
    else low = mid;
  }
  if (low == n) cout << -1 << endl;
  else cout << low << endl;
}


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

int a,b,k=1,num;

int main(){
	cin>>a>>b;
	num=b;
	while(num){
		num/=10;k*=10;
	}
	a=a*k+b;
	for(int i=3;i<=320;++i)
		if(i*i==a){
			printf("Yes");
			return 0;
		}
	printf("No");
	
	return 0;
}

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

int main(void){
    double x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << fixed << setprecision(9) << sqrt(pow((x2 - x1), 2) + pow((y2 - y1),2)) << endl;
    return 0;
}



Measured memory_bytes: 3272
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
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;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	template<class C>
	int minLeft(int a,int b,C &check,Monoid x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l||!check(dat[k],x))return -1;
		if(r-l==1)return l;
		int lv=minLeft(a,b,check,x,k*2+1,l,(l+r)/2);
		if(lv!=-1)return lv;
		return minLeft(a,b,check,x,k*2+2,(l+r)/2,r);
	}
	template<class C>
	int maxRight(int a,int b,C &check,Monoid x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l||!check(dat[k],x))return -1;
		if(r-l==1)return l;
		int rv=maxRight(a,b,check,x,k*2+2,(l+r)/2,r);
		if(rv!=-1)return rv;
		return maxRight(a,b,check,x,k*2+1,l,(l+r)/2);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};

int N,Q;
auto f=[](int a,int b){return max(a,b);};
auto g=[](int a,int b,int sz){return b;};
auto h=[](int a,int b){return b;};
auto check=[](int a,int b){return b<=a;};
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>Q;
	Segtree<int,int,decltype(f),decltype(g),decltype(h)>segtree(N,f,g,h,-1,-1);
	rep(i,N){
		int a;cin>>a;segtree.set(i,a);
	}
	segtree.init();
	while(Q--){
		int t;cin>>t;
		if(t==1){
			int x,v;cin>>x>>v;x--;
			segtree.update(x,x+1,v);
		}else if(t==2){
			int l,r;cin>>l>>r;l--;
			cout<<segtree.query(l,r)<<"\n";
		}else {
			int x,v;cin>>x>>v;x--;
			int res=segtree.minLeft(x,N,check,v);
			if(res==-1)res=N;
			cout<<res+1<<"\n";
		}
	}
}

Measured memory_bytes: 11408
n = int(input())
robo = [0] * n
for i in range(n):
    x, l = map(int, input().split())
    robo[i] = (x - l, x + l)
robo.sort(key=lambda x: x[1])

max_r, cnt = -float('inf'), 0
for l, r in robo:
    if  max_r <= l:
        cnt += 1
        max_r = r
print(cnt)

Measured memory_bytes: 18216
import java.util.*;
import java.util.stream.*;
import java.util.function.*;

public class Main {
    public static void main(String[] args) throws Exception {
        System.out.println(new Main().solve());
    }
    
    // パラメタ渡しもちゃんとクラス作るのも面倒なので手抜き
    // 必要な値はここで全部取ってしまう
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    {sc.nextLine();}
    int[] a = IntStream.range(0, n).map(i -> Integer.parseInt(sc.next())).toArray();
    // // ソートしておく
    // List<Integer> a = IntStream.range(0, n)
    //                             .map(i -> Integer.parseInt(sc.next()))
    //                             .sorted()
    //                             .boxed().collect(Collectors.toList());
    
    int solve() {
        
        // a の最大公約数を求める
        int gcd = a[0];
        for(int i = 1; i < n; i++) {
            gcd = gcd(gcd, a[i]);
        }
        
        
        // 嘘くさい
        return gcd;
    }
    
    static int gcd(int a, int b) {
        int tmp;
        while(true) {
            tmp = a % b;
            if(tmp == 0) {
                return b;
            }
            a = b;
            b = tmp;
        }
    }
}




Measured memory_bytes: 49240
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int p,q,n,a;

int ans;
int rec(int sum_u, int sum_l, int nn, int k){
  if( sum_l > a || nn==0 )
    return -1;

  if( sum_u * q == sum_l * p ){
    ans++;
    return 0;
  }
  if( p/double(q) < sum_u/double(sum_l) )
    return 0;

  nn--;
  for(int x=k;;x++ ){
    if( rec(sum_u*x+sum_l, sum_l*x, nn, x) < 0 )
      break;
  }
  return 0;
}

int main(){
  while( cin>>p>>q>>a>>n,p){
    ans=0;
    rec(0, 1, n+1, 1);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTG(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define ENDL cout << endl;
using namespace std;
using ll = long long;
using ld = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VI = vector<int>;
using VVI = vector<VI>;
using Vll = vector<ll>;
using VVll = vector<Vll>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  VI p(N);
  INPUT(p);
  int ans = 0;
  REP(i, N)
  {
    if (p[i]-1 == i)
    {
      ans++;
      int tmp = p[i];
      p[i] = p[i+1];
      p[i+1] = tmp;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 640
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

	static int[][] d;
	static final int INF = Integer.MAX_VALUE/2;

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		while (true) {

			int n = Integer.parseInt(scan.next());
			int k = Integer.parseInt(scan.next());
			if(n==0) break;
			d = new int[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					d[i][j] = i == j ? 0 : INF;
				}
			}

			for (int i = 0; i < k; i++) {
				int f = Integer.parseInt(scan.next());
				if (f == 0) {
					int a = Integer.parseInt(scan.next()) - 1, b = Integer
							.parseInt(scan.next()) - 1;
					out.println(d[a][b] == INF ? -1 : d[a][b]);
				} else {
					int a = Integer.parseInt(scan.next()) - 1, b = Integer
							.parseInt(scan.next()) - 1, cost = Integer
							.parseInt(scan.next());
					d[a][b] = d[b][a] = Math.min(d[a][b], cost);

					for(int e : new int[]{a,b}){
						for (int j2 = 0; j2 < n; j2++) {
							for (int l = 0; l < n; l++) {
								d[j2][l] = Math.min(d[j2][l], d[j2][e] + d[e][l]);
							}
						}
					}

				}
			}
		}
		out.flush();
	}
}

Measured memory_bytes: 38472
#include<iostream>
#include<vector>
using namespace std;
#define Max 1000

int main() {
    vector<int> v[Max];
    int q, n;
    cin >> n >> q;
    int num, qst, x;
    for (int i = 0; i < q; i++) {
        cin >> qst >> num;
        if (qst == 0) {
            cin >> x;
            v[num].push_back(x);
        } else if (qst == 1) {
            for (int i = 0; i < v[num].size(); i++) {
                if (i) cout << " ";
                cout << v[num][i];
            }
            cout << endl;
        } else {
            v[num].clear();
        }
    }
    return 0;
}



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

int main()
{
  int n;
  while (cin >> n) {
    for (int i = 0; i < n; ++i) {
      double xa, ya, ra, xb, yb, rb;
      cin >> xa >> ya >> ra >> xb >> yb >> rb;
      
      double d = sqrt((xa-xb)*(xa-xb) + (ya-yb)*(ya-yb));
      
      if (d > ra+rb)
	cout << "0" << endl;
      else if (d+ra < rb)
	cout << "-2" << endl;
      else if (d+rb < ra)
	cout << "2" << endl;
      else
	cout << "1" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

bool solve(vector< vector<int> > G){
  int n = G.size();
  for(int k = 0; k < n; ++k){
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
      }
    }
  }
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      if(G[i][j] == INF)
        return true;
  return false;
}

int main(){
  int N, M;
  cin >> N >> M;
  vector< vector<int> > G(N,vector<int>(N,INF));
  vector<int> A(M), B(M);
  for(int i = 0; i < M; ++i){
    cin >> A[i] >> B[i];
    --A[i];
    --B[i];
    G[A[i]][B[i]] = 1;
    G[B[i]][A[i]] = 1;
  }
  for(int i = 0; i < N; ++i) G[i][i] = 0;
  int ans = 0;
  for(int i = 0; i < M; ++i){
    G[A[i]][B[i]] = INF;
    G[B[i]][A[i]] = INF;
    if(solve(G)) ++ans;
    G[A[i]][B[i]] = 1;
    G[B[i]][A[i]] = 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;

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


int main() {
    int n, m;
    int sum = 0;
    cin >> n >> m;
    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
        sum += a[i];
    }
    double b = (double)sum / (4.0 * (double)m);
    int c = 0;
    rep(i, n) {
        if ((double)a[i] < b) ++c;
    }
    cout << (((n - c) >= m ? "Yes" : "No")) << endl;
    return 0;
}



Measured memory_bytes: 256
#include "iostream"
#include "vector"
using namespace std;

int main()
{
    int N, M;  cin >> N >> M;
    int count[ M ] = {0};

    for( int i=0 ; i<N ; i++ )
    {
        int K;
        cin >> K;

        for( int j=0 ; j<K ; j++ )
        {
            int temp; cin >> temp;
            count[ temp-1 ]++;
        }
    }

    int counter=0;

    for( int i=0 ; i<M ; i++ )
    {
        if( count[i] == N ) counter++;
    }

    cout << counter << endl;

    return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    #[allow(unused_mut)]
    let mut s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

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

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

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

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

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

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

fn main() {
  input!{
    n: usize,
    capacity: i64,
    items: [(i64, usize); n]
  }
  let mut dp = vec![vec![1_000_000_000_000_000_000i64; 100_001]; 2];
  dp[0][0] = 0;
  for (idx, item) in items.iter().enumerate() {
    for value in 0..100_001 {
      dp[(idx + 1) % 2][value] = dp[idx % 2][value];
      if item.1 <= value {
        dp[(idx + 1) % 2][value] = cmp::min(dp[(idx + 1) % 2][value], dp[idx % 2][value - item.1] + item.0);
      }
    }
  }
  let ans = dp[n % 2].iter().enumerate().rev().filter(|&(_, w)| *w <= capacity).next().unwrap().0;
  println!("{}", ans)
}


Measured memory_bytes: 6396
n,k,q = map(int,input().split())
a_list=[int(input()) for _ in range(q)]

import collections
c = collections.Counter(a_list)

for i in range(n):
    num=i+1
    count = c[num]
    minus = q-count
    if k - minus > 0:
        print('Yes')
    else:
        print('No')

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

using ll=long long; 

void solve(){
	int a,b,k;
	cin>>a>>b>>k;
	for(int i=a; i<=b; i++){
		if(i>=b-k+1 || i<=a+k-1){
			cout<<i<<endl;
		}
	}
}

signed main(){
	//while(1)
	solve();
}

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

using namespace std;

int main() {
  long n;
  long ans = 0;
  cin >> n;
  vector<long> b;

  for (long i=1; i<=n; i++) {
    long a; cin>>a;
    b.push_back(a-i);
  }

  sort(b.begin(), b.end());
  long B = ((n&1)? b[n/2] : (b[n/2-1]+b[n/2])/2);
  ans = accumulate(b.begin(),b.end(),0L,
    [&](long acc, long i) {return acc + abs(i-B);});
  cout << ans << endl;

}


Measured memory_bytes: 2420
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> P;

int main()
{
	int N, M;
	int a, b;
	vector<P> e;
	vector<int> v;
	int count = 0;
	bool flag = false;

	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		e.push_back(P(a, b));
	}

	for (int i = 1; i <= N; i++)
	{
		v.push_back(i);
	}

	do
	{
		if (v.front() == 1)
		{
			vector<int> v_t;
			v_t = v;
			while (true)
			{
				flag = false;
				for (int i = 0; i < (int)e.size(); i++)
				{
					if (v_t[0] == e[i].first && v_t[1] == e[i].second)
					{
						v_t.erase(v_t.begin());
						flag = true;
						break;
					}
					else if (v_t[1] == e[i].first && v_t[0] == e[i].second)
					{
						v_t.erase(v_t.begin());
						flag = true;
						break;
					}
				}
				if (!flag)
					break;

				if (v_t.size() == 1)
				{
					count++;
					break;
				}
			}
		}
	} while (next_permutation(v.begin(), v.end()));

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pil;
typedef complex<double> xy_t;

const lint mod = 1e9 + 7;

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int a[n][m], b[m][n];
    rep(i, n)rep(j, m){
        scanf("%d", &a[i][j]);
        --a[i][j];
        b[a[i][j]][i] = j;
    }
    set<pii> s[n];
    rep(i, n)rep(j, m) s[i].insert(pii(j, a[i][j]));

    int num[m], tmp = 0, ans;
    rep(i, m) num[i] = 0;
    rep(i, n) ++num[a[i][0]];
    rep(i, m) tmp = max(tmp, num[i]);
    ans = tmp;

    rep(i, m-1){
        rep(j, m)if(num[j] == tmp){
            rep(k, m) num[k] = 0;
            rep(k, n){
                s[k].erase(pii(b[j][k], j));
                ++num[(*(s[k].begin())).se];
            }
            tmp = 0;
            rep(k, m) tmp = max(tmp, num[k]);
            ans = min(ans, tmp);
            break;
        }
    }

    printf("%d\n", ans);
}

Measured memory_bytes: 5120
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl
#define show2(a, n, m) rep(i, n) { rep(j, m) {cout << a[i][j] << ' ';} cout << endl;} 
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef long double ld;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

struct mint {
	ll x;
	mint(ll x=0):x((x%MOD+MOD)%MOD){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {if ((x+=a.x)>=MOD) x-=MOD; return *this;}
	mint& operator-=(const mint a) {if ((x+=MOD-a.x)>=MOD) x-=MOD; return *this;}
	mint& operator*=(const mint a) {(x*=a.x)%=MOD; return *this;}
	mint operator+(const mint a) const {mint res(*this); return res+=a;}
	mint operator-(const mint a) const {mint res(*this); return res-=a;}
	mint operator*(const mint a) const {mint res(*this); return res*=a;}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
 		return a;
	}

	// For prime mod.
	// Do not use if MOD is not prime number !!
	mint inv() const { return pow(MOD-2);}
	mint& operator/=(const mint a) { return (*this) *= a.inv();}
	mint operator/(const mint a) const {mint res(*this); return res/=a;}
};

typedef vector<mint> vm;
typedef vector<vm> vvm;
int main() {
//	cout << fixed << setprecision(15);
    string k;
    int d;
    cin >> k >> d;
    vector<vvm> dp(k.size() + 1, vvm(2, vm(d))); // digit, smaller, remainder
    dp[0][0][0] = 1;
    rep(i, k.size()) rep(j, 2) rep(l, d) {
        int c = k[i] - '0';
        for(int m = 0; m <= (j ? 9 : c); m++) {
            dp[i + 1][j || (m < c)][(l + m) % d] += dp[i][j][l];
        }
    }
    mint ans = dp[k.size()][1][0] + dp[k.size()][0][0];
    ans -= 1;
    cout << ans.x << endl;
}


Measured memory_bytes: 17024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const long long INF = 1e18;
# define len(x) ((int)(x).size())
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define foreps(i, m, n) for(int i = m;i < n;i++)
# define ALL(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
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; }

ld N, K;

ll solve(ll n) {
    ll nn = n, cnt = 0;;
    while(nn < K) nn *= 2, cnt++;
    return cnt;
}

int main() {
    cin >> N >> K;
    ld Dice = 1 / N, Coin = 0.5;

    ld ans = 0.0;
    reps(i, N) {
        ans += Dice * pow(Coin, solve(i));
    }
    cout << fixed << setprecision(12) << ans << endl;
}

Measured memory_bytes: 3880
#include <bits/stdc++.h>
using namespace std;
static const int MAX = 1000000;

int f(int num) {
  if (num % 2 == 0) {
    return num / 2;
  } else {
    return 3 * num + 1;
  }
}

int main() {
  int s;
  cin >> s;
  vector<int> a(MAX);
  for (int i = 1; i <= MAX; i++) {
    if (i == 1) {
      a[i] = s;
      continue;
    }
    a[i] = f(a[i - 1]);
  }
  for (int i = 1; i <= MAX; i++) {
    for (int j = i + 1; j <= MAX; j++) {
      if (a[i] == a[j]) {
        cout << j << endl;
        return 0;
      }
    }
  }
  cout << 0 << endl;
}

Measured memory_bytes: 4096
function main(input) {
  input=input.trim();
  const a = input.split(" ")[0];
  const b = input.split(" ")[1];
  var tsunagi=Number(a+b);
  if(Number.isInteger(Math.pow(tsunagi,0.5))==true){
    console.log("Yes");
  }else{
    console.log("No");
  }

}



main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 9420
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <cassert>
#include <iomanip>

using namespace std;

#define pb push_back
typedef long long ll;
typedef complex<int> P;
typedef pair<int, int> Pii;

const int MAX = 200 ;

int a[MAX][MAX];
P dd[] = {P(1,0), P(1,1), P(0,1), P(-1,0), P(-1,-1), P(0,-1)};


int dfs(P p, int k){
	if(a[p.real() + MAX/2][p.imag() + MAX/2] == -2) return 0;
	if(k <= a[p.real() + MAX/2][p.imag() + MAX/2]) return 0;

	int res = 0;
	if(a[p.real() + MAX/2][p.imag() + MAX/2] == -1) res++;
	a[p.real() + MAX/2][p.imag() + MAX/2] = k;
	for(int i=0;i<6;i++){
		res += dfs(p + dd[i], k-1);
	}
	return res;
}

bool solve(){
	int t, n;
	cin>> t>> n;
	if(t==0 && n==0) return false;
	
	memset(a, -1, sizeof(a));
	for(int i=0;i<n;i++){
		int x, y;
		cin>> x>> y;
		a[x + MAX/2][y + MAX/2] = -2;
	}
	P p;
	cin>> p.real()>> p.imag();
	int ans = dfs(p, t);
	cout<< ans<< endl;
	
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	
	while(solve());

	return 0;
}

 

Measured memory_bytes: 1324
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 1500

int F[MAX][MAX];
int h,w;

int ans[MAX][MAX];
int dp();

int main(){
    cin >> h >> w;
    for(int i = 0; i < h; i++){
        F[i][0] = F[i][w+1] = 1;
        ans[i][0] = ans[i][w+1] = INT_MIN;
    }
    for(int i = 0; i < w; i++){
        F[0][i] = F[h+1][i] = 1;
        ans[0][i] = ans[h+1][i] = INT_MIN;
    }

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> F[i][j];
        }
    }

    int a = dp();

    cout << a << endl;

    return 0;
}

int dp(){
    int ma = INT_MIN;

    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(F[i][j] == 1){
                ans[i][j] = 0;
            }else{
                int mi = min(ans[i-1][j], min(ans[i][j-1], ans[i-1][j-1]));
                if(mi == INT_MIN) ans[i][j] = 1;
                else ans[i][j] = mi+1;
            }
            
            ma = max(ma, ans[i][j]);
        }
    }

    return ma*ma;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  string s;
  cin>>s;
  int cnt = 0;
  char cur = 'A';
  REP(i,s.size()){
    char to = s[i];
    do{
      if(cur=='Z'){
        cnt++;
        cur = 'A';
      }else{
        cur++;
      }
    }while(to != cur);
  }
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 3148
#include<iostream>
#include <cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

////Nayeem Shahriar Joy,Applied Physics &Electronic Engineering,University of Rajshahi.

int main()

{
    bool prime[1000001];
    memset(prime,true,sizeof(prime));
    for( int i=4;i<=999999;i=i+2)
    {
        prime[i]=false;
    }
    for(int i=3;i*i<=999999;i++)
    {
        if(prime[i]==true){
        for(int j=i*2;j<=999999;j=j+i)
        {
            prime[j]=false;
        }
        }
    }
    int n;

    while(cin>>n)
    {
        int count=0;
        for( int i=2;i<=n;i++)
        {
            if(prime[i]==true)
            {
                count++;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

Measured memory_bytes: 4020
#ABC170 D
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()

if a[0] == a[-1]: # n=1 やサンプル２のような時
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1: #１だけは素因数分解するときにバグるので別で処理
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct): # 約数のリストつくるやつ
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n): #素因数分解
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct): # 約数の集合を作る
      c.add(num(div))

# 積集合をとり、それが空でかつ同じ数字が並んでない時に答えを加算
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i) #今まで見た数の集合を更新

print(ans)

Measured memory_bytes: 124392
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#define shosu(x) fixed<<setprecision(x)
using namespace std;

int n,w,inf=-1,wei[105],val[105],dp[10005];

int func(){
	for(int i=0;i<n;i++){
		for(int j=w;j>=wei[i];j--){
			dp[j]=max(dp[j],dp[j-wei[i]]+val[i]);
		}
	}
	return dp[w];
}

int main(){
	cin>>n>>w;
	for(int i=0;i<n;i++){
		cin>>val[i]>>wei[i];
	}
	cout<<func()<<endl;
}

Measured memory_bytes: 1200
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define pi pair<int, int>

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int x, y;
	cin >> x >> y;
	
	int ret = 0;
	
	ret += max(0, (4 - x) * 100000);
	ret += max(0, (4 - y) * 100000);
	ret += max(0, (3 - x - y) * 400000);
	
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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


  int n;
  cin >> n;
  ll a[n];
  ll ans=0;
  rep(i,n) {
    cin >> a[i];
    while(a[i]%2==0){
      a[i]/=2;
      ans++;
    }
  }


  cout << ans << endl;
  //  cout << endl << endl;
  //  cout << static_cast<double>(clock()) / CLOCKS_PER_SEC << "s"<<endl;
  return 0;


}


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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 512;

vector<int> v[N];

void solve() {
  int n, m, q; scanf("%d%d%d", &n, &m, &q);
  for (int l, r, i = 0; i < m; ++i) {
    scanf("%d%d", &l, &r);
    v[l].push_back(r);
  }
  for (int i = 1; i <= n; ++i) {
    if (v[i].empty()) continue;
    sort(v[i].begin(), v[i].end());
  }
  for (int l, r, i = 0; i < q; ++i) {
    scanf("%d %d", &l, &r);
    int ans = 0;
    for (; l <= r; ++l) {
      if (v[l].empty()) continue;
      ans += upper_bound(v[l].begin(), v[l].end(), r) - v[l].begin();
    }
    printf("%d\n", ans);
  }
}

int main() {
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 5204
/// Swift5 -> Swift2.2

extension String {
    // split(separator:maxSplits:omittingEmptySubsequences:)
    func split(separator separator: Character) -> [String] {
        return self.characters.split(separator).map(String.init)
    }
}
extension Array {
    // init(repeating:count:)
    init(repeating: Element, count: Int) {
        self.init(count: count, repeatedValue: repeating)
    }
}
extension Array where Element: Comparable {
    // sorted()
    func sorted() -> [Element] {
        return self.sort( { $0 < $1 } )
    }
}
// stride(from:through:by:)
func stride(from start: Int, through end: Int, by stride: Int) -> StrideThrough<Int> {
    return start.stride(through: end, by: stride)
}
// stride(from:to:by)
func stride(from start: Int, to end: Int, by stride: Int) -> StrideTo<Int> {
    return start.stride(to: end, by: stride)
}
extension Range {
    func reversed() -> [Element] {
        return self.reverse()
    }
}

/// end

let input = readLine()!.split(separator: " ").map { Int($0)! }
let N = input[0]
let W = input[1]

var dp = Array(repeating: 0, count: W + 1)

for _ in 0 ..< N {
    let knapsack = readLine()!.split(separator: " ").map { Int($0)! }
    let weight = knapsack[0]
    let value = knapsack[1]

  	let tmp = (weight ... W).reverse()
    for i in stride(from: W, through: weight, by: -1) {
        dp[i] = max(dp[i], dp[i - weight] + value)
    }
}

print(dp.last!)


Measured memory_bytes: 4208
#include <bits/stdc++.h>
#include <vector>
#define rep(i,n) for(int i = 0; i < n; i++)
using ll = long long;
using namespace std;
int main(){
  int x,a,b;
  cin >> x >> a >> b;
  if(abs(x - a) > abs(x - b)){
    cout << "B" << endl;
  }else{
    cout << "A" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <map>
#include <utility>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<pair<string, pair<int, int>>> vc;
    pair<string, pair<int, int>> p;
    pair<int,int> pp;
    int n,b;
    string a;
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> a >> b;
        pp.first = -b;
        pp.second = i+1;
        vc.push_back(pair<string, pair<int,int>>(a,pp));
    }
    
    sort(vc.begin(), vc.end());
    
    for(int i=0; i<n; i++){
        p = vc[i];
        pp=p.second;
        cout << pp.second;
        //cout << p.second << " " <<  p.first;
        cout << endl;
    }
    
}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/


Measured memory_bytes: 256
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
import bisect
def main():
    N = I()
    X = LI()
    Ans_list = []
    for i in range(1, 101):
        cnt = 0
        for x in X:
            cnt += (x - i) ** 2
        Ans_list.append(cnt)
    print(min(Ans_list))

if __name__ == "__main__":
    main()


Measured memory_bytes: 74680
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}

func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}

func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n, m, c := iScan(), iScan(), iScan()
	b := iSScan(m)
	ans := 0
	for i := 0; i < n; i++ {
		x := c
		for j := 0; j < m; j++ {
			x += iScan() * b[j]
		}
		if x > 0 {
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1776
#include <stdio.h>

int main() {
  char s[11], ans[11]="";
  scanf("%s", s);

  int i, j;
  for (i=0, j=0; s[i]!='\0'; i++) {
    if (s[i]=='0') ans[j++]='0';
    else if (s[i]=='1') ans[j++]='1';
    else {
      if (j) ans[j--]='\0';
    }
  }
  ans[j]='\0';

  printf("%s\n", ans);
  return 0;
}

Measured memory_bytes: 128
import sys
input = sys.stdin.readline

def count(P):
    res = 0
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(N+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return


    Pi = [None]*N
    for i in range(N):
        Pi[P[i]] = i
    for i in range(N):
        p = Pi[i]
        res += i-BIT_query(p+1)
        BIT_update(p+1, 1)
    return res
 

N = int(input())
A = tuple(map(int,input().split()))
B = tuple(map(int,input().split()))
uhalf = -(-N//2)
dhalf = N - uhalf
inf = 10**9+7
ans = inf
for S in range(1<<N):
    card = [A[i] if S&(1<<i) else B[i] for i in range(N)]
    parity = [(1&(S>>i))^(i&1) for i in range(N)]
    even = [(card[i], i) for i in range(N) if parity[i]]
    odd = [(card[i], i) for i in range(N) if not parity[i]]
    if len(even) != uhalf or len(odd) != dhalf:
        continue
    even.sort()
    odd.sort()
    if any(e[0] > o[0] for e, o in zip(even, odd)) or any(e[0] < o[0] for e, o in zip(even[1:], odd)):
        continue
    perm = [even[i//2][1] if not i&1 else odd[i//2][1] for i in range(N)]
    ans = min(ans, count(perm))
print(ans if ans < inf else -1)


Measured memory_bytes: 65416
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
//                       _oo0oo_                         //
//                      o8888888o                        //
//                      88" . "88      ------ hzt1       //
//                      (| -_- |)                        //
//                      0\  =  /0                        //
//                    ___/`---'\___                      //
//                  .' \|     |// '.                     //
//                 / \|||  :  |||// \                    //
//                / _||||| -:- |||||- \                  //
//               |   | \  -  /// |     |                 //
//               | \_|  ''\---/''  |_/ |                 //
//               \  .-\__  '-'  ___/-. /                 //
//             ___'. .'  /--.--\  `. .'___               //
//          ."" '<  `.___\_<|>_/___.' >' "".             //
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |           //
//         \  \ `_.   \_ __\ /__ _/   .-` /  /           //
//     =====`-.____`.___ \_____/___.-`___.-'=====        //
//                       `=---='                         //
//                                                       //
//                                                       //
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~       //
//                                                       //
//                 God-He Bless All.                     //
//           This Code Will Never Explode.               //
//                                                       //
//                                                       //
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
typedef long long ll;
const int maxn=200010;
int n,k,cur;
deque<int> A;
void work() {
	int x=A.front();A.pop_front();
	if(x^cur) A.push_front(cur);
	else cur^=1,A.push_back(cur^1);
}
void force(int k) {
	while(k--) work();
	rep(i,0,n-1) {
		int x=A.front();A.pop_front();
		putchar(x^cur?'A':'B');
	}
}
char s[maxn];
int main() {
	scanf("%d%d%s",&n,&k,s);
	rep(i,0,n-1) A.push_back(s[i]=='A');
	if(k>=2*n) k=2*n+(k-2*n)%2;
	force(k);
	return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<string>
#include<vector>

using namespace std;

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

  vector<long> number;
  long temp;
  for(int i=0; i<num; ++i){
    cin >> temp;
    number.push_back(temp);
  }

  long sum = 0;
  for(auto v:number){
    sum += v;
  }

  if(sum % 2 ==1){ cout << "NO" << endl;
                 }else{
    cout << "YES" << endl;
  }
}

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

void solve(int a, int b){
  if(a == 0) return;

  int total = 0, m;
  for(int i=1; i<=b; i++){
    total += i;
    if(total >= a){
      m = i; break;
    }
  }

  cout << m << endl;
  solve(a-m, m-1);
  return;
}

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

  solve(N, N);
}
  
  

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main()
{
	char a[105];
	int n;
	cin>>a>>n;
	int i;
	for(i=0;i<n;i++)
		if(a[i]=='1') continue;
		else{
			cout<<a[i]<<endl;
			break;
		}
	if(i==n) cout<<"1"<<endl;
	return 0;	
}


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

int main() {
  string A,X,C;
  cin >> A >> X >> C;
  
  string a;
  char x,c;
  a = 'A';
  x = X.at(0);
  c = 'C';
  
  cout <<  a + x + c << endl;
}


Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = pow(k // i, n, M)
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    
# print(sum((i)*nums[i]%M for i in range(len(nums)))%M)
print((np.arange(k+1) * nums).sum()%M)

Measured memory_bytes: 28632