akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N;
    cin >> N;
    int zero = 0, one = 0, two = 0;
    rep(i, N){
        int a;
        cin >> a;
        if(a % 4 == 0) two++;
        else if(a % 2 == 0) one++;
        else zero++;
    }
    
    if(one == 0){
        if(two + 1 >= zero){
            output("Yes");
        }
        else{
            output("No");
        }
    }
    else{
        if(two >= zero) output("Yes");
        else output("No");
    }
    
    return 0;
}

Measured memory_bytes: 256
/* ex9_1
   nabe9393 */

#include<stdio.h>
#include<stdlib.h>
#define SIZE 11
typedef struct stack{
  int size;
  int count;
  char data[SIZE];
  char *top;
} stack;

//関数
void initialize_stack(stack *stk);
void print_stack(stack *stk);
void push(stack *stk, char elem);
char pop(stack *stk);

int main(void){
  stack stk;
  int i;
  char str[11];
  //初期化
  initialize_stack(&stk);
  //入力
  for(i=0;i<10;i++){
    scanf("%c",&str[i]);
  }
  for(i=0;i<10;i++){
    if(str[i]=='1' || str[i]=='0'){
      //スタックにデータを追加
      push(&stk, str[i]);
    }
    if(str[i]=='B'){
      if(stk.count>0){
        //スタックからデータを取り出す
        pop(&stk);
      }
    }
  }
  //結果の出力
  print_stack(&stk);
  return 0;
}
      
void initialize_stack(stack *stk){
  stk->count = 0;
  stk->size = SIZE;
  stk->top = &(stk->data[SIZE]);
}

void push(stack *stk, char elem){
  if(stk->count >= stk->size){
    printf("Error: stack overflow. (x=%c)\n", elem);
    exit(1);
  }
  else{
    stk->top--;
    *(stk->top) = elem;
    stk->count++;
  }
}

char pop(stack *stk){
  char elem;
  if(stk->count <= 0){
    printf("Error: stack underflow.\n");
    exit(1);
  }
  else{
    elem = *(stk->top);
    stk->top++;
    stk->count--;
    return elem;
  }
}

void print_stack(stack *stk){
  char output[11], *ptr_out;
  ptr_out = stk->top;
  for(int i=stk->count;i>0;i--){
    //逆順にする
    output[i-1] = *ptr_out;
    ptr_out++;
  }
  printf("%s\n",output);
}

Measured memory_bytes: 1516
int_a, int_b, int_c = list(map(int, input().split()))
int_k = int(input())


ar_order = sorted([int_a, int_b, int_c], reverse=True)

int_max = ar_order.pop(0)

for n in range(int_k):
    int_max *= 2


print(int_max + sum(ar_order))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP2(i,j,n) for(int i=j;i<n;i++)
const int INF = 1000000009;


int main(){
    int N;
    cin >> N;
    int a[N],b[N],c[N];
    REP(i,N){
        cin>>a[i]>>b[i]>>c[i];
    }
    //dpは3*Nの配列，0→a,1→b,2→c
    int dp[N][3] ={0};
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];
    REP2(j,1,N){
        dp[j][0] = max(dp[j-1][1],dp[j-1][2])+a[j];
        dp[j][1] = max(dp[j-1][0],dp[j-1][2])+b[j];
        dp[j][2] = max(dp[j-1][1],dp[j-1][0])+c[j];
    }
    int ans = (dp[N-1][0]>dp[N-1][1]) ? dp[N-1][0]:dp[N-1][1];
    ans = (ans > dp[N-1][2]) ? ans :dp[N-1][2];
    cout << ans << endl;
}

Measured memory_bytes: 2560
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define sqr(x) (x) * (x)

using namespace std;
using namespace __gnu_pbds;

mt19937_64 gen(time(0));

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

//const int inf = 2e9 + 34333;
//const ll mod = 1e9 + 7;
const int maxn = 6;

char c[maxn][maxn];

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif
    int h, w, k;
    cin >> h >> w >> k;
    for(int i = 0; i < h; ++i)
        for(int j = 0; j < w; ++j)
            cin >> c[i][j];
    int ans = 0;
    for(int msk1 = 0; msk1 < (1 << h); ++msk1)
        for(int msk2 = 0; msk2 < (1 << w); ++msk2)
        {
            int b = 0;
            for(int i = 0; i < h; ++i)
                for(int j = 0; j < w; ++j)
                {
                    if (c[i][j] == '#' && ((msk1 >> i) & 1) == 0 &&
                        ((msk2 >> j) & 1) == 0)
                            ++b;
                }
            if (b == k) ans++;
        }
    cout << ans;
    return 0;
}


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

using ll = long long;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (fopen("input.in", "r")) {
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
  }

  ll N, W;
  cin >> N >> W;
  vector<ll> w(N+1), v(N+1);
  for (ll i = 1; i <= N; i++) {
    cin >> w[i] >> v[i];
  }

  // dp[j][i] = by using first j items, construct sum i (max value)

  vector<vector<ll>> dp(N+1, vector<ll>(W+1, 0));

  for (ll j = 1; j <= N; j++) {
    for (ll i = 1; i <= W; i++) {
      if (i-w[j] >= 0) dp[j][i] = max(dp[j][i], dp[j-1][i-w[j]]+v[j]);
      dp[j][i] = max(dp[j][i], dp[j-1][i]);
    }
  }

  cout << dp[N][W] << endl;

  return 0;
}

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

int gcd1(int a,int b){
    int tmp; 
  if(a>=b){
  while(b!=0){
    tmp=a;
    a=b;
    b=tmp%b;
  }
  }else{
    a=gcd1(b,a);
  }
  return a;
}

int gcd2(int a,int b,int c){
  int n;
  n=gcd1(gcd1(a,b),c);
  return n;
} 

int main(){
  long long k,sum=0;
  cin >> k;
  for(int i=1;i<=k;i++){
    for(int j=1;j<=k;j++){
      for(int l=1;l<=k;l++){
        sum+=gcd2(i,j,l);
    }
    }
  }
  cout << sum <<endl;
  return 0;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
using namespace std;

int main()
{
    int R;
    cin >> R;
    
    if (R < 1200) {
        cout << "ABC" << endl;
    }else if(R < 2800){
        cout << "ARC" << endl;
    }else{
        cout << "AGC" << endl;
    }
    
    return 0;
}

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

string week[7] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

int main() {
    string S;
    cin >> S;
    for (int i = 0; i < 7; i++) {
        if (S == week[i]) {
            cout << 7 - i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// ~ は、-1の時だけfalse
// struct Edge {
//   int to, id;
//   Edge(int a, int b): to(a), id(b) {}
// };

int main(int argc, char const *argv[])
{
	int x,y,z;cin>>x>>y>>z;

	cout<<z<<" "<<x<<" "<<y<<endl;
	return 0;
}

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

int main(){
   int N, M;
   cin >> N >> M;
   map<int, int> ab;
   for (int i=0; i<M; i++){
      int a, b;
      cin >> a >> b;
      ab[a]++;
      ab[b]++;
   }
   for (int i=1; i<=N; i++){
      cout << ab[i] << endl;
   }

}



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

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

int main() {
	int n, g;
	cin >> n >> g;
	for (int i = 0, a; i < n - 1; i++) {
		cin >> a;
		g = gcd(g, a);
	}
	int count = 0;
	while (g % 2 == 0) {
		count++;
		g >>= 1;
	}
	cout << count;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] a = new int[N];
    for(int i = 0; i < N; i++) {
      a[i] = sc.nextInt();
    }
    Arrays.sort(a);
    int l = 0;
    int r = N;
    int ans = -1;
    while(l < r) {
      int med = (l + r) / 2;
      boolean[][] dp = new boolean[N][K + 1];
      dp[0][0] = true;
      if(med != 0 && a[0] < K + 1) dp[0][a[0]] = true;
      for(int j = 1; j < N; j++) {
        for(int k = 0; k < K + 1; k++) {
          if(med == j) {
            dp[j][k] = dp[j - 1][k];
          } else {
            if(k >= a[j]) {
              dp[j][k] = dp[j - 1][k] || dp[j - 1][k - a[j]];
            } else {
              dp[j][k] = dp[j - 1][k];
            }
          }
        }
      }
      boolean flg = false;
      for(int j = Math.max(0, K - a[med]); j < K; j++) {
        flg = flg || dp[N - 1][j];
      }
      if(flg) {
        r = med;
      } else {
        l = med + 1;
        ans = med;
      }
    }
    System.out.println(ans + 1);
  }
}


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

const long double PI = acos(-1);
constexpr long double EPS = 1e-15;
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,pair<ll,ll>> P;

//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

vector<int> G[100010];
ll d[100010][3];
ll s,t;
ll n,m;

void solve() {
  cin >> n >> m;
  REP(i,m) {
    ll from,to;
    cin >> from >> to;
    from--,to--;
    G[to].pb(from);
  }
  cin >> s >> t;
  s--,t--;
  REP(i,n) {
    REP(j,3) {
      d[i][j] = -1;
    }
  }
  priority_queue<P,vector<P>,greater<P>> pq;
  pq.push({0,{t,0}});
  d[t][0] = 0;
  while (!pq.empty()) {
    P tp = pq.top();
    pq.pop();
    if (tp.fi > d[tp.se.fi][tp.se.se]) continue;
    for (int i = 0; i < G[tp.se.fi].size(); i++) {
      int to = G[tp.se.fi][i];
      if (tp.se.se != 2) {
        if (d[to][tp.se.se+1] == -1 || d[to][tp.se.se+1] > tp.fi) {
          d[to][tp.se.se+1] = tp.fi;
          pq.push({d[to][tp.se.se+1],{to,tp.se.se+1}});
        }
      } else {
        if (d[to][0] == -1 || d[to][0] > tp.fi + 1) {
          d[to][0] = tp.fi + 1;
          pq.push({d[to][0],{to,0}});
        }
      }
    }
  }
  cout << d[s][0] << endl;
}

int main(int argc, char *argv[]){

  /* Regular */
  int case_num = 1;
  if (argc > 1 && stoi(argv[1])) cin >> case_num;
  REP(case_no, case_num) {
    cerr << endl << "case " << case_no + 1 << endl;
    solve();
  }
  
  // /* AOJ */
  // solve();
  return 0;
}

Measured memory_bytes: 10480
//****** @mdazmat9 **********
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define EB emplace_back
#define PB push_back
#define endl "\n"
#define MOD 1000000007
#define MOD2 998244353
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
typedef pair<int, int> pr;
typedef vector<int> VI;
typedef vector<pr> VP;
typedef vector<string> VS;
typedef vector<vector<int>> VV;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define trace(v) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
const int inf = 1e17;
int fast_pow(int x, int y, int p);
const int sz = 200001;
VI g[sz];
int n;
int dp[sz][2];

int rec(int node,int tight,int pr){
	if(dp[node][tight]!=-1)return dp[node][tight];
	int ans = 0;
	int w = 1;
	for(auto x:g[node]){
		if(x!=pr){
			w= (w*rec(x,0,node))%MOD;
		}
	}
	ans+=w;
	ans%=MOD;
	if(!tight){	
		int b = 1;
		for(auto x:g[node]){
			if(x!=pr){
				b= (b*rec(x,1,node))%MOD;
			}
		}
		ans+=b;
		ans%=MOD;
	}
	return dp[node][tight]=ans;
}

void solve() {
	cin>>n;
	for(int i=0;i<n-1;i++){
		int x,y;
		cin>>x>>y;
		g[x].EB(y);
		g[y].EB(x);
	}
	memset(dp,-1,sizeof dp);
	cout<<rec(1,0,-1);
}


int32_t main() {

	IOS;
	int test = 1;
	// cin>>test;
	for (int i = 1; i <= test; i++) {
        // cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}
int fast_pow(int x, int y, int p) {
	int res = 1;
	x = x % p;
	while (y > 0) {
		if (y & 1)
			res = (res * x) % p;
		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}

Measured memory_bytes: 19584
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(), x.end()

int main() {
  string s;
  cin >> s;
  ll j, n = s.size();
  vector<ll> ans(n);
  for (ll i = 0; i < n; i++) {
    if (s.at(i) == 'R')
      j = i;
    else
      ans.at(j + (i - j) % 2)++;
  }
  for (ll i = n - 1; i >= 0; i--) {
    if (s.at(i) == 'L')
      j = i;
    else
      ans.at(j - (j - i) % 2)++;
  }
  for (ll i = 0; i < n; i++) {
    cout << ans.at(i) << ' ';
  }
  cout << endl;
}

Measured memory_bytes: 1408
function main(input) {
  var t = input.split(' ').map(x => x * 1);
  
  if ((t[0] * t[1]) % 2 === 0) {
     console.log("Even");
  } else {
    console.log("Odd"); 
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;


int main() {
    string n;
    bool ans = true;
    cin >> n;
    vector<int>ss(26,1);
    for (auto s : n) {
        ss[s - 'a']--;
    }
    for (auto a : ss)if (a < 0)ans = false;
    if (ans) {
        cout << "yes" << endl;
    }
    else {
        cout << "no" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
//q015.cpp
//Sun Aug  9 12:40:42 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007
#define rep(i,n) for (int i=0;i<(n);++i)

using namespace std;
using ll=long long;
typedef pair<double,double> P;

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

	P p[n];
	rep(i,n) {
		double x,y;
		cin >> x >> y;
		p[i].first = x;
		p[i].second = y;
	}

	double ans = 0;
	sort(p,p+n);
	do {
		double tmp = 0;
		for (int i=1;i<n;i++){
			tmp += sqrt((p[i].first-p[i-1].first)*(p[i].first-p[i-1].first)+
		(p[i].second-p[i-1].second)*(p[i].second-p[i-1].second));
		}
		ans += tmp;
	} while (next_permutation(p,p+n));

	for (int i=1;i<=n;i++){
		ans = ans/double(i);
	}

	printf("%.10f\n",ans);
}

Measured memory_bytes: 3708
// +build ignore
package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10240), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []byte {
	return []byte(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

func run(input io.Reader, output io.Writer) int {
	sc := NewScanner()
	N := sc.nextInt()
	S := sc.nextStr()

	if N == 0 {
	}

	if N < 4 {
		fmt.Println(0)
		return 0
	}

	var nr, nb, ng int
	for _, c := range S {
		if c == 'R' {
			nr++
		}

		if c == 'B' {
			nb++
		}

		if c == 'G' {
			ng++
		}
	}

	same := 0
	// etot := 0
	for a := 1; a < N; a++ {
		i := 0
		j := 1 * a
		k := 2 * a
		if k >= N {
			break
		}
		for k < N {
			// etot++
			// fmt.Printf("(%4d) [%2d] (%3d, %3d, %3d)", etot, a, i, j, k)
			if S[i] != S[j] && S[i] != S[k] && S[j] != S[k] {
				same++
				// fmt.Printf(" (%4d)", same)
			}
			// fmt.Println()
			i += 1
			j += 1
			k += 1
		}
	}

	tot := nr * nb * ng

	// sum := 0
	// sum2 := 0
	// for k := 2; k < N; k++ {
	// 	for j := 1; j < k; j++ {
	// 		for i := 0; i < j; i++ {
	// 			if j-i == k-j {
	// 				if S[i] != S[j] && S[i] != S[k] && S[j] != S[k] {
	// 					sum2++
	// 				}
	// 				continue
	// 			}

	// 			if S[i] != S[j] && S[i] != S[k] && S[j] != S[k] {
	// 				sum++
	// 			}
	// 		}
	// 	}
	// }

	// fmt.Println(tot, same, sum, sum2)
	fmt.Println(tot - same)

	return 0
}

func main() {
	os.Exit(run(os.Stdin, os.Stdout))
}


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

int N;
map<pair<ll, ll>, pair<ll, ll>> M;
int Z;
ll p2[202020];
const ll mo = 1000000007;
// https://kmjp.hatenablog.jp/entry/2020/05/17/1000
int main()
{
    int i, j, k, l, r, x, y;
    string s;

    p2[0] = 1;
    for (int i = 0; i < 201010; i++)
    {
        p2[i + 1] = p2[i] * 2 % mo;
    }

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        ll X, Y;
        cin >> X >> Y;
        if (X == 0 && Y == 0)
        {
            Z++;
        }
        else if (X == 0)
        {
            M[{0, 0}].first++;
        }
        else if (Y == 0)
        {
            M[{0, 0}].second++;
        }
        else
        {
            if (Y < 0)
            {
                X = -X, Y = -Y;
            }
            ll g = __gcd(abs(X), abs(Y));
            X /= g;
            Y /= g;
            if (X < 0)
            {
                M[{Y, -X}].first++;
            }
            else
            {
                M[{X, Y}].second++;
            }
        }
    }
    ll ret = 1;
    for(auto m : M)
    {
        ll a = p2[m.second.first] + p2[m.second.second] - 1;
        ret = (ret * a) % mo;
    }

    cout << (ret + Z + mo - 1) % mo << endl;
    return 0;
}

Measured memory_bytes: 20784
#include <stdio.h>

/*óÔÔê*/
int status_no[20000];
int status_no_max;
/*[xÀW][yÀW][óÔÔ][¼OªJ©]*/
int memo[20][20][20000][2];

/*üÍîñ*/
char flag[20][21];
int width,height;

/*óÔðñ·é*/
void enum_status(void) {
	int current_number;
	int pos;
	int i;
	status_no[0]=0;
	status_no[1]=1;
	pos=2;
	for(current_number=2;current_number<(1<<19);current_number<<=1) {
		for(i=0;status_no[i]<(current_number>>1);i++) {
			status_no[pos]=current_number | status_no[i];
			pos++;
		}
	}
	status_no_max=pos-1;
}

/*óÔÔðæ¾·é*/
int get_status_num(int status) {
	int left=0;
	int right=status_no_max;
	int mid;
	while(left<=right) {
		mid=(left+right)/2;
		if(status==status_no[mid])return mid;
		else if(status<status_no[mid])right=mid-1;
		else left=mid+1;
	}
	return 0;
}

int search_flags(int w,int h,int x,int y,int stat,int maeisj);

int main(void) {
	int i;
	int all_flags;
	int bad_flags;
	int x,y;
	scanf("%d %d",&height,&width);
	for(i=0;i<height;i++)scanf("%s",flag[i]);
	enum_status();
	/*SÄÌøÌíÞðæ¾*/
	all_flags=1;
	for(y=0;y<height;y++) {
		for(x=0;x<width;x++) {
			if(flag[y][x]=='?') {
				all_flags=(all_flags*3)%100000;
			}
		}
	}
	/*¢¢øÅÈ¢øÌíÞðæ¾*/
	bad_flags=search_flags(width,height,0,0,0,0);
	/*¢¢øÌíÞðoÍ*/
	if(all_flags<bad_flags)all_flags+=100000;
	printf("%d\n",all_flags-bad_flags);
	return 0;
}

int search_flags(int w,int h,int x,int y,int stat,int maeisj) {
	int result=0;
	int stat2;
	if(y>=h)return 1;
	else if(x>=w)return search_flags(w,h,0,y+1,stat,0);
	if(memo[x][y][get_status_num(stat)][maeisj]>0) {
		return memo[x][y][get_status_num(stat)][maeisj]-1;
	}
	if(flag[y][x]!='?') {
		if(flag[y][x]=='J') {
			stat2=(stat<<1) & ((1<<(w-1))-1);
			result=search_flags(w,h,x+1,y,stat2,1);
		} else if(flag[y][x]=='O') {
			stat2=(stat<<1) & ((1<<(w-1))-1);
			if(maeisj)stat2|=1;
			result=search_flags(w,h,x+1,y,stat2,0);
		} else if(flag[y][x]=='I') {
			if(!(stat & (1<<(w-2)))) {
				/*ãÉJOª³¢ê*/
				stat2=(stat<<1) & ((1<<(w-1))-1);
				result=search_flags(w,h,x+1,y,stat2,0);
			}
		}
	} else {
		/*JðÄÍßé*/
		stat2=(stat<<1) & ((1<<(w-1))-1);
		result=search_flags(w,h,x+1,y,stat2,1);
		/*OðÄÍßé*/
		stat2=(stat<<1) & ((1<<(w-1))-1);
		if(maeisj)stat2|=1;
		result+=search_flags(w,h,x+1,y,stat2,0);
		/*IðÄÍßé*/
		if(!(stat & (1<<(w-2)))) {
			/*ãÉJOª³¢ê*/
			stat2=(stat<<1) & ((1<<(w-1))-1);
			result+=search_flags(w,h,x+1,y,stat2,0);
		}
	}
	result%=100000;
	memo[x][y][get_status_num(stat)][maeisj]=result+1;
	return result;
}

Measured memory_bytes: 30000
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iomanip>
using namespace std;
#define mod (long)(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<long> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } long C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int main(){
    int N, K;
    cin >> N >> K;
    YES(2 * K - 1 <= N);
}


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

static const int N = 100;
static const int white = 0;
static const int gray = 1;
static const int black = 2;

int n, m[N][N];
int nt[N], color[N];
int d[N], f[N];
int tt;

int next(int u) {
	for (int v = nt[u]; v < n; v++) {
		nt[u] = v + 1;
		if (m[u][v] == 1)
			return v;
	}
	return -1;
}

void dfs(int u) {
	for (int i = 0; i < n; i++)
		nt[i] = 0;
	stack<int> s;
	s.push(u);
	color[u] = gray;
	d[u] = ++tt;
	while (!s.empty()) {
		int u = s.top();
		int v = next(u);
		if (v != -1) {
			if (color[v] == white) {
				s.push(v);
				color[v] = gray;
				d[v] = ++tt;
			}
		} else {
			s.pop();
			color[u] = black;
			f[u] = ++tt;
		}
	}
}

void dfs_init() {
	tt = 0;
	for (int i = 0; i < n; i++)
		color[i] = white;
	
	for (int i = 0; i < n; i++) {
		if (color[i] == white)
			dfs(i);
	}
	for (int i = 0; i < n; i++) {
		cout << i + 1 << " " << d[i] << " " << f[i] << endl;
	}
}

int main() {
	int k, u, v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			m[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++) {
			cin >> v;
			v--;
			m[u][v] = 1;
		}
	}
	dfs_init();
	return 0;
}



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

#ifndef ONLINE_JUDGE
	#define W(x, y) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << y;
#else
	#define W(x, y)
#endif

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define vl vector<ll>
#define vll vector<pll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pi acosl(-1)
#define ld long double
#define prime (1000000000 + 7)
#define INF 1000000000

using namespace std;


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

    string s, t, u;
    ll a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if(u == s){
        a--;
    } else{
        b--;
    }
    cout << a << " " << b << endl;

   
    return 0;
}


/*
    r   o   #   r   o   u   n   d
-1  0   0   0   1   2   0   0   0 
*/
// 1 = 3
// 2 = 3
// 3 = -1
// 4 = 0
// 5 = 1

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

using namespace std;


void solve() {
    int N; cin >> N;
    vector<vector<pair<int, int>>> testimony(N);

    for (int i = 0; i < N; i++) {
        int a; cin >> a;
        for (int j = 0; j < a; j++) {
            int x, y; cin >> x >> y; x--;
            testimony[i].push_back(make_pair(x, y));
        }
    }

    int ans = 0;

    for (int bit = 0; bit < 1<<N; bit++) {

        bool flag = true;

        int tmp = 0;

        for (int i = 0; i < N; i++) {
            if (bit & 1<<i){
                tmp++;
                for (auto e : testimony[i]) {
                    if (e.second == 0) {
                        if (bit & 1<<e.first) flag = false;
                    }
                    if (e.second == 1) {
                        if (!(bit & 1<<e.first)) flag = false;
                    }
                }
            }
        }

        if (flag) ans = max(ans, tmp);
    }

    cout << ans << endl;
}


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

Measured memory_bytes: 3620
using System;

namespace AtBC175
{
    class Program
    {
        static void Main(string[] args)
        {

            string input = Console.ReadLine();
            if (input == "SSS")
            {
                Console.WriteLine("0");
            }
            if (input == "SSR")
            {
                Console.WriteLine("1");
            }
            if (input == "SRS")
            {
                Console.WriteLine("1");
            }
            if (input == "RSS")
            {
                Console.WriteLine("1");
            }
            if (input == "RRS")
            {
                Console.WriteLine("2");
            }
            if (input == "SRR")
            {
                Console.WriteLine("2");
            }
            if (input == "RRR")
            {
                Console.WriteLine("3");
            }
            if (input == "RSR")
            {
                Console.WriteLine("1");
            }
        }
    }
}

Measured memory_bytes: 25872
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
// typedef long double ldouble;

using Graph = vector<vector<int>>;

// int ctoi(const char c){
//   if('0' <= c && c <= '9') return (c-'0');
//   return -1;
// }

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

// llong POW(llong a, llong b){
//   if(b == 0) return 1;
//   else{
//     if(b%2 == 0) return POW(a * a % MOD, b / 2) % MOD;
//     else return a * POW(a * a % MOD, b / 2) % MOD;
//   }
// }

int main(){
  string a, b;
  cin >> a >> b;
  for(int i=0; i<3; ++i){
    if(a[i] != b[2-i]){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int h, w, n;
	scanf("%d %d %d", &h, &w, &n);
	int sr, sc;
	scanf("%d %d", &sr, &sc);
	char s[200005], t[200005];
	scanf("%s%s", s, t);
	int i;
	int l, r, u, d;
	l = 1;
	u = 1;
	d = h;
	r = w;
	for (i = n - 1; i >= 0; i--)
	{
		if (i < n - 1)
		{
			if (t[i] == 'U' && d < h)
				d++;
			if (t[i] == 'D' && u > 1)
				u--;
			if (t[i] == 'L' && r < w)
				r++;
			if (t[i] == 'R' && l > 1)
				l--;
		}
		if (s[i] == 'U')
			u++;
		if (s[i] == 'D')
			d--;
		if (s[i] == 'R')
			r--;
		if (s[i] == 'L')
			l++;
		if (r<l || u>d)
		{
			printf("NO\n");
			return 0;
		}
	}
	if (u <= sr && sr <= d && l <= sc && sc <= r)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)



int main() {
  ll K;
  cin >> K;
  vector<ll> a(1000001);
  //vector<vector<int>> data(3, vector<int>(4));
  a[0] = 7;
  rep(i, K){
    if(i==0) a[0]=7;
    else{
      a[i] = (a[i-1] * 10 + 7) % K;
    }
  }
  rep(i, K) {
    if(a[i]%K==0){
      cout << i+1 << endl;
      return 0;
    }
  }  
  cout << "-1" << endl;
  return 0;
}


Measured memory_bytes: 11168
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
const int INF = 1 << 30;

int main() {
    int N; cin >> N;
    priority_queue<P, vector<P>, greater<P>> que;
    rep(i, N) {
        int X, L;
        cin >> X >> L;
        que.emplace(X + L, X - L);
    }
    int now = -INF;
    int ans = 0;
    while(!que.empty()) {
        auto[end, start] = que.top();
        que.pop();
        if(now <= start) {
            ans++;
            now = end;
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 4260
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int main() {
    int N;cin>>N;
    vector<int> a(N,0);
    rep(i,N) cin>>a[i];

    deque<int> dq;
    rep(i,N) {
        int plc = lower_bound(dq.begin(),dq.end(),a[i]) - dq.begin();
        if(plc==0) {
            dq.push_front(a[i]);
        } else {
            dq[plc-1] = a[i];
        }
    }
    cout<<dq.size()<<endl;
}

Measured memory_bytes: 4056
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;
int N,M;
int main() {
	cin>>N>>M;





	cout<<(N-1)*(M-1)<<endl;

	return 0;
}


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

using ll = long long;
using pint = pair<int, int>;

const ll INF = 1e12;
const ll MOD = 1e9 + 7;

ll N, K;

double probability(int dice)
{
    ll point = dice;
    double res = 1 / (double)N;
    while (point < K)
    {
        point *= 2;
        res /= (double)2.0;
    }
    return res;
}

int main()
{
    cin >> N >> K;
    double ans = 0;
    for (int i = 1; i < N + 1; ++i)
    {
        ans += probability(i);
    }
    printf("%.12f\n", ans);
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Maximum Sum
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		int n, k, sum = 0, max1 = 0, max2 = 0;
		int[] list;

		while (!(line = br.readLine()).equals("0 0")) {
			n = Integer.parseInt(line.substring(0, line.indexOf(' ')));
			k = Integer.parseInt(line.substring(line.indexOf(' ') + 1));
			list = new int[n];
			for (int i = 0; i < n; i++) {
				list[i] = Integer.parseInt(br.readLine());
			}
			max1 = 0;
			for (int i = 0; i < k; i++) {
				max1 += list[i];
			}
			sum = max1;
			for (int i = k; i < n; i++) {
				sum = sum - list[i - k] + list[i];
				if (sum > max1)
					max1 = sum;
			}
			System.out.println(max1);
		}
	}
}

Measured memory_bytes: 29540
#include "bits/stdc++.h"
using namespace std;

int main(void) {
	int days, num;
	cin >> days >> num;
	int l;
	int i = 0;
	int a[num];
	while (i < num) {
		cin >> l;
		a[i] = l;
		i++;
	}
	for (int i = 0; i < num; i++)
		days -= a[i];
	if (days < -1)
		days = -1;
	cout << days << endl;
	return 0;
}

Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,l,sum=0;;
  cin>>n>>l;
  int a[n];
  for(int i=1;i<=n;i++){
    a[i]=l+i-1;
    sum+=l+i-1;
}
  int j,m=1e7;
  for(int i=1;i<=n;i++){
    if(m>abs(a[i])){
      m=abs(a[i]);
       j=a[i];
  }
  }
  cout<<sum-j<<endl;
}

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


int main(){
    ll N, M, ans=0;
    cin >> N >> M;
    vector<pair<ll, ll>> AB;
    rep(i, N){
        int A, B;
        cin >> A >> B;
        AB.push_back({A, B});
    }
    sort(AB.begin(), AB.end());
    for(auto ab: AB){
        if(ab.second<=M){
            M-=ab.second;
            ans+=ab.first*ab.second;
        }
        else{
            ans+=M*ab.first;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2548
#include<iostream>
#include<algorithm>
using namespace std;
int gcdfunk(long long int, long long int);

int main(){
  long long int a, b;
  int gcd[50], lcm[50];
  int i=0;
  while(1){
    cin >> a >> b;
    if(cin.eof()){
      break;
    }
    gcd[i]= gcdfunk(a, b);
    lcm[i]= (a*b)/ gcdfunk(a,b);
    i++;
  }
  for(int j=0;j<i;j++){
    cout << gcd[j] << " " << lcm[j] << endl;
  }
  return 0;
}

int gcdfunk(long long int x, long long int y){
  int z, work=0;
  if(x<y){
    work=x;
    x=y;
    y=work;
  }
  while(1){
    z=x%y;
    if(z==0){
      break;
    }else{
      x=y;
      y=z;
    }
  }
  return y;
}

Measured memory_bytes: 3028
import java.util.Scanner;

/**
 * A - Takoyaki
 * 高橋君はたこ焼きが好きです。
 * たこ焼き器を使うと、1 度に最大で X 個のたこ焼きを作ることができます。
 * これにかかる時間は作る個数によらず T 分です。
 * N 個のたこ焼きを作るためには何分必要ですか？
 */
public class Main {

    public static void main( String[] args ) {

        // 入力値
        Scanner sc = new Scanner( System.in );
        int n = sc.nextInt();   // 作るたこ焼きの数
        int x = sc.nextInt();   // 一度に作れるたこ焼きの数
        int t = sc.nextInt();   // 1回作るのにかかる時間

        if( n <= x ) System.out.println( t );
        else System.out.println( ( ( int ) Math.ceil( ( double ) n / x ) ) * t );

        sc.close();
    }
}


Measured memory_bytes: 35584
nk = list(map(int, input().split()))
p = list(map(int, input().split()))
s=0
summo=0
l = []
for i in range(1,1001):
    s += i
    l.append(s/i)

r = []
for i in range(nk[0]):
    summo += l[p[i]-1]
    r.append(summo)

ans = 0
for i in range(nk[0]):
    if i-nk[1] >= 0:
        if ans < r[i]-r[i-nk[1]]:
            ans = r[i]-r[i-nk[1]]
    else:
        if ans < r[i]:
            ans = r[i]
print(ans)



Measured memory_bytes: 25604
import java.util.Scanner;
public class Main{
	
	public void solve(){
		Scanner sc = new Scanner(System.in);
		int S;
		S = sc.nextInt();
		
		System.out.println(((S-S%3600)/3600)+":"+((S-(S-S%3600)-(S%60))/60)+":"+(S%60));
	}
	public static void main(String[] args){
		Main obj = new Main();
		obj.solve();
	}
}

Measured memory_bytes: 17304
#encoding:utf-8
d_ary = []
while gets
 d_ary.push $_.to_i
end

i = 0
while i < d_ary.length
 s = 0
 x = d_ary[i]
 width = d_ary[i]
 while x < 600
  length = x**2
  s += length * width
  x += d_ary[i]
 end
 puts s
 i += 1
end

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

long long dp[90];

int main()
{
    char X, Y;
    cin >> X >> Y;
    if (X < Y)
        cout << "<" << endl;
    else if (X == Y)
        cout << "=" << endl;
    else
        cout << '>' << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
main(){
    int i,text,a,b;
    while(scanf("%d",&a)!=EOF){
        scanf("%d",&b);
        i=1;
        a+=b;
        while(a>=10){
            a/=10;
            i++;
        }
    printf("%d\n",i);
}
    return 0;
}


Measured memory_bytes: 2036
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, j, n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;
 
typedef long long i64;
typedef pair<int, int> pi;
 
template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;
 
i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcm(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

struct Edge {
  int to;
  i64 cost;

  Edge(int _to, i64 _cost) : to(_to), cost(_cost) {}
};

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

  int n, w;
  cin >> n >> w;
  vt<int> weight(n), value(n);
  rep(i, 0, n) cin >> weight[i] >> value[i];

  vvt<i64> dp(n + 1, vt<i64>(w + 1, 0));
  rep(i, 0, n) {
    rep(j, 0, w + 1) {
      if(j < weight[i]) dp[i + 1][j] = dp[i][j];
      else dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
    }
  }
  cout << dp[n][w] << endl;
}


Measured memory_bytes: 80256
#include <stdio.h>

int main(void) {
	int A[3][3];
	int _A[3][3] = { {0,0,0}, {0,0,0} };
	for (int i = 0; i < 3; ++i) {// make bingo sheet
		scanf("%d %d %d", &A[i][0], &A[i][1], &A[i][2]);
	}

	// let's bingo
	int n, b;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &b);

		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				if (A[j][k] == b) {
					_A[j][k] = 1;
				}
			}
		}

	}
	//judge
	//line and low
	int jg = 0;
	for (int i = 0; i < 3;  ++i) {
		if ((_A[0][i] && _A[1][i] && _A[2][i])|| (_A[i][0] && _A[i][1] && _A[i][2])) {
			jg = 1;
			break;
		}
	}
	//cross
	if ((_A[0][0] && _A[1][1] && _A[2][2]) || (_A[0][2] && _A[1][1] && _A[2][0])) {
		jg = 1;

	}
	printf(jg == 1 ? "Yes" : "No");


	return 0;
}

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

long long sum[2100][2100];

int check(int i, int j, const vector<string> &fi) {
    int n = (int)fi.size();
    int m = (int)fi[0].size();
    if (i < 0 || i >= n || j < 0 || j >= m) return 0;
    if (fi[i][j] == '#') return 1;
    else return 0;
}

long long solve(vector<string> fi) {
    // sum[a][b] := マス (i, j) であって i+j = a, i <= b を満たす範囲内にある黒マスの個数 (斜め累積和)
    memset(sum, 0, sizeof(sum));
    int n = (int)fi.size();
    int m = (int)fi[0].size();
    for (int ij = 0; ij < n+m-1; ++ij) {
        sum[ij][0] = 0;
        for (int i = 0; i < (n+m)*3; ++i) {
            int j = ij - i;
            int add = 0;
            if (i >= 0 && i < n && j >= 0 && j < m && fi[i][j] == '#') add = 1;
            sum[ij][i+1] = sum[ij][i] + add;
        }
    }
    
    long long res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (fi[i][j] != '#') continue;
            for (int k = 1; k < n+m; ++k) {
                int i2 = i + k;
                int j2 = j - k;
                if (i2 < 0 || i2 >= n || j2 < 0 || j2 >= m) continue;
                if (fi[i2][j2] != '#') continue;
                
                // 対辺が左上方向にあるもの
                {
                    int ij = i+j - k*2;
                    if (ij >= 0) {
                        if (check(i-k, j-k, fi)) ++res; // 直角二等辺三角形
                        if (check(i, j-k*2, fi)) ++res; // 直角二等辺三角形
                        
                        int a = max(i-k+1, 0);
                        int b = max(i, 0);
                        if (a <= b) res += (sum[ij][b] - sum[ij][a]) * 2; // それ以外
                    }
                }
                
                // 対辺が右下方向にあるもの
                {
                    int ij = i+j + k*2;
                    if (ij <= n+m-2) {
                        if (check(i+k, j+k, fi)) ++res; // 直角二等辺三角形
                        if (check(i+k*2, j, fi)) ++res; // 直角二等辺三角形
                        
                        int a = i+k+1;
                        int b = i+k*2;
                        res += (sum[ij][b] - sum[ij][a]) * 2; // それ以外
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> input(H);
    for (int i = 0; i < H; ++i) cin >> input[i];
        
    long long res = 0;
    res += solve(input);

    // 盤面を左右反転
    for (int i = 0; i < H; ++i) reverse(input[i].begin(), input[i].end());
    res += solve(input);
        
    cout << res / 2 << endl;
}


Measured memory_bytes: 34944
m,d = map(int,input().split())
c = 0
for i in range(22, d + 1):
  a = str(i)
  if (int)(a[1]) >= 2:
    b = (int)(a[1]) * (int)(a[0])
    if b>0 and b<=m:
      c += 1
print(c)


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define rrep(i,n) for(int (i)=1;i<=(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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;};

int n;
vector<int> a;
vector<P> b;

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	
	cin >> n;
	int prev = -1;
	rep(i, n) {
		int A;
		cin >> A;
		if(A != prev) {
			a.push_back(A);
			b.push_back(P(A, b.size()));
			prev = A;
		}
	}
	sort(all(b), greater<>());
	if(a.size() == 1) {
		if(a[0] == 0) cout << 0 << endl;
		else cout << 1 << endl;
		return 0;
	} 

	int ans = 1;
	int now = 0;
	
	rep(i, b.size()) {
		int id = b[i].second;
		if(id == 0) {
			if(a[id] > a[id + 1]) now++;
		} else if(id == a.size() - 1) {
			if(a[id - 1] < a[id]) now++;
		} else {
			if(a[id - 1] < a[id] && a[id] > a[id + 1]) now++;
			if(a[id - 1] > a[id] && a[id] < a[id + 1]) now--;
		}
		if(i == b.size() - 1 || b[i].first != b[i + 1].first) {
			chmax(ans, now);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll ;
typedef double db;
const double pi = 3.141592654;
#define pb         push_back
#define forab(i,a,b)       for(int i=(a);i<=(b);i++)
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define pcase(z,x)     printf("Case %ld: %lld\n",z,x)
#define nw	 "\n"
#define mod 1000000007

int main(void)
{
	CIN;
	ll tc,l,k,sum=0,x=0,y,z=0,m=1,n=0,ans=0,cnt=0;
	string s,t;
	cin>>s>>t;
	char p[100];
	for(ll i=0,j=0;j<s.size();i+=2,j++){
		p[i]=s[j];
	}
	for(ll i=1,j=0;j<t.size();j++,i+=2){
		p[i]=t[j];
	}
	for(ll i=0;i<s.size()+t.size();i++)
		cout<<p[i];
	


}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
static const int MAX_N = 1e5;
int N;
vector<int> g[MAX_N];
int dist[2][MAX_N], id;

// parは初期値のときに弾く
void dfs(int idx, int par = -1)
{
    if (~par) { // par=-1のときはfalse
        dist[id][idx] = dist[id][par] + 1;
    }
    for (auto to : g[idx]) {
        if (to != par) {
            dfs(to, idx);
        }
    }
}

signed
main()
{
    cin >> N;
    rep(i, N - 1)
    {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    id = 0; // Fennec
    dfs(0);
    id = 1; // Snuke
    dfs(N - 1);
    int res = 0;
    rep(i, N)
    {
        if (dist[0][i] <= dist[1][i]) {
            ++res;
        }
    }
    if (res >= (N + 2) / 2) {
        puts("Fennec");
    } else {
        puts("Snuke");
    }
    return 0;
}

Measured memory_bytes: 11136
n, k = map(int, input().split())

if n >= k:
  if n%k >= k-n%k:
    print(k-n%k)
  else:
    print(n%k)
  exit()
  
if n < k:
  if k-n >= n:
    print(n)
  else:
    print(k-n)
  

Measured memory_bytes: 3068
#include <iostream>
#include <cstdlib>

using namespace std;

int main(void){
  int W, a, b;
  int dist1, dist2;
  cin >> W >> a >> b;

  if((W+a-b)  < 0){
    dist1 = W+a-b;
  }

  if((W+b-a) < 0){
    dist2 = W+b-a;
  }
    cout << max(abs(dist1), abs(dist2)) << endl; 
}

Measured memory_bytes: 256
if __name__ == "__main__":
    N = int(input())

    mul = list()
    for i in range(1, 10):
        for j in range(1, 10):
            tmp = i * j
            if tmp not in mul:
                mul.append(tmp)
    
    if N in mul:
        print("Yes")
    else:
        print("No")


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

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

	j = 1;
	for(int i=0; i<N; i++){

		A = j*2;
		B = j+K;
		if( A > B ){
		j = B;
		}
		else{
			j = A;
		}
	}
	cout << j << endl;
}


Measured memory_bytes: 256