akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <map>
using namespace std;

string s;
map<char, pair<char, char> > mp;

int main() {
	//init();
	mp['A'] = {'X', 'Y'};
	mp['X'] = {'\0', 'Z'};
	mp['Y'] = {'X', '\0'};
	mp['Z'] = {'W', 'B'};
	mp['W'] = {'B', 'Y'};
	mp['B'] = {'Y', 'X'};

	cin >> s;
	while (s != "#") {
		char pos = 'A';
		for (auto c:s) {
			if (c == '0') {
				pos = mp[pos].first;
			}
			else if (c == '1') {
				pos = mp[pos].second;
			}
			
			if (pos == '\0') break;
		}
		
		if (pos == 'B') cout << "Yes" << endl;
		else cout << "No" << endl;
		
		cin >> s;
	}
	
	return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
// std::cout << std::setprecision(2) << 3.141; // "3.1"
using ll = long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl
#define all(x) (x).begin(),(x).end()
using ld = double;
using P = complex<ld>;
using G = vector<P>;
const ld pi = acos(-1);
const ld eps = 1e-10;
const ld inf = 1e12;

ld cross(const P& a, const P& b) { return a.real()*b.imag() - a.imag()*b.real(); }
ld dot(const P& a, const P& b) { return a.real()*b.real() + a.imag()*b.imag(); }

using C = pair<ld, P>;
#define rad first
#define pnt second

template <class iter>
std::pair<P, ld> min_ball(iter left, iter right, int seed = 1333) {
    const int n = right - left;

    assert(n >= 1);
    if (n == 1) {
        return {*left, ld(0)};
    }

    std::mt19937 mt(seed);
    std::shuffle(left, right, mt);
    // std::random_shuffle(left, right); // simple but deprecated

    iter ps = left;
    using circle = std::pair<P, ld>;

    auto make_circle_3 = [](const P &a, const P &b, const P &c) -> circle {
        ld A = std::norm(b - c), B = std::norm(c - a), C = std::norm(a - b),
           S = cross(b - a, c - a);
        P p = (A * (B + C - A) * a + B * (C + A - B) * b + C * (A + B - C) * c) / (4 * S * S);
        ld r2 = std::norm(p - a);
        return {p, r2};
    };

    auto make_circle_2 = [](const P &a, const P &b) -> circle {
        P c = (a + b) / (ld)2;
        ld r2 = std::norm(a - c);
        return {c, r2};
    };

    auto in_circle = [](const P &a, const circle &c) -> bool {
        return std::norm(a - c.first) <= c.second + eps;
    };

    circle c = make_circle_2(ps[0], ps[1]);

    // MiniDisc
    for (int i = 2; i < n; ++i) {
        if (!in_circle(ps[i], c)) {
            // MiniDiscWithPoint
            c = make_circle_2(ps[0], ps[i]);
            for (int j = 1; j < i; ++j) {
                if (!in_circle(ps[j], c)) {
                    // MiniDiscWith2Points
                    c = make_circle_2(ps[i], ps[j]);
                    for (int k = 0; k < j; ++k) {
                        if (!in_circle(ps[k], c)) {
                            c = make_circle_3(ps[i], ps[j], ps[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}

int main(){
    // vector<int> ans;
    int n;
    cin >> n;
    G g(n);
    rep(i,n){
            ld x,y;
            cin >> x >> y;
            g[i] = P(x,y);
        }
    auto ans = min_ball(all(g),time(0));
    cout << setprecision(10) <<sqrt(ans.second) << endl;
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FILEIN freopen("in.txt", "r", stdin)
int main()
{
    //FILEIN;
    int a,n,b,cnt=1;
    cin >> n;
    vector< int > s,p(n),q(n);
    for(int i=1;i<=n;i++)   s.push_back(i);
    for(auto &x : p)  cin >> x;
    for(auto &x : q)  cin >> x;
    if(p == s) a = cnt;
    if(q == s) b = cnt;
    cnt++;
    while(next_permutation(s.begin(),s.end())){
        if(s==p) a = cnt;
        if(s == q) b = cnt;
        cnt++;
    }
    cout << abs(a-b) << endl;
    return 0;

}


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

int main()
{
    int n,i;
    cin >> n;
    vector<int> a(n+2);
    vector<int> ans(n+2);
    for (i = 0; i <= n; i++) {
        ans[i] = 0;
    }
    for (i = 2; i <=n; i++) {
        cin >> a[i];
    }
    for(i=2;i<=n;i++){
        ans[a[i]]++;
    }
    for (i = 1; i <= n; i++) {
         cout << ans[i] << " ";
     }
}

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

 using namespace std;
 typedef long long ll;
 #define rep(i, n) for(int i = 0; i < (int)(n); i++)

 int main() {
   int N, a, ans = 0;
   cin >> N;
   rep(i, N) {
     cin >> a;
     ans += a - 1;
   }
   cout << ans << endl;
 }


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

int main() {
  int N , ans = -1 , a = 1 ;
  cin >> N ;
  vector<int> vec(N) ;
  for ( int i = 0 ; i < N ; i++ ){
    cin >> vec.at(i) ;
  }
  for ( int i = 0 ; i < N ; i++ ){
    a = vec.at( a - 1 ) ;
    if ( a == 2 ){
      ans = i + 1 ;
      break ;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  int a=0,w=0,t=0,r=0;
  for(int i=0;i<n;i++)
  {
    string s;
    cin >> s;
    if(s[0]=='A')
      a++;
    else if(s[0]=='W')
      w++;
    else if(s[0]=='T')
      t++;
    else if(s[0]=='R')
      r++;
  }
  cout << "AC x " << a << "\n";
  cout << "WA x " << w << "\n";
  cout << "TLE x " << t << "\n";
  cout << "RE x " << r << "\n";
}

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

int main(){
    int N,M,X;
    cin>>N>>M>>X;
    vector<int> C(N);
    vector<vector<int>> A(N,vector<int>(M));
    for(int i=0;i<N;i++){
        cin>>C.at(i);
        for(int j=0;j<M;j++){
            cin>>A.at(i).at(j);
        }
    }

    long int money =-1;
    unsigned int i=0;
    
    for(i=0;i<(1<<N);i++){
        vector<int> mem(M,0);
        long int temp=0;
        bitset<13> B(i);
        //cout<<B<<endl;
        for(int j=0;j<N;j++){
            if(B.test(j)){
                temp += C.at(j);
                for(int k=0;k<M;k++){
                    mem.at(k) += A.at(j).at(k);
                }
            }
        }
      /*  for(int o=0;o<N;o++){
            cout<<mem.at(o)<<endl;
        }*/

        bool flag =false;
        for(int p=0;p<M;p++){
            if(mem.at(p)<X){
                flag =1;
                break;
            }
        }
        if(!flag){
            if(money>temp || money ==-1){
                money= temp;
            }
            
        }
    }
    cout<<money<<endl; 
}

Measured memory_bytes: 3632
import java.util.Arrays;
import java.util.Scanner;

public class Main {

  static int[] pp;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String X = sc.next();
    int count1 = (int) X.chars().filter(ch -> ch == '1').count();
    int popcntxp1 = count1 + 1;
    int popcntxm1 = Integer.max(count1 - 1, 0);

    pp = new int[N + 1];
    Arrays.fill(pp, -1);
    pp[0] = 0;
    pp[1] = 1;

    int[][] fa = new int[N][2];
    fa[0][0] = (popcntxm1 > 1) ? 1 : 0;
    fa[0][1] = (popcntxp1 > 1) ?  1 : 0;
    for (int i = 1; i < N; i++) {
      fa[i][0] = (popcntxm1 > 1) ? (fa[i - 1][0] * 2) % popcntxm1 : 0;
      fa[i][1] = (fa[i - 1][1] * 2) % popcntxp1;
    }

    int answerxm1 = 0;
    int answerxp1 = 0;

    for (int i = 0; i < N; i++) {
      if (X.charAt(i) == '1') {
        answerxm1 = (popcntxm1 > 1) ? (answerxm1 + fa[N - 1 - i][0]) % popcntxm1 : 0;
        answerxp1 = (answerxp1 + fa[N - 1 - i][1]) % popcntxp1;
      }
    }

    for (int i = 0; i < N; i++) {
      int tmp = 0;
      if(X.charAt(i) == '1'){
        if(popcntxm1 < 2){
          System.out.println(popcount(popcntxm1));
        } else {
          tmp = Math.abs(popcntxm1 + answerxm1 - fa[N - 1 - i][0]) % popcntxm1;
          System.out.println(popcount(tmp) + 1);
        }
      } else {
        if(answerxp1 == 1){
          System.out.println(popcount(answerxp1));
        } else {
          tmp = Math.abs(answerxp1 + fa[N - 1 - i][1]) % popcntxp1;
          System.out.println(popcount(tmp) + 1);
        }
      }
    }
  }
  static private int popcount(int n) {
    if (pp[n] == -1) {
      pp[n] = popcount(n % Integer.bitCount(n)) + 1;
    }
    return pp[n];
  }
}


Measured memory_bytes: 68400
import math

a,b,h,m = map(int,input().split())
h = h*60
t = h+m
at = t*0.5
bt = (t*6)%360
k = abs(at-bt)
cos = math.cos(math.radians(k))

ans = (a**2) + (b**2) - 2*a*b*cos
print(math.sqrt(ans))

Measured memory_bytes: 9444
fun main(arr: Array<String>) {
    val (n,k) = readLine()!!.split(" ").map { it.toInt() }
    var ans = 0L
    for(i in (k+1..n)) {
        val min = 0
        var max = (n / i)
        if(max*i+k > n) {
            max--
        }
        ans += (max-min)*(i-k)
        ans += Math.min(i*(max+1)-1, n) - (i*max+k)+1
    }
    if(k == 0) {
        ans -= n
    }
    println(ans)
}

Measured memory_bytes: 36424
#pragma GCC target ("avx2")
#pragma GCC optimize "trapv"
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define input(a,n) for(ll i1=0;i1<n;i1++)cin>>a[i1]
#define ll long long
#define pi 2 * acos(0.0)
#define usll unordered_set<ll>
#define sll set<ll>
#define vll vector<ll>
#define mll map<ll,ll>
#define pll pair<ll,ll>
#define umll unordered_map<ll,ll>
#define S second
#define sz size()
#define all(v) v.begin(),v.end()
#define Y cout<< "YES"<< "\n"
#define N cout<< "NO"<< "\n"
#define F first
#define mp make_pair
#define pb push_back
#define pf push_front
#define ld long double
#define mod 1000000007
using namespace std;
/* Iterative Function to calculate (x^y)%p in O(log y) */
ll power(ll x, ll y, ll p)
{
    ll res = 1;     // Initialize result

    x = x % p; // Update x if it is more than or
                // equal to p

    if (x == 0) return 0; // In case x is divisible by p;

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1LL)
            res = (res*x) % p;

        // y must be even now
        y = y>>1LL; // y = y/2
        x = (x*x) % p;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    if(n==1)
        cout<<0;
    else
    {
        ll ans=power(10,n,mod);
        ans=(ans+power(8,n,mod))%mod;
        ans=(ans-((2*power(9,n,mod))%mod)+mod)%mod;
        cout<<ans;
    }
    return 0;
}


Measured memory_bytes: 3580
#include<stdio.h>
#include<math.h>
int main(void)
{
    int p,d,i,j,c=0,k,l;
    float q;
    int s=0;
    scanf("%d%d",&p,&d);
    int x[p][d];
    for(i=0;i<p;i++){
     for(j=0;j<d;j++) scanf("%d",&x[i][j]);}
     for(k=0;k<(p-1);k++){
      for(i=k+1;i<p;i++){
     for(j=0;j<d;j++)
        {
         s= s+((x[k][j]-x[i][j])*(x[k][j]-x[i][j])) ;
        }

        q=sqrt(s);

        l=q;



        if((q-l)==0) c++;
        s=0;
     }}
     printf("%d\n",c);
     return 0;
}


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

int main() {
    int n,m,a[50],b[50],c[50],d[50];
    cin>>n>>m;
    for (int i = 0; i < n; ++i) cin>>a[i]>>b[i];
    for (int i = 0; i < m; ++i) cin>>c[i]>>d[i];
    for (int i = 0; i < n; ++i) {
        int J=0, mn = abs(a[i]-c[0])+abs(b[i]-d[0]),di;
        for (int j = 1; j < m; ++j) {
            di=abs(a[i]-c[j])+abs(b[i]-d[j]);
            if (di<mn) {
                J=j;
                mn=di;
            }
        }
        cout<<J+1<<endl;
    }
}


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

int main(void){
    string s;
    int K;
    cin>>s>>K;
    
    list<string> tmp;
    int i,j;   
    for(i=0;i<s.size();i++){
        for(j=1;j<=5;j++){
            tmp.push_back(s.substr(i,j));
            if(i+j==s.size())break;
        }
    }
    
    tmp.sort();
    tmp.unique();
    
    list<string>::iterator itr;
    list<string>::iterator stop=tmp.begin();
    for(i=0;i<K-1;i++)stop++;
    
    cout<<*stop<<endl;
}


Measured memory_bytes: 2176
X, Y = map(int, input().split())
x, y = (X*2-Y)//3, (Y*2-X)//3
mod = 10**9+7
n = min(x, y)

factorial = [1]
for i in range(1, n+1):
    factorial.append((factorial[i-1]*i)%mod)

p_list = [(x+y)%mod]
for i in range(1, n+1):
    p_list.append((p_list[i-1]*(x+y-i))%mod)
    
if (X+Y)%3 != 0:
    print (0)
elif x < 0 or y < 0:
    print (0)
elif n == 0:
    print (1)
else:
    print (p_list[n-1]*pow(factorial[n], 10**9+5, mod)%mod)

Measured memory_bytes: 29484
import heapq


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


itemCount, ticketCount = map(int, input().split(' '))
prices = map(int, input().split(' '))

h = []
for price in prices:
    _heappush_max(h, price)

for i in range(ticketCount):
    price = _heappop_max(h)
    _heappush_max(h, price // 2)
total = 0
for price in h:
    total += price

print(total)

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n),b(n);
  int mx=0,id;
  rep(i,n){
    cin >> a.at(i);
    b.at(i) = a.at(i);
    if( mx < a.at(i) ){
      mx = a.at(i);
      id = i;
    }
  }
  sort(b.begin(),b.end());
  
  rep(i,n){
    if( i == id ){
      cout << b.at(n-2) << endl;
    }else{
      cout << b.at(n-1) << endl;
    }
  }

 
  return 0;
}


Measured memory_bytes: 3200
#![allow(unused_imports)]
use std::io;
use std::cmp;


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

pub trait BinarySearch<T> {
    fn lower_bound(&self, &T) -> usize;
    fn upper_bound(&self, &T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                cmp::Ordering::Less => {
                    low = mid + 1;
                },
                _ => { high = mid; }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                cmp::Ordering::Greater => {
                    high = mid;
                },
                _ => { low = mid + 1; }
            }
        }
        low
    }
}

fn main() {
    let _n = read_one::<usize>();
    let mut top = read::<usize>();
    let mut mid = read::<usize>();
    let mut btm = read::<usize>();
    top.sort();
    mid.sort();
    btm.sort();

    let mut pat = 0;

    // for i for j => O(n^2)
    /*
    for i in btm.iter() {
        let bound_i = mid.lower_bound(&i);
        for j in &mid[0..bound_i] {
            let bound_j = top.lower_bound(&j);
            pat += bound_j;
        }
    }
    */

    // for mid[i] lower * upper => O(n log n)
    for i in mid.iter() {
        let btm_bound = btm.upper_bound(&i);
        let top_bound = top.lower_bound(&i);
        pat += (btm.len() - btm_bound) * top_bound;
    }

    println!("{}", pat);
}

Measured memory_bytes: 13560
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

using T = tuple<int,int,int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    map<T,ll> dp;
    dp[{0,0,0}] = 0;
    rep(i,n) {
        // k = 0
        {
            int l = max(0,n/2-(n-i+1)/2);
            int r = min(i/2,n/2);
            for(int j = l; j <= r; j++) {
                if(!dp.count({i,j,0})) continue;
                if(dp.count({i+1,j,0})) chmax(dp[{i+1,j,0}],dp[{i,j,0}]);
                else dp[{i+1,j,0}] = dp[{i,j,0}];
                if(dp.count({i+1,j+1,1})) chmax(dp[{i+1,j+1,1}],dp[{i,j,0}]+a[i]);
                else dp[{i+1,j+1,1}] = dp[{i,j,0}]+a[i];
            }
        }
        // k = 1
        {
            int l = max(0,n/2-(n-i)/2);
            int r = min((i+1)/2,n/2);
            for(int j = l; j <= r; j++) {
                if(!dp.count({i,j,1})) continue;
                if(dp.count({i+1,j,0})) chmax(dp[{i+1,j,0}],dp[{i,j,1}]);
                else dp[{i+1,j,0}] = dp[{i,j,1}];
            }
        }
    }
    cout << max(dp[{n,n/2,0}],dp[{n,n/2,1}]) << endl;
}

Measured memory_bytes: 47800
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<cstring>
#include<string>
using namespace std;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n;
	scanf("%d",&n);
	if(n%10==9||n/10==9)printf("Yes\n");
		else printf("No\n");
	return 0;
}


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

int main(){
	int n;
  	cin>>n;
  int arr[n];
  for(int i=0;i<n;i++){
   cin>>arr[i]; 
  }
  int dp[n];
  dp[0]=0;
  dp[1]=abs(arr[1]-arr[0]);
  for(int i=2;i<n;i++){
   int a= dp[i-1] + abs(arr[i]-arr[i-1]);
    int b=dp[i-2] + abs(arr[i]-arr[i-2]);
    dp[i]=min(a,b);
  }
  cout<<dp[n-1];
}


Measured memory_bytes: 1024
import itertools


def count_chains(nums):
    if not nums:
        return

    count = 1
    for m, n in zip(nums, nums[1:]):
        if m >= n:
            count += 1
        else:
            yield count
            count = 1
    yield count


def main():
    n = int(input())
    h = [int(x) for x in input().split()]

    print(max(count_chains(h)) - 1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14528
#include<iostream>
main(){
  for(int n,k,a[100000],s,M,i;std::cin>>n>>k,n;printf("%d\n",M)){
    for(i=s=0;i<n;i++<k&&(M=s+=a[i-1]))std::cin>>a[i];
    for(i=k;i<n;M<s&&(M=s))s+=a[i]-a[i++-k];
  }
}

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

int main(void){
   int N;
   cin>>N;
   vector<int> d(N);
   for(int i=0;i<N;i++){
      cin>>d[i];
   }
   set<int> dict;
   for(int i=0;i<N;i++){
      dict.insert(d[i]);
   }
   cout<<dict.size()<<endl;
   return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define end "\n"
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int inf = int(1e9);
const int mod =1e9+7;
const int N = (int)2e5 + 5;


void solve(){
	int n,m;
	cin>>n>>m;
	char c[n+1][m+1];
	Rep(i,1,n){
		Rep(j,1,m){
			cin>>c[i][j];
		}
	}
	//char a[n*2+1][m+1];
	Rep(i,1,n*2){
		Rep(j,1,m){
			cout<<c[(i+1)/2][j];
		}
		cout<<"\n";
	}
	

}
int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

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

using namespace std;

int N;
int a[100005], b[100005], c[100005];
int dp[100005][3];

void solve() {
    for (int i = 1; i <= N; ++i) {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
    }
}

int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }
    solve();
    int res = max({dp[N][0], dp[N][1], dp[N][2]});
    cout << res;
    return 0;
}


Measured memory_bytes: 2560
#include<iostream>
using namespace std;
int n, nr, i, p, x, y, ok;
pair<int, int> w[200005];
int main(){
    cin>> n;
    if(n == 1){
        cout<<"No";
        return 0;
    }
    if(n == 6){
        cout<<"Yes\n1 2\n2 3\n3 7\n7 8\n8 9\n5 4\n4 7\n7 11\n11 10\n3 6\n4 12";
        return 0;
    }
    if(n % 2 == 0){
        p = 1;
        while(p * 2 <= n){
            p *= 2;
        }
        if(n == p){
            cout<<"No";
            return 0;
        }
        x = p;
        y = (n ^ p);
        w[++nr] = make_pair(x, y);
        w[++nr] = make_pair(y, n);
        w[++nr] = make_pair(n, x + n);
        w[++nr] = make_pair(x + n, y + n);
        w[++nr] = make_pair(y + n, 2 * n);
        w[++nr] = make_pair(x + 1, y + 1);
        w[++nr] = make_pair(y + 1, n);
        w[++nr] = make_pair(n, x + n + 1);
        w[++nr] = make_pair(x + n + 1, y + n + 1);
    }
    for(i = 2; i < n; i += 2){
        if(i == x || i == y){
            continue;
        }
        if(ok == 0){
            ok = 1;
            w[++nr] = make_pair(i, i + 1);
            w[++nr] = make_pair(i + 1, 1);
            w[++nr] = make_pair(1, i + n);
            w[++nr] = make_pair(i + n, i + n + 1);
            w[++nr] = make_pair(i + n + 1, n + 1);
        }
        else{
            w[++nr] = make_pair(i, i + 1);
            w[++nr] = make_pair(i + 1, 1);
            w[++nr] = make_pair(1, i + n);
            w[++nr] = make_pair(i + n, i + n + 1);
        }
    }
    if(n % 2 == 0){
        w[++nr] = make_pair(1, n);
    }
    cout<<"Yes\n";
    for(i = 1; i <= nr; i++){
        cout<< w[i].first <<" "<< w[i].second <<"\n";
    }
}


Measured memory_bytes: 3840
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

struct triple
{
  string fi;
  int pi;
  int ind;
  triple(string fi,int pi,int ind){
    this->fi = fi;
    this->pi = pi;
    this->ind = ind;
  }
};

bool compare(const triple a, const triple b){
  if(a.fi == b.fi)
    if(a.pi > b.pi)
      return true;
  if(a.fi < b.fi)
    return true;
  return false;
}

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

    ll n;
    cin >> n;
    vector<triple> v;
    string s;
    int p;
    F0R(i,n) {
      cin >> s >> p;
      v.push_back(triple(s,p,i));
    }

    sort(v.begin(),v.end(),compare);
    F0R(i,n){
      cout << v[i].ind + 1 << endl;
    }


    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = int_fast64_t;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;
	VAR(string, s);
	if(s<="2019/04/30") cout<<"Heisei"<<endl;
	else cout<<"TBD"<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ull unsigned long long int
using namespace std;
int main()
  {
  ull n,sum=1,m = 1000000007;
  cin>>n;
  for(ull i = 1;i<=n;i++)
    {
    sum = (sum * i)%m;
   }
  cout<<sum<<endl;
  }

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char a, b;
  cin >> a >> b;
  if (a == 'H'){
  cout << b;
  }else{
  if (b == 'D'){
  cout << "H";
  }else{
  cout << "D";
  }
  }
}


Measured memory_bytes: 256
import math
import random
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    def is_prime(self,n):
        is_prime_common=self.is_prime_common(n)
        if is_prime_common is not None:return is_prime_common
        if n<2000000:return self.is_prime_brute_force(n)
        return self.is_prime_miller_rabin(n)
    def is_prime_common(self,n):
        if n==1:return False
        if n in Prime.seed_primes:return True
        if any(map(lambda x:n%x==0,self.seed_primes)):return False
    def is_prime_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==0:return False
        return True
    def get_witnesses(self,num):
        def _get_range(num):
            if num<2047:return 1
            if num<1373653:return 2
            if num<25326001:return 3
            if num<3215031751:return 4
            if num<2152302898747:return 5
            if num<3474749660383:return 6
            if num<341550071728321:return 7
            if num<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(b,a)
        if b==0:return a
        while b:a,b=b,a%b
        return a
    @staticmethod
    def f(x,n,seed):
        p=Prime.seed_primes[seed%len(Prime.seed_primes)]
        return(p*x+seed)%n
    def find_factor(self,n,seed=1):
        if self.is_prime(n):return n
        x,y,d=2,2,1
        count=0
        while d==1:
            count+=1
            x=self.f(x,n,seed)
            y=self.f(self.f(y,n,seed),n,seed)
            d=self.gcd(abs(x-y),n)
        if d==n:
            return self.find_factor(n,seed+1)
        return self.find_factor(d)
    # nのすべての素因数を見つける
    def find_factors(self,n):
        primes={}
        if self.is_prime(n):
            primes[n]=1
            return primes
        while n>1:
            factor=self.find_factor(n)
            primes.setdefault(factor,0)
            primes[factor]+=1
            n//=factor
        return primes
n=int(input())
d=Prime().find_factors(n)
a=[]
for i in d:
    a.extend([i]*d[i])
print('%d:'%n,*sorted(a))


Measured memory_bytes: 8224
#input the K and S string
#using another new variable to count the length of string
#then compare the value with the string
#if string less than the value just pring the string S
#if the length of string more than the value
#cut the string using while loop then print ... at the end
#program end

K = int(input())  #O(1)
S = input() #O(1)
value=len(S)    #O(1)

if value <= K: 
    print(S)    #O(1)
elif value > K : 
    x=0     #O(1)
    while x<K: 
        print((S[x]),end=(""))  #O(1)
        x+=1
    print("...")   #O(1)
    

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

int B[100][100];
bool used[100][100];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int solve() {
    int H, W;
    cin >> W >> H;
    cin.ignore();
    if (H == 0) return -1;

    H = H * 2 + 1;
    W = W * 2 + 1;

    REP(i, H) B[i][0] = B[i][W-1] = 1;
    REP(j, W) B[0][j] = B[H-1][j] = 1;
    
    REP2(i, 1, H-1) {
        string s;
        getline(cin, s);
        REP2(j, 1, W-1) {
            if (s[j-1] == '1') B[i][j] = 1;
            else B[i][j] = 0;
        }
    }

    REP(i, H) REP(j, W) used[i][j] = false;

    
    deque<tuple<int, int, int> > queue;
    queue.push_back(make_tuple(1, 1, 1));
    while(!queue.empty()) {
        int r, c, d;
        tie(r, c, d) = queue.front();
        queue.pop_front();
        if (r == H - 2 && c == W - 2) return d;
        if (used[r][c]) continue;
        used[r][c] = true;

        REP(i, 4) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            if (B[nr][nc] || used[nr][nc]) continue;
            nr = nr + dr[i];
            nc = nc + dc[i];
            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            if (B[nr][nc] || used[nr][nc]) continue;
            
            queue.push_back(make_tuple(nr, nc, d+1));
        }
    }

    return 0;
}

int main() {
    while (true) {
        int ret = solve();
        if (ret == -1) break;
        cout << ret << endl;
    }
}

Measured memory_bytes: 3232
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		sc.close();
		long ans = 100;
		for(long i=1; i<Math.sqrt(N)+1; i++) {
			if(N%i==0) {
				int test = Math.max(disit(i, 10), disit(N/i, 10));
				ans = Math.min(ans, test);
			}
		}
		System.out.println(ans);
	}
	static int disit(long a, long d) {
		int count = 0;
		while(a!=0) {
			a = a/d;
			count++;
		}
		return count;
	}
	static long lcm(long a, long b) {
		return a*(b/gcd(a, b));
	}
	
	static long gcd(long a, long b) {
		long ta = Math.max(a, b);
		long tb = Math.min(a, b);
		long tmp;
		while((tmp = ta%tb) != 0) {
			ta = tb;
			tb = tmp;
		}
		return tb;
	}
	
	static long modcomb(long n, long k, long mod) {
		if(k==1) {
			return n;
		}
		
		long ans = 1;
		for(long i=n; i>=n-k+1; i--) {
			ans = (ans * i)%mod;
		}
		for(long i=k; 0<i; i--) {
			ans = (ans * modpow(i, mod-2, mod)) % mod;
		}
		return ans;
	}
	
	static long modpow(long a, long b, long mod) {
		if(b==0) return 1;
		if(b%2==0) {
			long d = modpow(a, b/2, mod);
			return (d*d)%mod;
		} else {
			return (a*modpow(a, b-1, mod))%mod;
		}
	}
}


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

int main(){
    int n, k, i, x, l = 0;
    cin >> n >> k;
    for(i=0; i<n; i++){
        cin >> x;
        l += 2 * min(x, k-x);
    }
    cout << l;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	char A[101],B[101],C[101];
	int ai,bi,ci;
	char x;
	scanf("%s",A);
	scanf("%s",B);
	scanf("%s",C);
	x=A[0];
	ai=0,bi=0,ci=0;
	while(1){
		if(x=='a'){
			if(A[ai]=='\0'){
				printf("A");
				break;
			}
			else{
				x=A[ai];
				ai++;
			}
		}
		else if(x=='b'){
			if(B[bi]=='\0'){
				printf("B");
				break;
			}
			else{
				x=B[bi];
				bi++;
			}
		}
		else if(x=='c'){
			if(C[ci]=='\0'){
				printf("C");
				break;
			}
			else{
				x=C[ci];
				ci++;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>


int A[100000];

int partition(int A[],int p,int r){
  int x,i,j,e;

  x = A[r];
  i = p-1;

  for(j = p ; j < r; j++){
    if(A[j] <= x){
      i++;
      e = A[j];
      A[j] = A[i];
      A[i] = e;
    }
  }
  e = A[i+1];
  A[i+1] = A[r];
  A[r] = e;

  return i+1;

}


int main(void){

  int i,j;
  int n;
  int q;

  scanf("%d",&n);
  for(i = 0 ; i < n ; i++)
    scanf("%d",&A[i]);
  q = partition(A,0,n-1);
  for( i = 0 ; i < n-1 ; i++){
    if(i == q){
      printf("[%d] ",A[q]);
      continue;
    }
    printf("%d ",A[i]);
  }
  printf("%d\n",A[i]);
  return 0;
}



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

using namespace std;

int main(){
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> v(n, 0);
    int index;
    for (int i = 0; i < q; i++)
    {
        cin >> index;
        v[index-1]++;
    }
    for (int i = 0; i < n; i++)
    {
        if(v[i]-(q-k)>0)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;

}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<int, int> P;


int main(){
    string s;   cin >> s;
    if(s[2] == s[3] && s[4] == s[5]){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }


    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        final int H = sc.nextInt();
        final int W = sc.nextInt();
        int D = sc.nextInt();
        int[][] L = new int[2][H*W+1];
        for(int i = 1;i < H+1;i++){
            for(int j = 1;j < W+1;j++){
                int aij = sc.nextInt();
                L[0][aij] = i;
                L[1][aij] = j;
            }
        }
        int[] A = new int[H*W+1];
            for(int j = D+1;j < H*W+1;j++){
                A[j] = A[j-D]+Math.abs(L[0][j]-L[0][j-D])+Math.abs(L[1][j]-L[1][j-D]);
            }
        int Q = sc.nextInt();
        for(int i = 0;i < Q;i++){
            int li = sc.nextInt();
            int ri = sc.nextInt();
            System.out.println(A[ri]-A[li]);
        }
    }
}

Measured memory_bytes: 98632
//FIRST THINK THEN CODE.

#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define FOR(i,n)  for(ll i=0;i<n;i++)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vld vector<ld>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define vvld vector<vector<ld>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define rev(p) reverse(p.begin(),p.end());
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define popcount(x) __builtin_popcountll(x)
#define sz(x) ((ll)x.size())
const ll M = 1000000007;
const ll MM = 998244353;
ll begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define trace(...)
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}

template<typename T, typename F>
void chmax( T &a, F b) {
  if (b > a)a = b;
}

template<typename T, typename F>
void chmin( T &a, F b) {
  if (b < a)a = b;
}



ll powM(ll a, ll b, ll m)
{
  if (a <= 0)return 0;
  a %= m;
  ll ans = 1LL;
  while (b)
  {
    if (b & 1)ans = ans * a % m;
    a = a * a % m;
    b >>= 1;
  }

  return ans;
}



ll poww(ll a, ll b)
{

  ll ans = 1;
  while (b)
  {
    if (b & 1)ans = ans * a;
    a = a * a;
    b >>= 1;
  }

  return ans;

}


string tostring(ll x) {
  stringstream sss;
  sss << x;
  string ans = sss.str();
  return ans;
}



const ll N = 1e6 + 5;





int main() {

  IOS;

#ifndef ONLINE_JUDGE

  freopen("input1.txt", "r", stdin);
  freopen("output1.txt", "w", stdout);

#endif

  ll n; cin >> n;
  string s; cin >> s;

//ll n=sz(s);

  s = '!' + s;


  vl pr(n + 1);


  for (ll i = 1; i <= n; i++) {
    pr[i] += pr[i - 1];
    if (s[i] == '.')pr[i]++;
  }

  ll ans = 1e9;

  for (ll i = 0; i <= n; i++) {
    ll wf = pr[i];
    ll wb = pr[n] - pr[i];
    ll bf = i - pr[i];
    ll bb = n - bf - wf - wb;
    chmin(ans, bf + wb);
  }

  cout << ans;



  return 0;
}

Measured memory_bytes: 5052
#include <bits/stdc++.h>
using namespace std;
#define f(i,j,k) for(int i=j;i<k;i++)
int main(){
    long long n,ans=1;
    cin>>n;
    while(1){
        ans*=2;
        if(ans>n){
            ans/=2;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector> 
#include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;
const int mod = 1e9+7;

int arr[100][100];
signed main(){
    char n;
    cin >> n;
    if(n-'a'<0)cout << "A" << endl;
    else cout << "a" << endl;



    return 0;
}


Measured memory_bytes: 3600
s = input()
n = len(s)
K = int(input())

# dp[i][j][k]
# i : 桁数
# j : 非0を使った数
# k : そこまでの桁がs（指定された最大値）と一致しているか？、0なら一致してない、1なら一致してる
dp = [[[0 for i in range(2)] for j in range(4)] for k in range(105)]

# i = 0は、与えられた整数の一つ左の桁（上位の桁）に０があると仮定した時に
# そのパターンは１つしかない状態を持たない（i=0, j=0, k=1）ため初期値を設定している
dp[0][0][1] = 1

# debug_msg = "dp[{}][{}][{}] = {}"
for i in range(n):
  for j in range(4):
    for k in range(2):
      # sのi桁目を取得
      nd = int(s[i])
      # 各桁について0~9のパターンを考える
      for d in range(10):
        ni = i + 1
        nj = j
        nk = k
        if (d != 0): nj += 1
        if (nj > K): continue
        if (k == 1):
          if (d > nd): continue
          if (d < nd): nk = 0
        dp[ni][nj][nk] += dp[i][j][k]
        # print(debug_msg.format(ni, nj, nk, dp[ni][nj][nk]))

res = dp[n][K][0] + dp[n][K][1]
print(res)

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<JobInfo> jobInfoList = new ArrayList<JobInfo>();
		for(int i= 0;i < n;i++) {
			JobInfo jobInfo = new JobInfo(sc.nextInt(),sc.nextInt());
			jobInfoList.add(jobInfo);
		}
		jobInfoList.sort((a,b)-> a.getKigen() - b.getKigen());
		long totalTask = 0;
		for(JobInfo jobInfo:jobInfoList) {
			totalTask += jobInfo.getTime();
			if(totalTask > jobInfo.getKigen()) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}
	static class JobInfo {
		private int time;
		private int kigen;
		public JobInfo(int time,int kigen) {
			this.time = time;
			this.kigen =kigen;
		}
		public int getTime() {
			return time;
		}
		public void setTime(int time) {
			this.time = time;
		}
		public int getKigen() {
			return kigen;
		}
		public void setKigen(int kigen) {
			this.kigen = kigen;
		}
	}
}

Measured memory_bytes: 108612
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    s = [int(x) for x in input().split()]
    t = [int(x) for x in input().split()]
    
    mod = pow(10, 9)+7
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for i in range(m+1):
        dp[0][i] = 1
    
    for i in range(n):
        for j in range(m):
            dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
            if s[i] == t[j]:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= mod
    
    print(dp[n][m])            
    
if __name__ == "__main__":
    main()

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

using namespace std;

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

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

#define VIN(v) for(auto&elem_: (v) )cin>>elem_
#define VOUT(v, sep) for(_loop_int idx=0; idx<(_loop_int)v.size(); idx++) {cout<<v[idx]; if(idx<(_loop_int)v.size()-1) cout<<sep;} cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(debugidx,v.size())cout<<" "<<v[debugidx];cout<<endl
#define DEBUG_ARR(v,n) cout<<#v<<":";REP(debugidx,n)cout<<" "<<v[debugidx];cout<<endl

const ll MOD = 1000000007ll;
const int IINF = numeric_limits<int>::max()/2-1;
const ll LINF = numeric_limits<ll>::max()/2-1;

template<class T> inline bool chmin(T& a, const T b) { if (a>b) { a=b; return true; } return false; }
template<class T> inline bool chmax(T& a, const T b) { if (a<b) { a=b; return true; } return false; }

#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int a,b,x;
    cin>>a>>b>>x;
    int ans = x-a;

    if(ans>=0 && b>=ans) yn;
    return 0;
}

Measured memory_bytes: 3644
#include <vector>
#include <bitset>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;

class Data
{
public:
    int g;
    int e;
    Data(){
        g = e = -1;
    }
    Data(int g0, int e0){
        g = g0;
        e = e0;
    }
    bool operator<(const Data& d) const{
        return g < d.g || (g == d.g && e < d.e);
    }
};

bool check[32][32][32][32];
Data memo[32][32][32][32];

Data solve(int y1, int x1, int y2, int x2, int s)
{
    if(check[y1][x1][y2][x2])
        return memo[y1][x1][y2][x2];

    int tmp = 0;
    for(int i=y1; i<=y2; ++i){
        for(int j=x1; j<=x2; ++j){
            tmp += memo[i][j][i][j].e;
        }
    }
    if(tmp < s)
        return Data();

    Data ret(1, tmp);
    for(int i=y1; i<y2; ++i){
        Data d1 = solve(y1, x1, i, x2, s);
        Data d2 = solve(i+1, x1, y2, x2, s);
        if(d1.g == -1 || d2.g == -1)
            continue;
        Data d3(d1.g + d2.g, min(d1.e, d2.e));
        ret = max(ret, d3);
    }
    for(int i=x1; i<x2; ++i){
        Data d1 = solve(y1, x1, y2, i, s);
        Data d2 = solve(y1, i+1, y2, x2, s);
        if(d1.g == -1 || d2.g == -1)
            continue;
        Data d3(d1.g + d2.g, min(d1.e, d2.e));
        ret = max(ret, d3);
    }

    check[y1][x1][y2][x2] = true;
    memo[y1][x1][y2][x2] = ret;
    return ret;
}

int main()
{
    for(;;){
        int h, w, s;
        cin >> h >> w >> s;
        if(h == 0)
            return 0;

        for(int i=0; i<h; ++i){
            for(int j=0; j<w; ++j){
                for(int k=0; k<h; ++k){
                    for(int l=0; l<w; ++l){
                        check[i][j][k][l] = false;
                        memo[i][j][k][l] = Data();
                    }
                }
            }
        }

        for(int i=0; i<h; ++i){
            for(int j=0; j<w; ++j){
                memo[i][j][i][j].g = 1;
                cin >> memo[i][j][i][j].e;
                s -= memo[i][j][i][j].e;
            }
        }
        s *= -1;

        Data d = solve(0, 0, h-1, w-1, s);
        cout << d.g << ' ' << (d.e-s) << endl;
    }
}

Measured memory_bytes: 9988
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,i;
    cin>>n>>m;
    int ara[m],dis[m-1];
    for(i=0;i<m;i++)
        cin>>ara[i];
    sort(ara,ara+m);
    for(i=1;i<m;i++)
    {
        dis[i-1]=ara[i]-ara[i-1];
    }
    sort(dis,dis+m-1);
    int res=0;
    n--;
    for(i=m-2;i>=0;i--)
    {
        if(n==0)
           res+=dis[i];
        else
            n--;
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 4408
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
#define max(a,b) a < b ? b : a
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int dp1[3010][3010];

int main(){
    int n;
    int t;
    vector<pii> vec;
    cin >> n >> t;
    int a,b;
    rep(i,n){
        cin >> a >> b;
        vec.push_back(make_pair(a,b));
    }

    sort(vec.begin(),vec.end(),[](const pii &a,const pii &b){
        if(a.first == b.first) return a.second > b.second;
        else return a.first < b.first;
    });
    
    rep(i,n){
        rep(j,t+1){
            if(j-vec[i].first>=0)
                dp1[i+1][j] = max(dp1[i][j],dp1[i][j-vec[i].first] + vec[i].second); 
            else
                dp1[i+1][j] = dp1[i][j];
        }
    }

    int ans = 0;
    rep(i,n){
        ans = max(ans,dp1[i][t-1] + vec[i].second);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 35584