akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;

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;
};

vector<int> divisor(int n) {
  vector<int> ret;
  for(int i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  return (ret);
};

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

  vector<int> divisors = divisor(M);

  sort(All(divisors));
  reverse(All(divisors));

  rep(i, 0, divisors.size()) {
    int gcd = divisors[i];
    int m = M / gcd;
    if (m >= N) {
      cout << gcd << endl;
      break;
    }
  }

  return 0;
};


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

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

  vector<int> ans(n);
  
  //該当する上司番号を入力値分だけカウントアップ
  rep(i,n-1) {
    int a;
    cin >> a;
    ans[a-1]++;
  }
  
  //集計結果を表示
  for (int x : ans) {
    cout << x << endl;
  }
}


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

int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n;
    cin >> n;
    int a[n],x=0,b[60]={0};
    for(int i=0;i<n;i++){
        cin >> a[i];
        x^=a[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<60;j++){
            if(((1ll<<j)&x) and ((1ll<<j)&a[i]))
                a[i]^=(1ll<<j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=59;j>=0;j--){
            if((1ll<<j)&a[i]){
                if(!b[j])b[j]=a[i];
                a[i]^=b[j];
            }
        }
    }
    int k=0;
    for(int i=59;i>=0;i--){
        k=max(k,k^b[i]);
    }
    cout << k+(x^k);
}

Measured memory_bytes: 4436
#include <cstdio>
#include <algorithm>
#include <utility>

int main()
{
  int n;
  using pair = std::pair<long long, long long>;
  pair crd[50];
  scanf("%d", &n);
  if (n == 1)
  {
    puts("1");
    return 0;
  }
  for (int i = 0; i < n; ++i)
  {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    crd[i] = pair{x, y};
  }
  std::sort(crd, crd + n);
  int ans = 1e9;
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      if (i == j || crd[j].first < crd[i].first) continue;
      if (crd[j].first == crd[i].second && crd[j].second < crd[i].second) continue;
      auto p = crd[j].first - crd[i].first;
      auto q = crd[j].second - crd[i].second;
      int cnt = 0;
      for (long long b = 0; b != (1LL << n) - 1;)
      {
        pair last;
        for (int i = 0; i < n; ++i)
        {
          if ((b >> i) & 1) continue;
          ++cnt;
          b |= 1LL << i;
          last = crd[i];
          break;
        }
        for (int i = 0; i < n; ++i)
        {
          if ((b >> i) & 1) continue;
          if (last.first + p == crd[i].first && last.second + q == crd[i].second)
          {
            b |= 1LL << i;
            last = crd[i];
          }
        }
      }
      if (ans > cnt) ans = cnt;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include <string> 

using namespace std;
typedef long long Int;
#define INF (1LL<<60)

int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}
int pow(int e, int b);

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

	string S;
	cin >> S;
	
	int a,b,c,d;
	a=ctoi(S[0]);
	b=ctoi(S[1]);
	c=ctoi(S[2]);
	d=ctoi(S[3]);

	string S1,S2,S3,S0;
	S0 = S[0]; 
	S1 = S[1]; 
	S2 = S[2]; 
	S3 = S[3]; 
	string ans;
	if(a+b+c+d==7) ans=S0+"+"+S1+"+"+S2+"+"+S3+"=7";
	if(a+b+c-d==7) ans=S0+"+"+S1+"+"+S2+"-"+S3+"=7";
	if(a+b-c+d==7) ans=S0+"+"+S1+"-"+S2+"+"+S3+"=7";
	if(a+b-c-d==7) ans=S0+"+"+S1+"-"+S2+"-"+S3+"=7";
	if(a-b+c+d==7) ans=S0+"-"+S1+"+"+S2+"+"+S3+"=7";
	if(a-b+c-d==7) ans=S0+"-"+S1+"+"+S2+"-"+S3+"=7";
	if(a-b-c+d==7) ans=S0+"-"+S1+"-"+S2+"+"+S3+"=7";
	if(a-b-c-d==7) ans=S0+"-"+S1+"-"+S2+"-"+S3+"=7";
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
using namespace std;
const int N = 2e5 + 5;
vector<int> G[N] = {};
int val[N] = {};
int n;
stack<int> ls[N];
int ans[N] = {};
bool ha[N] = {};
int t = 0;
int bs(int x) {
    int l = 1, r = t, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (ls[mid].top() < x)
            l = mid + 1;
        else r = mid - 1;
    }
    return l;
}
void dfs(int u, int f) {
    int idx = bs(val[u]);
    if (val[u] < ls[idx].top()) {
        ha[u] = true;
        ls[idx].emplace(val[u]);
        t = max(idx, t);
    }
    ans[u] = t;
    for (const int &v : G[u])
        if (v != f) dfs(v, u);
    if (ha[u]) {
        ls[idx].pop();
        if (ls[idx].top() == INF)
            t--;
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    ls[0].emplace(0);
    for (int i = 1; i <= n; i++)
        ls[i].emplace(INF);
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
    return 0;
}


Measured memory_bytes: 165136
import java.util.*;

public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] ints=new int[n];
        for(int i=0;i<n;i++){
            ints[i]=i;
        }
        int q=scanner.nextInt();
        for(int i=0;i<q;i++){
            int com=scanner.nextInt();
            int x=scanner.nextInt();
            int y=scanner.nextInt();
            int keyX=ints[x];
            int keyY=ints[y];
            if(com==0){
                for(int j=0;j<n;j++){
                    if(ints[j]==keyY) ints[j]=keyX;
                }
            }else{
                if(keyX==keyY){
                    System.out.println(1);
                }else{
                    System.out.println(0);
                }

            }
        }
    }
}



Measured memory_bytes: 70748
#include <stdio.h>
int main(){

  int n,a,result,i,j;

  while(1){

    scanf("%d",&n);
    if(n == 0) break;

    result=0;
    if(n == 1){

      printf("1\n");
      continue;

    }

    for(i = n+1; i <= 2*n; i++){

      a=0;
      for(j = 2; j*j <= i; j++){

        if(i%j == 0){

	  a=1;
          break;

        }

      }

      if(a == 0) result++;

    }

    printf("%d\n",result);

  }

  return 0;

}

Measured memory_bytes: 612
#include <stdio.h>
int main(void){
    double r,s,l;
    double PI = 3.141592653589;
    scanf("%lf",&r);
    
    s = r*r*PI;
    l = 2*r*PI;
    
    printf("%f %f\n",s,l);
    return 0;
}



Measured memory_bytes: 2756
N = int(input())
diff_a_b = []
for i in range(N):
  a, b = map(int, input().split())
  diff_a_b.append([a - b, a, b])

diff_a_b.sort()
if diff_a_b[0][0] == 0: # 最初から数列が等しい
  print(0)
  quit()

ans = 0
d = 0
temp = 10**10
for diff, a, b in diff_a_b:
  if diff <= 0: # a <= b
    ans += b
    d -= diff
  else:
    ans += b
    temp = min(temp, b)

print(ans - temp)

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

int main() {
  long A;
  char b1,b_,b2,b3;
  cin>>A>>b1>>b_>>b2>>b3;
  long B1=long(b1-'0')*100;
  long B2=long(b2-'0')*10;
  long B3=long(b3-'0');
  long B=B1+B2+B3;

  cout<<A*B/100<<endl;
}


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

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

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

using namespace std;

int main() {
	int r, d, x;
	cin >> r >> d >> x;

	int ans[10 + 1];
	ans[0] = x;

	for (int i = 1; i <= 10; i++) {
		ans[i] = r * ans[i - 1] - d;
	}

	for (int i = 1; i <= 10; i++) {
		cout << ans[i] << endl;
	}

	return 0;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5;
int m, k;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> m >> k;
  if(bit(m) <= k || m==1&&k==1){
    cout << -1 << endl;
    return 0;
  }
  if(m==1){
    cout << "0 0 1 1" << endl;
    return 0;
  }
  FOR(i, 0, bit(m)) if(i!=k) cout << i << " ";
  cout << k << " ";
  FORR(i, bit(m)-1, 0) if(i!=k) cout << i << " ";
  cout << k << endl;
}

Measured memory_bytes: 1792
import std.stdio, std.conv, std.string;
import std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

int DEBUG_LEVEL = 0;
void print()(){ writeln(""); }
void print(T, A ...)(T t, lazy A a){ write(t), print(a); }
void print(int level, T, A ...)(T t, lazy A a){ if(level <= DEBUG_LEVEL) print(t, a); }

void main(string[] args){
	if(args.length > 1 && args[1] == "-debug"){
		if(args.length > 2 && args[2].isNumeric) DEBUG_LEVEL = args[2].to!int;
		else DEBUG_LEVEL = 1;
	}
	
	int n = read.to!int;
	int m = read.to!int;
	
	long[] as;
	foreach(i; 0 .. n) as ~= read.to!long;
	
	int[] bs;
	long[] cs;
	foreach(j; 0 .. m) bs ~= read.to!int, cs ~= read.to!long;
	
	int[long] xc;
	foreach(a; as){
		if(a !in xc) xc[a] = 0;
		xc[a] += 1;
	}
	
	foreach(i; 0 .. m){
		int b = bs[i];
		long c = cs[i];
		if(c !in xc) xc[c] = 0;
		xc[c] += b;
	}
	
	long[] ks = xc.keys;
	ks.sort!"a>b"();
	
	long ans;
	foreach(k; ks){
		if(xc[k] <= n){
			ans += k * xc[k];
			n -= xc[k];
			continue;
		}
		else{
			ans += k * n;
			n = 0;
			break;
		}
	}
	
	ans.writeln;
	
}



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

void main_()
{
    ll N, M;
    cin >> N >> M;

    vector<ll> edge_num(N);

    for (ll i = 0; i < M;++i) {
        ll a, b;
        cin >> a >> b;
        edge_num[a - 1]++;
        edge_num[b - 1]++;
    }

    bool yes = all_of(begin(edge_num), end(edge_num), [](auto n) { return n % 2 == 0; });

    cout << (yes ? "YES\n" : "NO\n");
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

class Node {
	int id, left, right;
	int parent = -1;
	int sibling = -1;	// ???????????°
	int degree;			// ????????°
	int depth;
	int height;

	public Node(int id) {
		this.id = id;
	}

	@Override
	public String toString() {

		String type;
		if(this.parent == -1) {
			type = "root";
		} else if (this.degree == 0) {
			type = "leaf";
		} else {
			type = "internal node";
		}

		String str =
				String.format(
						"node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s",
						this.id, this.parent, this.sibling, this.degree, this.depth, this.height, type);
		return str;
	}
}

class Main {

	static int treeDepth = 0;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		Node[] bTree = new Node[n];

		for (int i = 0; i < n; i++) {
			bTree[i] = new Node(i);
		}

		for (int i = 0; i < n; i++) {
			int now = sc.nextInt();
			int left = sc.nextInt();
			int right = sc.nextInt();

			bTree[now].left = left;
			bTree[now].right = right;

			int deg = 0;
			if (left != -1) {
				deg++;
				bTree[left].parent = now;
			}
			if (right != -1) {
				deg++;
				bTree[right].parent = now;
			}
			if (left != -1 && right != -1) {
				bTree[left].sibling = right;
				bTree[right].sibling = left;
			}

			bTree[now].degree = deg;

		}
		sc.close();

		int root = -1;
		for(Node node : bTree) {
			if (node.parent == -1) {
				root = node.id;
				break;
			}
		}

		bTree[root].depth = 0;
		setDepth(root, bTree);
		setHeight(root, bTree);

		for (Node node : bTree) {
			System.out.println(node);
		}

	}

	private static void setHeight(int id, Node[] bTree) {
		int h1 = 0;
		int h2 = 0;

		Node now = bTree[id];

		if (now.left != -1) {
			setHeight(now.left, bTree);
			h1 = bTree[now.left].height + 1;
		}
		if (now.right != -1) {
			setHeight(now.right, bTree);
			h2 = bTree[now.right].height + 1;
		}

		now.height = Math.max(h1, h2);
	}

	private static void setDepth(int id, Node[] bTree) {
		Node now = bTree[id];

		if (now.left != -1) {
			bTree[now.left].depth = now.depth + 1;
			setDepth(now.left, bTree);
		}
		if (now.right != -1) {
			bTree[now.right].depth = now.depth + 1;
			setDepth(now.right, bTree);
		}

		treeDepth = Math.max(treeDepth, now.depth);
	}
}

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

int main() {
  int a, b;
  cin >> a >> b;

  if (a*b % 2 == 0) {
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
  // ここにプログラムを追記
}

Measured memory_bytes: 3640
#include <stdio.h>
#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

//降順
int des(const void *a, const void *b)
{
  return *(long *)b - *(long *)a;
}

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  long h[n];
  for (int i=0; i<n; i++) scanf("%ld", h+i);
  qsort(h, n, sizeof(long), des);
  if (n <= k) {
    printf("0\n");
    return 0;
  }
  long ans = 0;
  for (int i=k; i<n; i++) ans += h[i];
  printf("%ld\n", ans);
  return 0;
}


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

#define rep(i,a,b) for(ll i = (ll)(a); i < (ll)(b); i++)
#define ff first
#define ss second
#define fill(x,v) memset(x, v, sizeof(x))


typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

vi arr;

int main(){
  ll n,a, dif = 0;
  cin >> n;
  rep(i,0,n){
    cin >> a;
    if(a != i+1) dif++;
  }
  if(dif <= 2) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3564
#include <cstdio>
#include <iostream>
#include <cstring>
#define re register
inline int read() {
	int s = 0; char ch = getchar(), f = ' ';
	while(ch < '0' || ch > '9') { if(ch == '-') f = '-'; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	return f == '-' ? -s : s;
}
const int Max = 120;
int n, ans;
std :: string str;
int main() {
	n = read();
	std :: cin >> str;
	int len = str.length();
	for(re int i = 0; i < len; ++ i) {
		ans ++;
		if(str[i] == str[i-1]) ans --;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 512
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<math.h>
#include<bitset>
#include<random>
using namespace std;
using ll = long long;
using lll = __int128_t;
typedef pair<ll,ll> P;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
const ll longinf=1ll<<60;
const int inf=(1<<30)-1;
const ll mod=1e9+7;



int main(){
      int m,d;
      cin>>m>>d;
      int ans=0;
      for(int i=1;i<=d;i++){
            int d1=i%10;
            int d10=i/10;
            if(d1*d10<=m&&d1>=2&&d10>=2){
                  ans++;
            }
      }
      cout<<ans<<endl;
      return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	int length = String.valueOf(n).length();
	
	int result = 0;
	for (int i = length; i > 0; i--) {
	    if(i % 2 == 0) {
		result += Math.pow(10, i - 1) - Math.pow(10, i - 2);
		i--;
	    }
	    else {
		result += n - Math.pow(10, i - 1) + 1;
	    }
	}
	
	System.out.println(result);
    }
}


Measured memory_bytes: 21972
#include <cstdio>
#include <iostream>
#include <algorithm>
//#include <vector>
//#include <set>
#include <map>
//#include <string>
#include <cstring>
//#include <stack>
#include <queue>
//#include <cmath>
//#include <ctime>
//#include <bitset>
//#include <utility>
//#include <assert.h>
using namespace std;
#define rank rankk
#define mp make_pair
#define pb push_back
#define xo(a,b) ((b)&1?(a):0)
#define tm tmp
//#define LL ll
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const int INF=0x3f3f3f3f;
const double INFF=1e24;
const int MAX=1e6+5;
//const ll MAXN=2e8;
//const int MAX_N=MAX;
const ll MOD=1e9+7;
//const long double pi=acos(-1.0);
const long double eps=1e-9;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<typename T>inline T abs(T a) {return a>0?a:-a;}
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
inline ll powMM(ll a,ll b,ll M){
    ll ret=1;
    a%=M;
//    b%=M;
    while (b){
        if (b&1) ret=ret*a%M;
        b>>=1;
        a=a*a%M;
    }
    return ret;
}
void open()
{
//    freopen("1009.in","r",stdin);
    freopen("out.txt","w",stdout);
}
int n,m,k;
bool vi[MAX];
int main()
{
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        memset(vi,false,sizeof(vi));
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
                vi[i*(m-j)+j*(n-i)]=true;
        }
        if(vi[k])printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
/*

*/


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll h1,m1,h2,m2,k;
int main()
{
    cin>>h1>>m1>>h2>>m2>>k;
    h1=h1*60+m1;
    h2=h2*60+m2;
    if(h2<h1) h2+=12*60;
    h2-=h1;
    h2-=k;
    printf("%lld\n",h2);
}


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

int main()
{
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    if (N == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    if (N <= K)
    {
        cout << N << endl;
        return 0;
    }

    int start_idx = 0;
    int end_idx = (int)(S[0] == '0');
    int count = (int)(S[0] == '0');
    for (int i = 1; i < S.size(); i++)
    {
        if (S[i - 1] == S[i])
        {
            if (S[i] == '1')
            {
                if (count <= K)
                {
                    end_idx = i;
                }
            }
            continue;
        }
        if (S[i] == '0')
        {
            count++;
        }
        if (count <= K)
        {
            end_idx = i;
        }
    }

    int ans = end_idx - start_idx + 1;
    for (start_idx++; start_idx < S.size(); start_idx++)
    {
        if (S[start_idx] == '1' && S[start_idx - 1] == '0')
        {
            for (end_idx++; end_idx < S.size(); end_idx++)
            {
                if (S[end_idx] == '1' && end_idx + 1 < S.size() && S[end_idx + 1] == '0')
                {
                    break;
                }
            }
            if (end_idx <= S.size())
            {
                if (end_idx == S.size())
                {
                    ans = max(ans, (end_idx - 1) - start_idx + 1);
                }
                else
                {
                    ans = max(ans, end_idx - start_idx + 1);
                }
            }
        }
    }
    cout << ans << endl;
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

int main()
{
    string S; cin >> S;
    int max_l = 0;
    rep(i,S.size()){
        for(int j=i; j<S.size(); j++){
            int l = 0;
            for(int k=i; k<=j; k++){
                if(S[k] == 'A' || S[k] == 'G' || S[k] == 'C' || S[k] == 'T') l++;
                else{
                    l = -100;
                    break;
                }
            }
            if(max_l < l) max_l = l;
        }
    }
    cout << max_l << endl;
}

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

typedef long long ll;

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

    int n; cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end(),greater<int>());
    ll tate=0,yoko=0;
    for(int i=1;i<n;){
        if(tate==0 && a[i]==a[i-1]){
            tate = a[i];
            i += 2;
        }else if(yoko==0 && a[i]==a[i-1]){
            yoko = a[i];
            break;
        }else{
            i++;
        }
    }
    ll ans = tate * yoko;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#!/user/bin/env python
#pythonプログラムであることを示している

# -*- coding: utf-8 -*-
"""
このプログラムはPythonを書く際のテンプレとなっています。これをコピペしてコーディングを行なってください。
なお字下げしないこと！！
"""

__author_ = 'Maruta Yuzuha'
__version_ = '1.0.0'
__date__ = '2019/12/25'

def main():
    """
    ここでプログラムの解説を行う
     >>main()
    Hello world.
    0
    """
    s = input().split()
    if (s[0] == s[1]):
        print('Yes')
    else: 
        print('No')
    
    return 0

if __name__ == '__main__':
    #上記のifの記述によってこのスクリプトファイルが起動された時だけ実行する部分になる。
    #ちなみにスクリプトが "モジュールとして"インポートされた時には実行されない、

    #単体テスト:モジュールのdocstring(ドキュメンテーション文字列)に記載された全ての対話実行例が書かれている通りに動作するかを確認
    #python ファイル名 -v
    import doctest
    doctest.testmod()

    #実際にmain()を呼び出して、結果を得て、その結果でPythonシステムを終える
    import sys
    sys.exit(main())

Measured memory_bytes: 8532
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        int ans = 0;
        char prev = s.charAt(0);
        for(int i=0;i<s.length();i++){
            if(prev!=s.charAt(i))ans++;
            prev = s.charAt(i);
        }
        System.out.println(ans);


    }
}


Measured memory_bytes: 23764
#include<stdio.h>

int main(void){
	int n,i,j;
	int a[101];
	long long dp[101][21]={0};
	
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&a[i]);
	dp[0][a[0]] = 1;
	for(i=1;i<n-1;i++){
		for(j=0;j<21;j++){
			if(j-a[i]>=0)
			dp[i][j] = dp[i-1][j-a[i]];
		}
		for(j=0;j<21-a[i];j++){
			dp[i][j] += dp[i-1][j+a[i]];
		}
	}
	printf("%lld\n",dp[n-2][a[n-1]]);
	return 0;
}

Measured memory_bytes: 624
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//ll MOD=1000000007LL;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;
//const ll MAX_V=114514LL;
//const ll MAX = 500010LL;
const ll mod=MOD;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={0,0,1,-1};
vl dy={1,-1,0,0};

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; 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;
    }
}

// 二項係数計算
long long COM(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;
}

ll modpow(ll a, ll n, ll mod) {
  
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll N=2000010;
vl arr(N);
void Eratosthenes(){
	for(ll i = 0; i < N; i++){
		arr[i] = 1;
	}
        arr[1]=0;
	for(ll i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(ll j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}
}
//素数判定O(√n)
bool is_prime(ll n){
  for(ll i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return n!=1;
}


int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(10);
  /*--------------------------------*/
  ll n;cin>>n;
  if(n>=30)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 18676
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main(void) {

    double N,K; cin>>N>>K;
    int a;
    for (int i = 0; i < N; ++i) cin>>a;
    int ans = 0;
    if(N<=K) cout<<1<<endl;
    else{
        cout<<1+ceil((N-K)/(K-1))<<endl;
    }




    return 0;
}

Measured memory_bytes: 256
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


k = inp()
s = str_inp()
comb = combination(mod)
ans = pow(26, len(s) + k, mod)
for i in range(0, len(s)):
    ans -= comb.calc(k + len(s), i) * pow(25, k + len(s) - i, mod)
    ans %= mod
print(ans)


Measured memory_bytes: 285620
a, b, k = map(int, input().split())
if k%2 == 0:
    for _ in range(int(k/2)):
        a = int(a/2)
        b += a
        b = int(b/2)
        a += b
    print(a ,b)
    
else:
    for _ in range(int(k/2)):
        a = int(a/2)
        b += a
        b = int(b/2)
        a += b
    a = int(a/2)
    b += a
    print(int(a),int(b))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N; cin>>N;
  vector<long double>A(N);
  long double count=0;
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  sort(A.begin(),A.end());
  for(int i=0;i<N;i++){
    if(A[i]==0){cout<<0<<endl; return 0;}
    count+=log10(A[i]);
    if(count>18){
      cout<<"-1"<<endl;
      return 0;
    }
  }
  unsigned long long ans=1;
  for(int i=0;i<N;i++){
    ans*=A[i];
    if(ans>1000000000000000000){cout<<"-1"<<endl;return 0;}
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4852
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

int a, b, c, n;
string s;



int main()
{
cin>>a;
  cout<<a*a*a<<endl;
	
}


Measured memory_bytes: 256
N=int(input())
a,b,c,d=0,1e10,-1e10,1e10
for i in range(N):
  A,B=input().split()
  A=int(A)
  B=int(B)
  a=max(a,A+B)
  b=min(b,A+B)
  c=max(c,A-B)
  d=min(d,A-B)
print(max(abs(a-b),abs(c-d)))

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

int main() {
    int n; cin >> n;
    vector<int> a(n); for (int &ai: a) cin >> ai, ai--;
    vector<int> b(n); for (int &bi: b) cin >> bi;
    vector<int> c(n - 1); for (int &ci: c) cin >> ci;
    int ans = 0;
    for (int i = 0; i < n; i++) ans += b[a[i]];
    for (int i = 0; i + 1 < n; i++) {
        if (a[i] + 1 == a[i + 1]) ans += c[a[i]];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long

using namespace std;

const int MAXN=502,MAXM=2000011;
int n,m,q;
int sum[MAXN][MAXN];
int Query(int l,int r)
{
	return sum[r][r]-sum[r][l-1]-sum[l-1][r]+sum[l-1][l-1];
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	
	for(int i=1;i<=m;i++)
	{
		int tx,ty;
		scanf("%d%d",&tx,&ty);
		sum[tx][ty]++;
		sum[ty][tx]++;
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	
	for(int i=1;i<=q;i++)
	{
		int tx,ty;
		scanf("%d%d",&tx,&ty);
		printf("%d\n",Query(tx,ty)/2);
	}
	
	
	return 0;
}



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

bridges = []
for i in range(M):
    a, b = map(int, input().split())
    bridges.append((a, b))

bridges.sort(key=lambda x: x[1])

ans = 0
x = 0
for i in range(M):
    a, b = bridges[i]
    if a >= x:
        x = b
        ans += 1

print(ans)



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

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define mp(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll IINF = INT_MAX;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < k; i++) ans += a[i];
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3652
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
 
public class Main {
	public static void main(String[] args) {
		
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int L = sc.nextInt();
		List<String> inputs = new ArrayList<String>();
		for(int i = 0; i < N; i++) {
			inputs.add(sc.next());
		}
		Collections.sort(inputs);
		String output = String.join("", inputs);
		System.out.println(output);
	}
}

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

using namespace std;

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

	vector<int> cnt(n);

	for(int i = 0; i < k; ++i) {
		int d;
		cin >> d;
		for(int j = 0; j < d; ++j) {
			int x;
			cin >> x;
			++cnt[x - 1];
		}
	}
	
	int ans = 0;
	for(int i : cnt) {
		if(i == 0) {
			++ans;
		}
	}

	cout << ans << '\n';

	return 0;
}


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

 
int main(){
  string a,b,c;
  cin >> a >> b >> c;
  if( a.back() == b.front() && b.back() == c.front() ){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long; 
using P=pair<int,int>;
using lP=pair<ll,ll>;
using fP=pair<double,double>;
ll const mod=1e9+7;
const ll MAX=300000;
ll modpow(ll a,ll b){
  ll r=1;
  while(b>0){
    if(b%2==1)(r*=a)%=mod;
    (a*=a)%=mod;
    b/=2;
  }
  return r;
}
ll chose(ll a,ll b){
  if(b==0||b==a)return 1;
  if(b==1||b+1==a)return a;
  ll x=a,y=b;
  while(y>1){
    (a*=(--x))%=mod;
    (b*=(--y))%=mod;
  }
  return a*modpow(b,mod-2)%mod;
}

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    ll ans=0;
    ans=modpow(2,n)-1;
    //cout<<ans<<endl;
    ans-=chose(n,a);
    //cout<<ans<<endl;
    if(a!=b)ans-=chose(n,b);
    if(ans<0)ans+=mod;
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define F  first
#define S  second
#define ff(i,n) for(i=0;i<n;i++)
int main()
{ 
	ll t;
	t=1;
	while(t--)
	{
		ll i,n,sum=0;
		cin>>n;
		map<ll,ll> map1;
		ff(i,n)
		{
			ll x;
			cin>>x;
			map1[x]++;
			sum+=x;
		}
		ll q;
		cin>>q;
		while(q--)
		{
			ll a,b;
			cin>>a>>b;
			if(map1.find(a)!=map1.end())
			{
				ll s = map1[a];
				if(map1.find(b)==map1.end())
				{
					map1[b] = map1[a];
					map1.erase(a);
				}
				else
				{
					map1[b]+=map1[a];
					map1.erase(a);
				}
				sum+=s*(b-a);
			}
			printf("%lld\n",sum);
		}
	}
	return 0;
}

Measured memory_bytes: 7672
s = list(input())
K = int(input())

for i in range(len(s)):
    tmp = ord(s[i]) # asciiコードにする
    # 123もaを表していると考える
    if 1 <= 123 - tmp <= K and tmp != 97:
        # 'a'にできるものは先にaにしていく
        s[i] = "a"
        K -= (123 - tmp)

if K > 0:
    K = K % 26 # 26回で一回転
    tmp = (K + ord(s[-1]))
    s[-1] = chr(tmp)

def print_all(s):
    for t in s:
        print(t, end="")
    print()


print_all(s)


Measured memory_bytes: 5484
#include<stdio.h>

int main(void)
{
    int a,b,c;
    int k;
    long int i;
    long int sum = 0;
    int sum_comm = 0;
    int abc[300][300][300];

    for(a = 0;a < 300 ;a++)
    {
        for(b = 0;b < 300 ;b++)
        {
            for(c = 0;c < 300 ;c++)
            {
                abc[a][b][c] = 0;
            }
        }
    }
    scanf("%d", &k);

    for(i = 1 ; i <= k ; i ++)
    {
        for(a = 1 ; a <= k ; a++ )
        {
            for( b = 1 ; b <= k ; b++ )
            {
                for( c = 1 ;c <= k ; c++ )
                {
                    if(a % i == 0 && b % i == 0 && c % i ==0)
                    {
                        abc[a][b][c] = i;
                    }
                }
            }
        }

    }

    for(a = 0;a < 300 ;a++)
    {
        for(b = 0;b < 300 ;b++)
        {
            for(c = 0;c < 300 ;c++)
            {
                sum_comm += abc[a][b][c];
            }
        }
    }

//        printf("%d\n",number[i]);
    printf( "%d\n",sum_comm);
    return 0;
}




Measured memory_bytes: 107200
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

int main(){
    int r;
    cin >> r;
    cout << r * r << endl;
}

Measured memory_bytes: 3612
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <stack>
#include <iomanip>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int maxn = 2e5 + 7;
const int inf = 2e9 + 7;
const ll infl = 1e18 + 7;
const long double eps = 1e-9;
const ll mod = 998244353;

int main() {
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif // _DEBUG

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

	int n, W;
	cin >> n >> W;
	vector<pair<int, ll>> a;
	for (int i = 0; i < n; i++) {
		int w, v;
		cin >> w >> v;
		a.push_back({ w, v });
	}

	vector<vector<ll>> dp(n + 1, vector<ll>(W + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= W; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j - a[i - 1].ff >= 0) {
				ll res = dp[i - 1][j - a[i - 1].ff] + a[i - 1].ss;
				dp[i][j] = max(dp[i][j], res);
			}
		}
	}
	cout << dp[n][W];
	return 0;
}

Measured memory_bytes: 80256
/*
 * Author : Andrew J
*/
#include <bits/stdc++.h>
using namespace std;
#define rall(x) x.rbegin() , x.rend()
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
using ll = long long;
using ii = pair <int , int>;
void in(int &x);
const int N = 1e5 + 10;
#define singleCase
// #define multipleCase
int n,a[N];
map <int , int> freq;

void work() {
   in(n);
   for (int i = 1 ; i <= n ; i++) {
      in(a[i]);
      freq[a[i]]++;
   }
   if (freq.size() > 3) {
      puts("No");
      return;
   } else if (freq.size() == 3) {
      int res = 0, lowest = INT_MAX;
      for (ii x : freq) {
         res ^= x.fi;
         lowest = min(lowest , x.se);
      }
      if (res != 0) {
         puts("No");
         return;
      }
      for (ii x : freq) {
         if (x.se - lowest > 0) {
            puts("No");
            return;
         }
      }
   } else if (freq.size() == 2) {
      vector <int> v;
      for (ii x : freq) {
         v.pb(x.fi);
      }
      if (v[0] == 0) {
         if (freq[0] * 2 != freq[v[1]]) {
            puts("No");
            return;
         }
      } else if (v[1] == 0) {
         if (freq[0] * 2 != freq[v[0]]) {
            puts("No");
            return;
         }
      } else {
         puts("No");
         return;
      }
   } else {
      for (ii x : freq) {
         if (x.fi != 0) {
            puts("No");
            return;
         }
      }
   }
   puts("Yes");
   return;
}

int main() {
   #ifdef multipleCase
      int nQ; in(nQ);
      while (nQ--)
         work();
   #endif
   #ifdef singleCase
      work();
   #endif
   return 0;
}

void in(int &x) {
	bool neg = false;
	register int c;
	x = 0;
	c = getchar();
	if(c == '-') {
		neg = true;
		c = getchar();
	}
	for (; c > 47 && c < 58; c = getchar())
	  x = (x << 1) + (x << 3) + c - 48;
	if (neg) x *= -1;
}


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

int main(){
  
  int N; cin >> N;
  int p[N];
  for (int i = 0; i < N; i++) cin >> p[i];
  
  int count = 0;
  
  for (int i = 1; i < N-1; i++){
    bool dai1 = p[i-1] < p[i];
    bool dai2 = p[i] < p[i+1];
    bool shou1 = p[i-1] > p[i];
    bool shou2 = p[i] > p[i+1];
    if ((dai1 && dai2) || (shou1 && shou2)){
      count ++;
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    int a;
    while(cin>>a)

    {
      cin>>s;
      if(s.size()>a)
      {
          for(int i=0;i<a;i++)
          {
              cout<<s[i];
          }
          cout<<"..."<<endl;
      }
      else
      {
          cout<<s<<endl;
      }




    }











    return 0;
}


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

void solve() 
{
    int s,w;cin>>s>>w;
    cout<<(w>=s?"unsafe":"safe")<<endl;
}

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

Measured memory_bytes: 3576
//Author : pakhandi
//
using namespace std;

#include <bits/stdc++.h>

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

#define IGNORE cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');

const ll INF = (1LL << 58);

#ifdef BUGGY
	bool DEBUG = 1;
#endif
#ifndef BUGGY
	bool DEBUG = 0;
#endif

ll A, C;

int main()
{
	cin >> A >> C;
	cout << 2*C - A;

	return 0;
}
/*
	Powered by Buggy Plugin
*/ 

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

int main() {
	int a, b, c;
	cin >> a;
	cin >> b;

	c = (a*b)%2;
	if (c == 0) {
		cout << "Even" << endl;
	}
	else {
		cout << "Odd" << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <queue>
#include <memory>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)

using namespace std;
using ll = long long;
const int mod = 1e9+7;

int main(){
    int a,b;
    string s;
    cin >> a >> b;
    cin >> s;

    bool f = false;
    if(s.length() != a+b+1 || s[a] != '-'){
        cout << "No" << endl;
        return 0;
    }

    rep(i,a+b+1){
        if(i == a) continue;
        int x = s[i] - '0';
        if(x < 0 || x > 9){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(ll)(n);++i)
#define _repe3(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define _rrepe2(i,n) for(ll i=(ll)(n);i>=0;i--)
#define _rrepe3(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)
#define rrepe(...) _overload3(__VA_ARGS__,_rrepe3,_rrepe2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
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;}

ll N;
ll M;
vl A;
vl B;

void solve();

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> N;
    cin >> M;
    A = vl(M);
    B = vl(M);
    for(int i = 0; i < M; ++i){
        cin >> A[i];
        cin >> B[i];
    }
    solve();
}

// 2 <= N <= 2× 10^5
// 0 <= M <= 2× 10^5
// 1<= A_i,B_i<= N
// A_i != B_i

struct UnionFind {
    vector<int> par;

    UnionFind(int sz){
        par.assign(sz+1,-1);
    }

    bool unite(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return false;
        if(par[x]>par[y])swap(x,y);
        par[x]+=par[y];
        par[y]=x;
        return true;
    }

    int find(int x){
        if(par[x]<0)return x;
        return par[x]=find(par[x]);
    }

    int size(int x){
        return -par[find(x)];
    }
};

// ll N, ll M, vl A, vl B
// 答えを出力せよ。
void solve(){
    UnionFind uf(N);
    rep(i,M)uf.unite(A[i]-1,B[i]-1);
    
    ll ans=0;
    rep(i,N)chmax(ans,(ll)uf.size(i));
    cout<<ans<<endl;
}


Measured memory_bytes: 7120
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	int n,p[55],i,j,k;
	bool flag;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> p[i];
	}
	for(i=0; i<n; ++i){
		for(j=0; j<n; ++j){
			swap(p[i],p[j]);
			flag = true;
			for(k=1; k<n; ++k){
				if(!(p[k-1]<p[k])){
					flag = false;
					break;
				}
			}
			if(flag){
				cout << "YES" << endl;
				return 0;
			}
			swap(p[i],p[j]);
		}
	}
	cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
        "fmt"
)

func solution(a, b int) int {
        if b == 1 {
                return 0
        }
        if a >= b {
                return 1
        }

        c, p := 1, a

        for p < b {
                p += a - 1
                c++
        }
        return c
}

func main() {
        var a, b int
        fmt.Scan(&a, &b)
        fmt.Println(solution(a, b))
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

// https://atcoder.jp/contests/abc081/tasks/abc081_b

public class ABC081_B // ←Class名変更！！
{
    public static void Main()
    {
        var n = Ri();
        var a = Ria();

        var max = 0;
        var count = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] % 2 == 0)
            {
                a[i] = a[i] / 2;
            }
            else
            {
                max = count;
                break;
            }

            if (i == n - 1)
            {
                i = 0;
                count++;
            }
        }

        WriteLine($"{max}");
    } // Main

    public static string Rs() { return ReadLine(); }
    public static char Rc() { var c = ReadLine(); return c[0]; }    //最初の1文字だけ返す
    public static int Ri() { return int.Parse(ReadLine()); }
    public static long Rl() { return long.Parse(ReadLine()); }
    public static char[] Rca() { return ReadLine().ToCharArray(); }
    public static int[] Ria() { return Array.ConvertAll(ReadLine().Split(' '), int.Parse); }
    public static long[] Rla() { return Array.ConvertAll(ReadLine().Split(' '), long.Parse); }
} // Class


Measured memory_bytes: 13252