akhauriyash/Code-Regression huggingface dataset:
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n, m, s, t;
  cin >> n >> m >> s >> t;
  s--, t--;

  vvP toe(n), tos(n);
  rep(i, m) {
    ll u, v, a, b;
    cin >> u >> v >> a >> b;
    u--, v--;
    toe[u].emplace_back(a, v);
    toe[v].emplace_back(a, u);
    tos[u].emplace_back(b, v);
    tos[v].emplace_back(b, u);
  }

  priority_queue<P, vP, greater<P>> pque;
  vll diste(n, INF);
  diste[s] = 0;
  pque.emplace(0, s);
  while (!pque.empty()) {
    P p = pque.top();
    pque.pop();
    ll du, u;
    tie(du, u) = p;
    if (diste[u] < du) continue;
    for (auto e : toe[u]) {
      ll c, v;
      tie(c, v) = e;
      if (diste[v] > du + c) {
        diste[v] = du + c;
        pque.push({du + c, v});
      }
    }
  }

  vll dists(n, INF);
  dists[t] = 0;
  pque.emplace(0, t);
  while (!pque.empty()) {
    P p = pque.top();
    pque.pop();
    ll du, u;
    tie(du, u) = p;
    if (dists[u] < du) continue;
    for (auto e : tos[u]) {
      ll c, v;
      tie(c, v) = e;
      if (dists[v] > du + c) {
        dists[v] = du + c;
        pque.push({du + c, v});
      }
    }
  }

  rep(i, n) pque.emplace(diste[i] + dists[i], i);

  rep(i, n) {
    while (!pque.empty()) {
      if (pque.top().second < i) {
        pque.pop();
      } else {
        ll ans = 1000000000000000;
        cout << ans - pque.top().first << endl;
        break;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 19828
import math
a,b,x=map(int,input().split())
s=a*a*b
if x>=s/2:
  tmp=(s-x)/a/a*2
  print(math.degrees(math.atan(tmp/a)))
else:
  tmp=x/a/b*2
  print(90.0-math.degrees(math.atan(tmp/b)))

Measured memory_bytes: 9228
import java.util.*;

/**
 * D
 */
public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int max_v, min_v;
        int n = sc.nextInt();

        int array[] = new int[n];

        for(int i=0; i<n; i++) {
            array[i] = sc.nextInt();
        }

        sc.close();

        max_v = array[1] - array[0];
        min_v = array[0];

        for(int i=1; i<n; i++) {

            if(array[i] - min_v > max_v) {
                max_v = array[i] - min_v;
            }

            if(array[i] < min_v) {
                min_v = array[i];
            }

        }

        System.out.println(max_v);

    }
}


Measured memory_bytes: 101192
#include<bits/stdc++.h>
#define int ll
//{ PXH612
using namespace std;
#define ll long long
#define db double
#define pp pair<int,int>
#define x first
#define y second

#define false(x) if(!(x))
template<typename A,typename B>bool Min(A &a,B b){if(a<=b) return 0;a=b;return 1;}
template<typename A,typename B>bool Max(A &a,B b){if(a>=b) return 0;a=b;return 1;}
#define in ({ll x=0;int o=0,c=char(),t=0;for(;!isdigit(c)&&t<1000;c=getchar(),t++) o=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';o?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})

#define FOR(i,a,b) for(int i=a,ENDFOR=b;i<=ENDFOR;i++)
#define ROF(i,a,b) for(int i=b,ENDFOR=a;ENDFOR<=i;i--)
#define RR(x,a,b) {cout<<#x<<": ";FOR(_,a,b) cout<<x[_]<<" ";cout<<"\n";}
#define rr(x) " "<<#x<<'='<<(x)<<" "

#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define vn(a) (int)a.size()-1

#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define mu(x) (1ll<<x)
#define bitnum(x) __builtin_popcountll(x)

#define segg(a,b) (abs(a-b)+1)
#define midd(a,b) (a+(b-(a))/2)
#define mems(x,a) memset(x,a,sizeof x)
#define open(a) freopen(a,"r",stdin)
#define shut(b) freopen(b,"w",stdout)
//}/////////////////////////////////////////////////////}

const int N=2e5+5;
int n;
int a[N],b[N];

void RRAC()
{
    vector<int> rr;
    FOR(i,1,n) rr.pb(a[i]);
    FOR(i,1,n) rr.pb(b[i]);
    sort(rr.begin(),rr.end());
    rr.erase(unique(rr.begin(),rr.end()),rr.end());
    FOR(i,1,n) a[i]=lower_bound(rr.begin(),rr.end(),a[i])-rr.begin()+1;
    FOR(i,1,n) b[i]=lower_bound(rr.begin(),rr.end(),b[i])-rr.begin()+1;
}
vector<int> v[N];
int f[N];
main()
{
    //open("robot.inp");
    n=in;
    FOR(i,1,n)
    {
        int x=in,y=in;
        a[i]=x-y;
        b[i]=x+y;
    }
    RRAC();
   // FOR(i,1,n) cout<<rr(i) rr(a[i]) rr(b[i]) "\n";


    FOR(i,1,n) v[b[i]].pb(i);
    FOR(i,1,2*n)
    {
        Max(f[i],f[i-1]);
        VEC(j,v[i]) Max(f[i],f[a[j]]+1);
    }
    cout<<f[2*n];
}


Measured memory_bytes: 11988
#include <iostream>
#include <array>
#include <algorithm>
using namespace std;
int main(void){
    // 配列初期化
    array<array<array<int,10>, 3>, 4>  s;
    for(int i=0; i<4; i++)
        for(int j=0; j<3; j++)
            s.at(i).at(j).fill(0);
    
    // 入退去情報入力と情報更新
    int n, b, f, r, v;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> b >> f >> r >> v;
        s.at(b-1).at(f-1).at(r-1) += v;
    }
    
    // 結果出力
    for(int i=0; i<4; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<10; k++)
                cout << ' ' << s.at(i).at(j).at(k);
            cout << endl;    
        }
        if(i<3)
            cout << "####################" << endl;
    }
    return 0;
}


Measured memory_bytes: 3068
#include<stdio.h>

int main(void) {
  char s[11];
  scanf("%s", &s);

  if (s[0] == 'S') printf("Cloudy");
  if (s[0] == 'C') printf("Rainy");
  if (s[0] == 'R') printf("Sunny");

  return 0;
}


Measured memory_bytes: 128
// -*- mode:c++; coding:utf-8; indent-tabs-mode:nil; -*-
// ALDS1_3-C: Doubly Linked List

#include <cassert>
#include <cstdio>

template <typename T>
class doubly_linked_list {
  struct node {
    node* prev_;
    node* next_;
    T x_;
  };
  node sentinel_;
public:
  doubly_linked_list() {
    sentinel_.prev_ = sentinel_.next_ = &sentinel_;
  }
  void insert_elem_to_first(const T& x) {
    node* np = new node();
    np->x_ = x;
    np->prev_ = &sentinel_;
    np->next_ = sentinel_.next_;
    np->prev_->next_ = np;
    np->next_->prev_ = np;
  }
  void delete_first_elem(const T& x) {
    delete_node(search_first_elem(x));
  }
  void delete_first_node() {
    delete_node(sentinel_.next_);
  }
  void delete_last_node() {
    delete_node(sentinel_.prev_);
  }
private:
  void delete_node(node* np) {
    if (np) {
      np->next_->prev_ = np->prev_;
      np->prev_->next_ = np->next_;
      delete np;
    }
  }
  node* search_first_elem(const T& x) const {
    node* np = sentinel_.next_;
    for (;np != &sentinel_; np = np->next_) {
      if (np->x_ == x) return np;
    }
    return nullptr;
  }
public:
  void print(const char* sep=" ") const {
    const char* out_sep = "";
    for (const node* np = sentinel_.next_; np != &sentinel_; np = np->next_) {
      printf("%s%d", out_sep, np->x_);
      out_sep = sep;
    }
    puts("");
  }
};

int main(void) {
  unsigned int n;
  std::scanf("%d", &n);
  doubly_linked_list<int> list;

  for (auto i = 0U; i < n; ++i) {
    char buf[11+1]; // max_length == "deleteFirst".size()+1('\0')
    int x;
    std::scanf("%11s", buf);
    if (buf[0] == 'i') { // insert x
      std::scanf("%d", &x);
      list.insert_elem_to_first(x);
    } else if (buf[6] == 'F') { // deleteFirst
      list.delete_first_node();
    } else if (buf[6] == 'L') { // deleteLast
      list.delete_last_node();
    } else { // (buf[6] == '\0') // delete x 
      std::scanf("%d", &x);
      list.delete_first_elem(x);
    }
  }
  list.print();

  return 0;
}
// end

Measured memory_bytes: 33960
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) S.push_back(1);
        else S.push_back(0);
    }
    return S;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int> > list(n, vector<int>(n, -1));
    rep1(i, n){
        int a;
        cin >> a;
        rep1(j, a){
            int x, y;
            cin >> x >> y;
            x--;
            list[i][x] = y;
        }
    }
    ll ans = 0;
    for (int bit=0; bit<(1<<n); ++bit){
        vector<int> S = IntegerToVector(bit, n);
        ll cnt = 0;
        bool judge = true;
        rep1(i, n){
            if (S[i]==1) cnt++;
            rep1(j, n){
                if (S[i]==1) if ((list[i][j]==0 && S[j]==1) || (list[i][j]==1 && S[j]==0)) judge = false;
            }
        }
        if (judge) ans = max(ans, cnt);
    }
    cout << ans << endl;
    //printf("%.12f", ans);
}

Measured memory_bytes: 3628
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <bitset>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = Mint(2).pow(n);
  Mint pow(long long n) const {
    if (n==0) return Mint(1);
    Mint y = pow(n>>1); // pow(n/2)を計算する
    y *= y;
    if (n%2==1) y *= *this;
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return a.pow(mod-2);
  }

  Mint& operator /= (const Mint &a) {
    x *= modinv(a).x;
    x %= mod;
    return *this;
  }

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    Mint one = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= (i + one);
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

int main() {
  std::string s;
  std::cin >> s;
  int n = s.length();
  std::vector<std::vector<Mint> > dp(n+4, std::vector<Mint>(4, 0));
  dp[0][0] = 1;
  for (int i=0; i<n; i++) {
    // printf("i=%d\n", i);
    // 状態を動かさない場合
    if (s[i]=='?') {
      for (int j=0; j<4; j++) {
        Mint add = dp[i][j];
        add *= Mint(3);
        dp[i+1][j] += add;
      }
    } else {
      for (int j=0; j<4; j++) {
        dp[i+1][j] += dp[i][j];
      }
    }
    // printf("moving state\n");
    // 状態を動かす場合
    if (s[i]=='?') {
      for (int j=0; j<3; j++) {
        dp[i+1][j+1] += dp[i][j];
      }
    } else {
      if (s[i]=='A') {
        dp[i+1][1] += dp[i][0];
      } else if (s[i]=='B') {
        dp[i+1][2] += dp[i][1];
      } else if (s[i]=='C') {
        dp[i+1][3] += dp[i][2];
      }
    }
  }
  // printf("end\n");
  std::cout << dp[n][3].x << std::endl;
  return 0;
}

Measured memory_bytes: 9980
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
//typedef pair<ll,ll> P;
//#define rep(i,a,b) for(ll i=a ; i*i<=b ; i++)
const int max_n = 1e5;
const ll mod = 1e9+7;
typedef long double ld;
vector<ll> v[200000];

vector<ll> divisor(ll n){
  vector<ll> res;
  for(int i=1 ; i*i<=n ; i++){
    if(n%i == 0){
      res.pb(i);
      if(i!=n/i) res.pb(n/i);
    }
  }
  return res;
}
int main(){
  ll n,m;
  cin >> n >> m;
  ll ans = 1;
  vector<ll> v = divisor(m);
  /*for(ll i=1 ; i<=m ; i++){
    if(m%i==0){
      if(n<=m/i) ans = i;
      else break;
    }
  }*/
  for(ll i=0 ; i<v.size() ; i++){
    if(n<=m/v[i]) ans = max(ans, v[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4992
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int main(void)
{   
    int n, k;
    scanf("%d %d", &n, &k);
    int l[n];
    for (int i=0; i < n; i++) scanf("%d", &l[i]);

    for (int i=0; i < n-1; i++){
        for (int j=i+1; j < n; j++){
            if (l[i] < l[j]){
                int tmp = l[i];
                l[i] = l[j];
                l[j] = tmp;
            }
        }
    }

    int res = 0;
    for (int i=0; i < k; i++) res += l[i];

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

    return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstring>

int main()
{
	int a, b;
	while (scanf("%d %d", &a, &b) != EOF)
	{
		int s = a+b;
		int ans = 1;
		while (s > 9)
		{
			s /= 10;
			++ans;
		}
		printf("%d\n", ans);
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <boost/algorithm/string/join.hpp>
#include <boost/range/irange.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::irange;
using boost::algorithm::join;

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

typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<double,double> pdd;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<int> vi;
typedef vector<pair<int, int > > vii;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vll> vvll;

constexpr ll MOD = 1e9+7;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/4;
constexpr int INF=inf<int>;
constexpr ll LINF=inf<ll>;

#define Sort(x) sort(begin(x),end(x))
#define Reverse(x) reverse(begin(x),end(x))
#define ABS(a,b) ((a)<(b)?(b)-(a):(a)-(b))
#define nbit(n) (1ull<<(n))
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,(v).size())

// sort(begin(x), end(x), greater<ll>());
// lower_bound(a.begin(), a.end(), val): a[i] ≥ valである最左の位置
// upper_bound(a.begin(), a.end(), val): a[i] > valである最左の位置

// Returns minimum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmin(T& a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}

// Returns maximum of a and b.
// If a is less b, a is set to b.
template<typename T>
T chmax(T& a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}

template <typename T>
void dumpContents(const T& v, const string& msg)
{
  cerr << "### " << msg << " ###\n";
  for (const auto& x : v) {
    cerr << x << " ";
  }
  cerr << endl;
}

struct before_main_function {
  before_main_function() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(20)<<fixed;
    #define endl "\n"
  }
} before_main_function;

// ========== end of template ==========

int main(int argc, char** argv) {
  string S, T;
  cin >> S >> T;
  cout << (T+S) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*
int digts (int n) {
    int sum =0;
    while (n>0) {
      int dig  = n%10;
      sum = sum + dig;
      n = n/10;
    }
    return sum;
  }*/
int main () {
  int N, A, B; cin >>N >> A >>B;
  int res = 0;
  
  for ( int i=1; i<=N; i++) {
    int sum =0, t=i;
    for ( int j=0;j<5 ;j++) {
      sum += t%10;
      t /=10;
    }
    if ( sum >= A && sum <= B) res += i;
  }
  cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string aa,bb;
    cin>>aa;
    cin>>bb;
    int ct=0,i;
    for( i=0;i<3;i++)
    {
        if(aa[i]==bb[i])
        {
           ct++;

        }

        //cout<<"*"<<endl;
    }
  cout<<ct;



}


Measured memory_bytes: 256
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

il =[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K = iin()

print(il[K-1])

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

ll cost[105], value[105];
ll olddp[100005], newdp[100005];

int main(){
    
    ll n, w; scanf("%lld %lld", &n, &w);
    for(ll i = 1; i <= n; i++)
        scanf("%lld %lld", &cost[i], &value[i]);
    
    for(ll i = 1; i <= n; i++){
        for(ll j = 0; j+cost[i] <= w; j++)
            newdp[j+cost[i]] = max(newdp[j+cost[i]], olddp[j] + value[i]);
        for(ll j = 0; j <= w; j++)
            olddp[j] = newdp[j];
    }
    
    ll res = 0;
    for(ll i = 0; i <= w; i++)
        res = max(res, olddp[i]);
    printf("%lld\n", res);
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define F first
#define S second
typedef pair<int, int> P;
const int N = 30 + 5, INF = 0x3f3f3f3f;
inline int read() {
	int x = 0, f = 0; char ch = 0;
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
bool cmp(P a, P b) {
	return b.F * (a.S + 1) < a.F *(b.S + 1) ;
}
vector <P> a; vector <int> b;
int f[N];
signed main() {
	int n = read(), T = read();
	for (int i = 1; i <= n; i++) {
		int x = read(), y = read();
		if (x) a.pb(make_pair(x, y));
		else b.pb(y + 1);
	}
	sort(a.begin(), a.end(), cmp);
	sort(b.begin(), b.end());
	for (int i = 1; i < b.size(); i++) b[i] += b[i - 1];
	for (int i = 1; i <= 30; i++) f[i] = T + 1;
	for (int i = 0; i < a.size(); i++)
		for (int j = 30; j; j--)
			f[j] = min(f[j], (f[j - 1] + 1) * (a[i].F + 1) + a[i].S);
	int ans = 0;
	for (int i = 0; i <= 30; i++) 
		if (f[i] <= T) ans = max(ans, i + (b.empty() ? 0 : upper_bound(b.begin(), b.end(), T - f[i]) - b.begin()));
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 6384
#pragma GCC optimize("O3", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

signed main() {
	int n; cin >> n;
	vector<int> cnt(n, 0); // 各数が何個あるか
	for (int i = 0; i < n; ++i) {
		int ai; cin >> ai;
		++cnt[--ai];
	}
	vector<int> stock(n + 1, 0); // i個ある数の種類
	for (int i = 0; i < n; ++i)
		++stock[cnt[i]];
	vector<int> ttl(n + 1, 0); // i個以上ある数の種類
	ttl[n] = stock[n];
	for (int i = n - 1; i >= 0; --i)
		ttl[i] = ttl[i + 1] + stock[i];
	for (int k = 1; k <= n; ++k) {
		if (ttl[1] < k) {
			cout << 0 << endl;
			continue;
		}
		ll tmp_sum = ttl[1];
		bool f = false;
		for (int i = 1;i < (n / k) ; ++i) {
			tmp_sum += ttl[i + 1];
			if (tmp_sum < (i + 1) * (ll)k) {
				cout << i << endl;
				f = true;
				break;
			}
		}
		if (f) continue;
		cout << (n / k) << endl;
	}

	return 0;
}

Measured memory_bytes: 4352
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <vector>
 
using namespace std;
typedef long long ll;
#define MAX_N (100010)
ll dp[MAX_N][2];		// dp[i][j] = i番目までで、i番目をj余らせた時の最大のペア

ll solve( ll A[], int N ) {
    ll ans = 0;
    if ( A[0] ) {
	if ( A[0] % 2 ) {	// 奇数
	    dp[0][1] = A[0] >> 1;
	}
	else {			// 偶数
	    dp[0][0] = A[0] >> 1;
	    dp[0][1] = ( A[0] - 1 ) >> 1;
	}
    }
 
    for ( int i = 1; i < N; i++ ) {
	if ( A[i] ) {
	    ll pre_max = max( dp[i-1][0], dp[i-1][1] );
	    if ( A[i] % 2 ) {	// 奇数
		dp[i][0] = pre_max + ( (A[i] - 1 ) >> 1 );
		dp[i][1] = pre_max + ( A[i] >> 1 );
		if ( dp[i-1][1] ) {
		    dp[i][0] = max( dp[i][0], dp[i-1][1] + 1 + ( ( A[i] - 1 )  >> 1 ) );
		}
	    }
	    else {		// 偶数
		dp[i][0] = pre_max + ( A[i] >> 1 );
		dp[i][1] = pre_max + ( ( A[i] - 1 ) >> 1 );
		if ( dp[i-1][1] ) {
		    dp[i][1] = max( dp[i][1], dp[i-1][1] + 1 + ( ( A[i] - 1 ) >> 1 ) );
		}
	    }
	}
	else {
	    dp[i][0] = dp[i-1][0];
	    dp[i][1] = 0;
	}
    }
    
    for ( int i = 0; i < N; i++ ) {
	ans = max( ans, max( dp[i][0], dp[i][1] ) );
    }

    return ans;
}
int main()
{
    int N;

    ll A[MAX_N];
    ll B[MAX_N];
    ll ans = 0;
    scanf("%d", &N);
    for ( int i = 0; i < N; i++ ) {
	scanf("%lld", &A[i]);
	B[N-1-i] = A[i];
    }

    ans = solve( A, N );
    for ( int i = 0; i < N; i++ ) {
	dp[i][0] = dp[i][1] = 0;
    }
    ans = max( ans, solve( B, N ) );

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


Measured memory_bytes: 3328
N,M = map(int,input().split())
*A, = map(int,input().split())
S = [0]*(N+1)
for i in range(N):S[i+1]=(S[i]+A[i])%M
ans = 0
c = {}
for s in S:c[s] = c.get(s,0)+1
for n in c.values():ans+=n*(n-1)//2
print(ans)

Measured memory_bytes: 16272
from collections import deque
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
d=deque(A)
import time
l=[]
if K%2==0 or (K%2==1 and A[0]>=0):
  for i in range(K//2):
    if d[0]*d[1]>d[-1]*d[-2] and (i==K//2-1 or (len(d)>2 and  d[2]>0)):
      l.append(d.popleft())
      l.append(d.popleft())
    else:
      l.append(d.pop())
      l.append(d.pop())
  if K%2==1:
    l.append(d[0])
else:
  for i in range(K):
    l.append(d.popleft())
      
ans=1
for i in l:
  ans*=i
  ans%=10**9+7
print(ans)

Measured memory_bytes: 32360
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# C^2 と A*Bの比較
Q = ir()
answer = []
for _ in range(Q):
    a, b = lr()
    if a > b:
        a, b = b, a
    if a == b:
        ans = (a-1) * 2
    elif b == a+1:
        ans = 2 * (a-1)
    elif b > a + 1:
        c = int((a*b-1) ** .5) - 2
        while (c+1) ** 2 < a*b:
            c += 1
        # c は aより大きい
        if c * (c+1) >= a * b:
            ans = 2 * c - 2
        else:
            ans = 2 * c - 1
    answer.append(ans)

print('\n'.join(map(str, answer)))



Measured memory_bytes: 9444
n,k = gets.split.map(&:to_i)
x = gets.split.map(&:to_i)

left = []
right = []
ans = 10 ** 9

n.times do |i|
  if x[i] < 0
    left << x[i].abs
  elsif x[i] > 0
    right << x[i]
  else
    k -= 1
  end
end
if k > 0
  left.reverse!
  if left.empty?
    ans = right[k-1]
  elsif right.empty?
    ans = left[k-1]
  else
    t = [k,left.length+right.length-k+1].min
    l = [left.length,k].min
    r = k - l
    #puts t
    t.times do |i|
      a = left[l-i-1]
      b = right[r+i-1]
      result = a + b + [a,b].min
      #puts l-i-1
      #puts r+i-1
      #puts result
      #puts
      ans = result if result < ans
    end
  end
else
  ans = 0
end
puts ans


Measured memory_bytes: 11788
#include <stdio.h>
 
int main(void){
  long a, b, k;
  scanf("%ld %ld %ld", &a, &b, &k);
  
  if(k > a){
    k = k - a;
  }else{
    a = a - k;
    printf("%ld %ld", a, b);
    return 0;
  }
  if(k > b){
    k = k - b;
    printf("%d %d", 0, 0);
  }else{
    b = b - k;
    printf("%d %ld", 0, b);
  }
 
  return 0;
}

Measured memory_bytes: 128
/*==============================================*\
Codeforces ID:    mdshihab
                                                  |
Name:     Md. Shihabul Minhaz                     |
Study:      CSE, JKKNIU                           |
Address:  Trishal, Mymensingh, Bangladesh         |
                                                  |
 mail:   mdshihabul20171@gmail.com                |
 FB  :   fb.com/mdshihabul.minhaz.7               |
 github: Shihabulminhaz                           |
stopstalk :  mdshihab                             |
                                                  |
@uthor   Md. Shihabul Minhaz (shihab)             |
\*===============================================*/


#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int shihab;
void FI()
{
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\SHIHAB\\Desktop\\input.in","r",stdin);
#endif // ONLINE_JUDGE
}

int main()
{
    fast
    FI(); /// skip this line for compile
    string s1,s2;
    int x;
    cin >> s1 >> s2;
    s1+=s2;
    x = stoi(s1);
    int y = sqrtl(x);
    if(y*y==x) cout << "Yes\n";
    else cout << "No\n";
    return 0;
    //code end
}
//okbye


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RNG(i,from,to) for(int i=(from); i<(int)(to); i++)
#define gcd(i,j) __gcd((i), (j))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vecll;
template<typename S, typename T> string to_string(pair<S, T> p) { return "("+to_string(p.first)+","+to_string(p.second)+")"; }
template<typename T> string to_string(T p[2]) { return "["+to_string(p[0])+","+to_string(p[1])+"]"; }
template<typename T> void println(T e){ cout << to_string(e) << endl; }
template<typename T> void println(const vector<T>& v){ cout << "[";for(const auto& e : v){ cout << to_string(e) << ","; }cout << "]";cout << endl; }
template<typename T> void println(const vector<vector<T>>& vv){ for(const auto& v : vv){ println(v); } }
template<typename Iter> void println(Iter first, Iter last){ for(auto it=first; it != last; it++){ cout << *it << " "; }; cout << endl; }
const ll DVSR = 1e9+7;


int main(int argc, char const *argv[])
{
  ll N, K, cnt = 0;
  cin >> N >> K;
  if (N == 0) {
    cout << 1 << endl;
    return 0;
  }
  while (N) {
    N /= K;
    cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lli long long
#define rep0(i,j) for(int i=0; i<j; i++)
#define all(a) a.begin(), a.end()
using namespace std;
int main(){
    lli n,sum=0, size=0;
    cin >> n;
    vector<lli> vec(n);
    rep0(i,n) {
        cin >> vec[i];
        sum += vec[i];
    }
    rep0(i,n){
        if(size+vec[i] > sum - (size + vec[i])){
            cout << min( 2*(size + vec[i]) - sum, sum - 2*size);
            if(getchar()=='\n'&& getchar()=='\n') return 0;
            return 0;
        }
        size += vec[i];
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define INF 1000000007
#define SEP " "

int     main()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	vector<bool> dp(k+1, false);
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j < n; j++) {
			if (a[j] > i)
				break ;
			if (dp[i-a[j]] == false)
				dp[i] = true;
		}
	}
	if (dp[k] == true)
		cout << "First" << endl;
	else
		cout << "Second" << endl;
}



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

const LL mod = 1e9 + 7;

LL mul(LL a, LL b){return ((a%mod)*(b%mod))%mod;}

struct Mat{
	LL arr[55][55];
	Mat(){memset(arr,0,sizeof(arr));}
	Mat operator * (const Mat &rhs) const{
		Mat ret;
		for (int i = 1; i <= 50; i++){
			for (int j = 1; j <= 50; j++){
				for (int k = 1; k <= 50; k++){
					ret.arr[i][j] += mul(arr[i][k], rhs.arr[k][j]);
					ret.arr[i][j] %= mod;
				}
			}
		}
		return ret;
	}
};

LL n, k;
Mat base;
Mat ans;

Mat fpow(Mat base, LL e){
	Mat ret;
	for (int i = 1; i <= 50; i++) ret.arr[i][i] = 1;
	while (e>0){
		if (e&1) ret = ret * base;
		base = base * base;
		e >>= 1;
	}
	return ret;
}
int main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		ans.arr[i][i] = 1;
		for (int j = 1; j <= n; j++)
			cin >> base.arr[i][j];
	}
	ans = fpow(base, k);
	LL tot = 0LL;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			(tot += ans.arr[i][j]) %= mod;
	cout << tot << '\n';
}


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

int main()
{
  int n;
  cin >> n;
  long long t, a, x, y;
  cin >> t >> a;
  x = t; y = a;
  for (int i = 1; i < n; i++) {
	cin >> t >> a;
	long long l, m;
	if (x%t != 0) {
	  l = x / t + 1;
	}
	else
	{
	  l = x / t;
	}
	if (y % a != 0) {
	  m = y / a + 1;
	}
	else {
	  m = y / a;
	}
	long long k = max(l, m);
	x = k*t;
	y = k*a;
  }
  cout << x + y << endl;
  return 0;
}



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

#define REP(i,b,n) for(int i=b;i<n;i++)
#define REPR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define EACH(i, c) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define BIT(n, b) ((n>>b) & 1)
#define PB push_back
#define MP make_pair

using namespace std;

static const double PI = acos(-1.0);
static const double EPS = 1e-9;
typedef long long ll;
typedef pair<int, int> pii;

int n;
bool vacant[128][64] = {0};

int solve(){
	
	bool dp[128][128][64] = {0};
	
	for(ll i=0; i<n; ++i){
		dp[i][i][0] = true;
	}
	
	for(int d = 1; d <= 30; ++d){
		
		bool sum[128] = {false};
		
		//gather
		for(int i=0; i<n; ++i){
			for(int j=0; j<n; ++j){
			
				dp[i][j][d] |= dp[i][j][d-1];
				sum[j] |= vacant[i][d] && dp[i][j][d-1];	
			}
		}
		
		//distribute
		for(int i=0; i<n; ++i){
			for(int j=0; j<n; ++j){
			
				dp[i][j][d] |= vacant[i][d] && sum[j];
			}
		}
		
		//count
		for(int i=0; i<n; ++i){
			
			int cnt = 0;
			
			for(int j=0; j<n; ++j){	
				cnt += dp[i][j][d];
			}
			
			if(cnt == n){
				return d;
			}
		}
	}
	
	return -1;
}

int main(){
	
	while(cin>>n, n){
		
		memset(vacant, false, sizeof(vacant));
		
		for(int i = 0; i < n; ++i){
			
			int d;
			cin >> d;
			
			for(int j = 0; j < d; ++j){
				int a;
				cin >> a;
				vacant[i][a] = true;
			}
		}
		
		cout << solve() << endl;
	}
	
	return 0;	
}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;


#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

int dx2[2] = {1,0}, dy2[4] = {0,1};
int h,w;
bool dp[85][85][12890];

bool inside(int y,int x)
{
    return 0<=y && y<h && 0<=x && x<w;
}


int main()
{

    cin>>h>>w;
    vector<vector<int>> a(h);
    for (int hh = 0; hh < h; hh++)
    {
        for (int ww = 0; ww < w; ww++)
        {
            int aa;
            cin>>aa;
            a[hh].push_back(aa);
        }
    }
    for (int hh = 0; hh < h; hh++)
    {
        for (int ww = 0; ww < w; ww++)
        {
            int bb;
            cin>>bb;
            a[hh][ww]=abs(a[hh][ww]-bb);
        }
    }
    m0(dp);
    dp[0][0][a[0][0]]=true;
    for (int y = 0; y < h; y++)
    {
        for (int x = 0; x < w; x++)
        {
            for (int v = 0; v < 12805; v++)
            {
                if(dp[y][x][v]==true)
                {
                    for(int i=0;i<2;i++)
                    {
                        int nexty=y+dy2[i];
                        int nextx=x+dx2[i];
                        if(inside(nexty,nextx)==true)
                        {
                            dp[nexty][nextx][abs(v+a[nexty][nextx])]=true;
                            dp[nexty][nextx][abs(v-a[nexty][nextx])]=true;
                        }

                    }
                }
            }
        }
    }
    ll ans=-1;
    for (ll i = 0; i < 12850; i++)
    {
        if(dp[h-1][w-1][i]==true)
        {
            ans=i;
            break;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}

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

int main(void){
    int A,P = 0;
  	int pie_num = 0;
    
    /* 標準入力 */
    cin >> A >> P;
  
  	P += A*3;
  	pie_num = P/2;
  	
    cout << pie_num << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(k < a+1){
			System.out.print(k+1);
		}else{
			if(b-a>2){
				int kc = k-a+1;
				int nok = kc/2;
				if(kc%2==1){
					System.out.print((long)nok*(b-a)+a+1);
				}else{
					System.out.print((long)nok*(b-a)+a);
				}
			}else{
				System.out.print(k+1);
			}
		}
	}
}


Measured memory_bytes: 23764
N = int(input())

cnt = 0
ans = 'No'

for i in range(0, N):
	d1, d2 = map(int, input().split())
	if d1 == d2:
		cnt += 1
	else:
		cnt = 0
	
	if cnt == 3:
		ans = 'Yes'
		break

print(ans)

Measured memory_bytes: 62304
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10; 
int a[N];
int s[N];
int main(){
	int n;
	long long k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	k++;
	int now=1,step=1,res;
	while(!s[now]){
		s[now]=step;
		step++;
		if(step==k+1){
			cout<<now<<endl;
			return 0;
		}
		now=a[now];
	}	
	int c=step-s[now];
//	printf("now=%d c=%d step=%d\n",now,c,s[now]);
	k-=s[now];
	k%=c;
	while(k--){
		now=a[now];
	}
	printf("%d\n",now);
}

Measured memory_bytes: 5320
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int ej=0;
    cin>>n;
    vector<int> value1,value2;
    for(int i=0;i<n;i++)
    {
        int m;
        cin>>m;
        value1.push_back(m);
    }
    value2=value1;
    sort(value1.begin(),value1.end());
    for(int i=0;i<n;i++)
    {
        if(value1.at(i)!=value2.at(i))
        {
            ej++;
        }
    }

    if(ej<=2)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }


}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()

P(K*(K-1)**(N-1))

Measured memory_bytes: 38256
def main():
    from itertools import product

    N = int(input())

    g = []
    for _ in range(N):
        a = int(input())
        t = []
        for _ in range(a):
            x, y = map(int, input().split())
            t.append((x - 1, y))
        g.append(t)

    def is_ok(prd):
        for j, bl in enumerate(prd):
            if bl:
                for x, y in g[j]:
                    if prd[x] != y:
                        return False
        return True

    ans = 0
    for prd in product([0, 1], repeat=N):
        if is_ok(prd):
            ans = max(ans, prd.count(1))
    print(ans)


if __name__ == '__main__':
    main()

# bit演算しようとしてはまった


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main()
{
  int A,B,C,D,L,R;
  cin>>A>>B>>C>>D;
  L=A+B;
  R=C+D;
  if (L>R) cout<<"Left"<<endl;
  else if (L==R) cout<<"Balanced"<<endl;
  else cout<<"Right"<<endl;
  //system("pause");
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

int bit_search(int H, int W, int K, vector<vector<char>> c) {
    int sum = 0;
    vector<vector<char>> d;
    for (int bit_h = 0; bit_h < (1 << H); ++bit_h) {
        for (int bit_w = 0; bit_w < (1 << W); ++bit_w) {
            int black = 0;
            d = c;
            for (int i = 0; i < H; i++) {
                if (bit_h & (1 << i)) {
                    for (int j = 0; j < W; j++){
                        d.at(i).at(j) = '-';
                    }
                }
            }
            for (int j = 0; j < W; j++) {        
                if (bit_w & (1 << j)) {
                    for (int i = 0; i < H; i++) {
                        d.at(i).at(j) = '-';
                    }
                }
            }
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (d.at(i).at(j) == '#') black++;
                }
            }
            if (black == K) sum++;
        }
    }
    return sum;
}

int main(){
    int N, ans = 0;
    cin >> N;
    for (int i = 0; i < 10; i++) {
        if (i * 1000 < N && N <= (i + 1) * 1000) {
            ans = (i + 1) * 1000 - N;
        }
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=0; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define F first
#define S second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;

int main()
{
  int n, l ;
  cin >> n >> l ;
  vector<string> vec(n) ;
  string ans ;
  
  REP(i,n){
    cin >> vec.at(i) ;
  }
  
  sort(ALL(vec)) ;
  
  REP(i,n){
    ans += vec.at(i) ;
  }
  
  cout << ans <<endl ;
    

  return 0 ;
}




Measured memory_bytes: 256
#include <stdio.h>
#define N 13000000
int c[N];
int main(void)
{
    int i, j, k=0, n;
    c[0]=c[1]=1;
    for(i=2;i*i<N;++i) if (!c[i])
        for(j=i*i;j<N;j+=i) c[j]=1;

    while (scanf("%d", &n), n) {
        int a, b;
        if (!c[n]) { puts("0"); continue; }
        for(a=n;c[a];--a);
        for(b=n;c[b];++b);
        printf("%d\n", b-a);
    }
    return 0;
}

Measured memory_bytes: 51392
#include "bits/stdc++.h"
using namespace std;
using lint = long long;
#define low lower_bound
#define upp upper_bound
#define rep(i, n) for (lint i = 0; i < lint(n); ++i)
#define Rep(i, n) for (lint i = lint(n); i >= 0; --i)
#define all(vec) (vec).begin(), (vec).end()
#define cend printf("\n");
#define prique(T) priority_queue<T, vector<T>, greater<T>>
#define prique2(T) priority_queue<T>

struct edge { int to; double cost; };
using P = pair<lint, lint>;
using D = pair<double, double>;
using DI = pair<double, int>;
//const lint mod = 998244353LL;
const lint mod = 1000000007LL;
const lint inf = 3LL * mod * mod;

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

lint modpow(lint x, lint n, lint m) {
	lint ans = 1;
	while (n > 0) {
		if (n & 1) {
			ans *= x;
			if (m <= ans) ans %= m;
		}
		x *= x;
		if (m <= x) x %= m;
		n >>= 1;
	}
	return ans;
}

lint fact[1000000];
void f_init(lint n) {
	if (1000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1];
		if (mod <= fact[i]) fact[i] %= mod;
	}
	return;
}

lint inver[1000000]; bool inve[100000];
lint inv(lint x) {
	if (x == 0) return 0;
	else if (inve[x]) return inver[x];
	else {
		inve[x] = true;
		return inver[x] = modpow(x, mod - 2, mod);
	}
}

lint comb(lint n, lint r) {
	if (n < r) return 0;
	if (n == r) return 1;
	lint ans = fact[n] * inv(fact[n - r]) % mod * inv(fact[r]) % mod;
	if (ans < 0) return ans + mod;
	return ans;
}

lint nck[1010][1010];
void comb(lint n) {
	rep(i, n + 1) {
		rep(j, i + 1) {
			if (j == 0 || i == j) nck[i][j] = 1;
			else nck[i][j] = nck[i - 1][j - 1] + nck[i - 1][j];
		}
	}
}

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

lint lcm(lint a, lint b) { return a / gcd(a, b) * b; }

bool pri(lint p) {
	for (lint i = 2; i * i <= p; i == 2 ? ++i : i += 2) if (p % i == 0) return false;
	return p > 1;
}

map<lint, lint> factring(lint n) {
	map<lint, lint>ans;
	for (lint i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++ans[i];
		}
	}
	if (n != 1) ++ans[n];
	return ans;
}

double dis(D a, D b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)); }

string s;
lint n, dp[100010][13]; //i桁目までで余りがjとなる整数の個数
int main() {
	cin >> s;
	n = s.size();
	reverse(all(s));
	rep(i, n) {
		if (i == 0) {
			rep(j, 10) {
				if (j == s[0] - '0' || s[0] == '?') dp[0][j] = 1;
				else dp[0][j] = 0;
			}
		}
		else if (s[i] == '?') {
			lint m = modpow(10, i, 13);
			rep(j, 10) {
				rep(k, 13) {
					dp[i][(k + j * m) % 13] += dp[i - 1][k];
					dp[i][(k + j * m) % 13] %= mod;
				}
			}
		}
		else {
			lint m = (s[i] - '0') * modpow(10, i, 13);
			rep(j, 13) {
				dp[i][(j + m) % 13] += dp[i - 1][j];
				dp[i][(j + m) % 13] %= mod;
			}
		}
	}
	cout << dp[n - 1][5] << endl;
}


Measured memory_bytes: 10752
#include <bits/stdc++.h>
using namespace std;
#define lli int
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
#define pl pair<lli,lli>
#define vl vector<lli>
#define vvl vector<vl>
#define INF (lli)1e18

vvl a,dp;
lli n,mx;

lli solve(lli i,lli mask)
{
	if(mask==mx)
		return 1;
	if(dp[i][mask]!=-1)
		return dp[i][mask];
	lli j,ans=0;
	for(j=0;j<n;j++)
	{
		if(((mask&(1<<j))==0)&&(a[i][j]==1))
		{
			ans=ans+solve(i+1,mask|(1<<j));
			if(ans>=mod)
				ans%=mod;
		}
	}
	return dp[i][mask]=ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli i,j;
    cin>>n;
    mx=(1<<n)-1;
    a.resize(n,vl(n));
    dp.resize(n,vl(mx+1,-1));
    for(i=0;i<n;i++)
    	for(j=0;j<n;j++)
    		cin>>a[i][j];
    cout<<solve(0,0)<<"\n";
    return 0;
}

Measured memory_bytes: 180608
#include<bits/stdc++.h>
using namespace std;
void fl()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
int main()
{
	ios::sync_with_stdio(0);
//    fl();
	string a,b;
	cin>>a>>b;
	cout<<b<<a<<endl;
	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/python3

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    x=0
    y=0
    z=0
    cnt=0
    for i in range(N):
        s=str(input())
        if s[0]=='B' and s[-1]=='A':
            x+=1
        if s[0]=='B' and s[-1]!='A':
            y+=1
        if s[0]!='B' and s[-1]=='A':
            z+=1

        
        for j in range(len(s)-1):
            if s[j:j+2]=='AB':
                cnt+=1
    if x==0:
        print(cnt+min(y,z))
    elif y>0 or z>0: print(cnt+(x-1)+min(y,z)+1)
    else: print(cnt+(x-1)+min(y,z))    
        

    
resolve()

Measured memory_bytes: 41584
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring> 
#include<cassert>
#include<cmath>
#include<sstream>
#include<fstream>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	cout<<n-k+1;
}

Measured memory_bytes: 256