akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

const int maxn = 1e5 + 5;
vector <ii> v;
int n, m;
int sz[maxn], l[maxn], p[maxn];
bool alive[maxn];

void make_set(int u){
	sz[u] = 1;
	p[u] = u;
	l[u] = u - 1;
}

int fset(int u){
	return u == p[u] ? u : p[u] = fset(p[u]);
}

void merge(int u, int v){
	u = fset(u);
	v = fset(v);
	if(u != v){
		if(sz[v] > sz[u]) swap(u, v);
		sz[u] += sz[v];
		l[u] = min(l[u], l[v]);
		p[v] = u;
	}
}


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

	cin >> n >> m;
	v.resize(n);
	for(int i = 0; i <= m; i++)
		make_set(i);
	for(int i = 0; i < n; i++){
		cin >> v[i].first >> v[i].second;
	}
	sort(all(v), [](ii& a, ii& b){
		if(a.second == b.second) return a.first > b.first;
		return a.second > b.second;
	});
	ll res = 0;
	memset(alive, 1, sizeof alive);
	for(int i = 0; i < n; i++){
		//cout << v[i].first << " " << v[i].second << endl;
		int t = m - v[i].first;
		//cout << t << endl;
		if(t < 0) continue;
		if(alive[t]){
			res += v[i].second;
			alive[t] = 0;
			if(t - 1 >= 0 && !alive[t - 1]) merge(t, t - 1);
			if(t + 1 <= n - 1 && !alive[t + 1]) merge(t, t + 1);
		}
		else{
			t = fset(t);
			if(l[t] >= 0){
				res += v[i].second;
				int added = l[t];
				alive[added] = 0;
				merge(t, added);
				if(added - 1 >= 0 && !alive[added - 1]) merge(added, added - 1);
			}
		}
	}	
	cout << res;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const ll INF = (1LL << 31) - 1;
const double pi=acos(-1);

int main(){
  ll n ;
  cin >> n;
  int nowt=0,nowx=0,nowy=0;
  rep(i,n){
    int t,x,y;
    cin >> t >> x >> y;
    if(abs(nowx-x)+abs(nowy-y)>t-nowt || (abs(nowx-x)+abs(nowy-y))%2!=(t-nowt)%2){
      cout << "No" << endl;
      return 0;
    }
    nowt=t;
    nowx=x;
    nowy=y;
  }
  cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define F(i,n) for(int i=0;i<n;i++)
#define G(i,m,n) for(int i=m;i<=n;i++)
int main()
{
 ll n,a=0,w=0,t=0,r=0 ;
 cin >> n;

 F(i,n)
 {
     string s;
     cin >> s;
     if(s[0]=='A') a++;
     if(s[0]=='W') w++;
     if(s[0]=='T') t++;
     if(s[0]=='R') r++;


 }

 cout <<"AC x "<<a<<endl;
 cout<<"WA x "<<w<<endl;
 cout<<"TLE x "<<t<<endl;
 cout<<"RE x "<<r<<endl;





return 0;
}


Measured memory_bytes: 3632
let cnt = ref 0

let solve () = 
    let a = Scanf.sscanf (read_line ()) "%d" (fun a -> a) in
    let b = Scanf.sscanf (read_line ()) "%d" (fun a -> a) in
    let c = Scanf.sscanf (read_line ()) "%d" (fun a -> a) in
    let x = Scanf.sscanf (read_line ()) "%d" (fun a -> a) in
    for i = 0 to a do
        for l = 0 to b do
            for k = 0 to c do
                if i*500+l*100+k*50 == x 
                    then cnt := !cnt + 1
                    else ()
            done
        done
    done

let _ = solve (); print_int (!cnt); print_string "\n"

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	string s;
	cin >> s;
	cout << s.substr(0, 3);

	return 0;
}

Measured memory_bytes: 3648
import sys

input = sys.stdin.readline


def main():
    n = int(input())
    h_list = [int(i) for i in input().split()]
    print(
        1 + len([i for i, h in enumerate(h_list[1:], start=1) if h >= max(h_list[:i])])
    )


if __name__ == "__main__":
    main()


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

using namespace std;

int max(std::vector<int> &v)
{
    int maxVal = 0;       // 整数最小値
    for(int i = 0; i < (int)v.size(); ++i) {
        if( v[i] > maxVal )
            maxVal = v[i];
    }
    return maxVal;
}

int main()
{
    vector<int> ans;

    string input_str;
    cin >> input_str;

    int len_str = input_str.length();

    int count = 0;

    for (int i=0; i<len_str; i++)
    {
        if (input_str[i] == 'A' || input_str[i] == 'T' || input_str[i] == 'C' || input_str[i] == 'G')
        {
            count++;
        }else
        {
            count = 0;
        }
        ans.push_back(count);
    }

    cout << max(ans) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;i++)
#define INF 10000000000000000
int main(void){
    ll n,m;cin>>n>>m;
    ll l0,r0,l1,r1;cin>>l0>>r0;
    rep(i,m-1){
        cin>>l1>>r1;
        l0=max(l0,l1);
        r0=min(r0,r1);
    }
    if(l0>r0)cout<<0;
    else cout<<r0-l0+1;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a,b,c;
    char op;
    
    for( ;scanf("%d %c %d",&a,&op,&b) != EOF; ){
    
    if ( op == '+')
    {c = a + b;
    printf("%d\n",c);}
    
    else if( op == '-')
        {
        c = a - b;
        printf("%d\n",c);
        }
    
    else if( op == '*')
        {
        c = a * b;
        printf("%d\n",c);
        }
    
    else if( op == '/')
        {c = a / b;
        printf("%d\n",c);
        }
        
    else break;
    }
    return 0;
}



Measured memory_bytes: 2752
#[allow(unused_macros)]
macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect() }; input_inner!{next, $($r)*} }; }
macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} };}
macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; }

#[allow(unused_imports)]
use std::cmp::{min,max};

fn main(){
    input!{
        n: usize,
        a: [usize; n]
    }
    let mut ans = 0;
    for i in 0..n{
        let mut aa = a[i];
        loop{
            if aa%2==0{
                ans += 1;
                aa /= 2;
            }else{
                break;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  int n, l;
  cin >> n >> l;
  vector<string> v(n);

  for (int i=0; i<n; i++) {
    string t;
    cin >> t;
    v[i]=t;
  }

  sort(v.begin(), v.end());

  for (int i=0; i<n; i++) {
    cout << v[i];
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    k = ni()
    s = ns()

    if len(s) <= k:
        print(s)
    else:
        print(s[:k] + '...')


if __name__ == '__main__':
    main()

Measured memory_bytes: 9728
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;

double eps=1e-8;

bool eq(double a,double b){
  return (-eps<a-b&&a-b<eps);
}

bool eq(P a,P b){
  return (abs(a-b)<eps);
}

double dot(P a,P b){
  return real(b*conj(a));
}

double cross(P a,P b){
  return imag(b*conj(a));
}
    
bool isParallel(P a,P b){
  return eq( cross(a,b) , 0 );
}


struct S{
  P p,q;
  S(P a=P(0,0),P b=P(0,0)):p(a),q(b){}
  P base(){    return q-p;  }
};

typedef S L;

double getDistanceLP(L l,P p){
  P a=l.p,b=l.q;
  return abs( cross(b-a,p-a) ) / abs(b-a);
}

double getDistanceSP(S s,P p){
  P a=s.p;
  P b=s.q;
  if( dot(b-a,p-a) < eps )return abs(p-a);
  if( dot(a-b,p-b) < eps )return abs(p-b);
  return getDistanceLP(s,p);
}

P reflect(S s,P p){
  P a=s.p;
  P b=s.q;
  p-=a;
  b-=a;
  return a+conj(p/b)*b;
}

bool onLine(L l,P p){
  P a=l.p;
  P b=l.q;
  return eq(0, cross(p-a,b-a) );
}

bool onSegment(S s,P p){
  P a=s.p;
  P b=s.q;
  return eq( abs(a-b) , abs(p-a) + abs(p-b) );
}

P getCrossPoint(S s1,S s2){
  P a=s1.p, b=s1.q;
  P c=s2.p, d=s2.q;
  a-=d,b-=d,c-=d;
  return d+a+(b-a)*imag(a/c)/imag(a/c-b/c);
}

bool isIntersectLS(L li,S se){
  P a=li.p;
  P b=li.q;
  double A=cross(b-a,se.p-a);
  double B=cross(b-a,se.q-a);
  return (A*B<eps);
}

P input(){
  double x,y;
  cin>>x>>y;
  return P(x,y);
}

int N;
S t[5];
P si,ti;
int tl[10];
double ans;

double calc(P p,P v,int depth){

  if( eq(p,ti) ) return 0;
  
  P np,nv;
  
  if(depth>6)return 1e20;
  
  double mini=1e20;
  for(int i=0;i<N;i++){
    S seg=t[i];
    if(onSegment(seg,p))continue;

    L li=L(p,p+v);
    if( !isIntersectLS(li,seg) )continue;
    
    P k=getCrossPoint( li, seg );
        assert( onSegment(seg,k) );
        assert( onLine(li,k) );
    /*
    cout<<"i="<<i<<endl;
    cout<<"k="<<k<<endl;
    cout<<"v="<<v<<endl;
    cout<<"p="<<p<<endl;
    cout<<endl;
    */
    if( dot(k-p,v) < 0 )continue;
    
    if(mini>abs(k-p)){
      mini=abs(k-p);
      np=k;
      nv=reflect(seg,k+v)-k;
    }
  }

  if( isParallel(v,ti-p) && dot(v,ti-p) > 0 ){
    if( mini > abs(ti-p)){
      return abs(ti-p);
    }
  }

  if(mini==1e20)return 1e20;
  return mini+calc(np,nv,depth+1);
}

P ansve;
void check(int size,P target){
  P v=target-si;
  if( abs(v) < eps )return;
  double dist=calc(si,v,0);
  if(ans>dist){
    ans=dist;
    ansve=v;
  }
}

void dfs(int depth, P target){
  check(depth,target);
  if(depth==6)return;
  for(int i=0;i<N;i++){
    dfs(depth+1, reflect(t[i],target) );
  }
}

int main(){
  while(1){
    cin>>N;
    if(N==0)break;
    for(int i=0;i<N;i++){
      P a=input();
      P b=input();
      t[i]=S(a,b);
    }
    ti=input();
    si=input();
    ans=1e20;
    dfs(0,ti);
    printf("%.10f\n",ans);
  }

  return 0;
}

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

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int dist(int a, int b, int c, int d) {
  return abs(a - c) + abs(b - d);
}

int main() {
  ios:: sync_with_stdio(false);
  cin.tie();
  int n;
  cin >> n;
  vector<int> a, b;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    a.push_back(dist(1, 1, x, y));
    b.push_back(dist(1, 1000000000, x, y));
  }
  cout << max(*max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end()), *max_element(b.begin(), b.end()) - *min_element(b.begin(), b.end()));
  return 0;
}




Measured memory_bytes: 5072
import java.util.Scanner;
 
public class Main{
		
	public static void main(String args[]){
		  
		Scanner sc = new Scanner(System.in);
		
		int in = sc.nextInt();
		
		int l = in/100;
		int r = in%100;
		
		if((r > 0 && r <= 12) && (l > 0 && l <= 12)) {
			System.out.println("AMBIGUOUS");
		}else if((l > 0 && l <= 12) && r >= 0) {
			System.out.println("MMYY");
		}else if((r > 0 && r <= 12) && l >= 0) {
			System.out.println("YYMM");
		}else {
			System.out.println("NA");
		}
		
	}
}


Measured memory_bytes: 21588
N = int(input())
A = list(map(int, input().split()));
lis = [0]*(N+1)
ans = [0]*(N+1)
ans_selected = [0]*(N+1)
ans_sum = 0

for i in A:
    lis[i] += 1

for num, i in enumerate(lis):
    ans[num] = i * (i-1) // 2
    ans_sum += i * (i-1) // 2
    if i != 0:
        ans_selected[num] = (i-1) * (i-2) // 2

for i in A:
    print(ans_sum - ans[i] + ans_selected[i])


Measured memory_bytes: 26140
#include<bits/stdc++.h>
using namespace std;
vector<int>a[100005];
priority_queue<int> q;
int main(){
	int n,m,x,y,ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		if(x>m)continue;
		a[m-x+1].push_back(y);
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<a[i].size();j++)ans+=a[i][j],q.push(-a[i][j]);
		while(q.size()>i){ans+=q.top();q.pop();}
	}
	printf("%d",ans);
}


Measured memory_bytes: 6268
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  long int N, cnt = 0, m = 0;
  long int lb = 0, lw = 0, rb = 0, rw = 0;
  string S;
  cin >> N >> S;
  //wb
  for(int i = 0; i < N; ++i)
    if(S[i] == '.') ++rw;
    else ++rb;
  m = min(rw, rb);
  for(int j = 0; j < N + 1; ++j) {
    if(S[j] == '.') {--rw; ++lw;}
    else {--rb; ++lb;}
    m = min(m, lb + rw);
  }
  cout << m << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
ll red[100];
ll blue[100];
ll le[100];
ll ri[100];

ll gcd(ll a,ll b){
	if(b>a){	a^=b;	b^=a;	a^=b;	}
	while(1){
		int temp=a%b;
		if(temp==0)	break;
		a=b;	b=temp;
	}
	return b;
}

ll dfs(int now){
	ll l=1,r=1;
	if(le[now]!=0)	l*=dfs(le[now]-1);
	if(ri[now]!=0)	r*=dfs(ri[now]-1);
	ll g=gcd(blue[now]*r,red[now]*l);
	ll ans=blue[now]*r*red[now]*l/g;
	return ans/blue[now]+ans/red[now];	
}
	
int main(){
	while(true){
		cin>>n;
		if(n==0)	return 0;
		vector<int> parent(n,-1);
		for(int i=0;i<n;i++){
			cin>>red[i]>>blue[i]>>le[i]>>ri[i];
			if(le[i]!=0)	parent[le[i]-1]=i;	
			if(ri[i]!=0)	parent[ri[i]-1]=i;
		}
		for(int i=0;i<n;i++){
			if(parent[i]==-1){
				cout<<dfs(i)<<endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1204
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            Integer[] A = new Integer[N];
            for (int i = 0; i < N; i++) A[i] = in.nextInt();
            Arrays.sort(A);

            if (N == 2) {
                out.println(A[1] + " " + A[0]);
            } else {
                int n = A[N - 1];
                int k = A[N - 2];
                for (int i = N - 3; i >= 0; i--) {
                    if (Math.min(k, n - k) < Math.min(A[i], n - A[i])) {
                        k = A[i];
                    }
                }
                out.println(n + " " + k);
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 41948
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	static Scanner sc =new Scanner(System.in);
	public static void main(String[] args) {
		
		int N=sc.nextInt();
		int k=sc.nextInt();
		int a[]=new int[N];
		for(int i=0;i<N;i++)a[i]=sc.nextInt();
		
		int dp[]=new int[N+1];
		
	if(N==2)System.out.println(Math.abs(a[0]-a[1]));
	else if(N==3&&k>=2)System.out.println(Math.min(Math.abs(a[0]-a[1])+Math.abs(a[1]-a[2]),Math.abs(a[0]-a[2])));
	else if(N==3&&k<2)System.out.println(Math.abs(a[0]-a[1])+Math.abs(a[1]-a[2]));
	
	else {
		dp[0]=0;
		dp[1]=0;
		dp[2]=Math.abs(a[0]-a[1]);
		if(k>=2)
		dp[3]=Math.min(Math.abs(a[0]-a[1])+Math.abs(a[1]-a[2]),Math.abs(a[0]-a[2]));
		else dp[3]=Math.abs(a[0]-a[1])+Math.abs(a[1]-a[2]);
		
		for(int i=4;i<N+1;i++) {
			List<Integer> list=new ArrayList<Integer>();
			
			//dp[i]=Math.min(dp[i-1]+Math.abs(a[i-2]-a[i-1]),dp[i-2]+Math.abs(a[i-3]-a[i-1]));
			for(int j=k;j>=1;j--) {if(i-j-1>=0)list.add(dp[i-j]+Math.abs(a[i-j-1]-a[i-1]));}
		dp[i]=Collections.min(list);
			
		}
		System.out.println(dp[N]);
	}}

}


Measured memory_bytes: 148016
from collections import Counter
n, m = map(int, input().split())
cl = []
for i in range(2, int(m ** .5) + 1):
    while m % i == 0:
        cl.append(i)
        m //= i
if m > 1:
    cl.append(m)

def comb(x, y):
    y = min(y, x - y)
    a = 1
    for i in range(x, x - y, -1):
        a *= i
    b = 1
    for i in range(1, y + 1):
        b *= i
    return a // b

ans = 1
mod = 10 ** 9 + 7
for t in Counter(cl).values():
    ans = ans * comb(t + n - 1, t) % mod
print(ans)

Measured memory_bytes: 3444
#include<iostream>
#include<algorithm>
using namespace std;
#define i64 long long int
#define ran 100010
int N;i64 C;
i64 pos[ran], val[ran], lef[ran], rig[ran], lef2[ran], rig2[ran];
int main(){
	ios::sync_with_stdio(false);
	cin >> N >> C;
	for(int i=1; i<=N; i++)
		cin >> pos[i] >> val[i];

	i64 cur = 0;
	lef[0] = 0;
	for(int i=1; i<=N; i++){
		cur += val[i];
		lef[i] = max(lef[i-1], cur - pos[i]);
		lef2[i] = max(lef2[i-1], cur - 2 * pos[i]);
	}

	cur = 0;
	rig[0] = 0;
	for(int i=1; i<=N; i++){
		cur += val[N+1-i];
		rig[i] = max(rig[i-1], cur - (C - pos[N+1-i]));
		rig2[i] = max(rig2[i-1], cur - 2 * (C - pos[N+1-i]));
	}

	i64 res = 0;
	for(int i=1; i<=N; i++){
		res = max(res, lef[i] + rig2[N-i]);
		res = max(res, rig[i] + lef2[N-i]);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 4992
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <list>
#include <vector>
#include <map>

using namespace std;


int main(void) {
	int n, *a,check,cost=0;
	float sum = 0;
	cin >> n;
	a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	sum /= n;
	check = (int)sum;
	if (sum - check > 0.5)check++;

	for (int i = 0; i < n; i++) {
		cost+=pow(a[i] - check, 2);
	}
	cout << cost << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstdlib>
#include <vector>
#include <iomanip>
#include <utility>
using namespace std;
#define ll long long

int main(void){
    ll n, k;
    cin >> n >> k;
    ll count = 0;
    while(n >= 1){
        n /= k;
        count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,N) for(int i=0;i<N;i++)
using namespace std;
long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;


int main(){

int N;
cin>>N;

vector<vector<int>>v(N);
vector<pair<int,int>>node(N-1);
int cnt[N]={};
rep(i,N-1){
    int a,b;
    cin>>a>>b;
    a--,b--;
    v[a].push_back(b);
    v[b].push_back(a);
    node[i]=make_pair(a,b);
    cnt[a]++;
    cnt[b]++;
}


vector<long long> c(N);
rep(i,N)cin>>c[i];
sort(c.begin(),c.end());


multimap<int,int>mp;

rep(i,N){
    mp.insert(make_pair(-cnt[i],i));
}
bool checked[N]={};
queue<int>q;
long long ans[N];
auto iter=mp.begin();
q.push(iter->second);
checked[iter->second]=true;
int p=N-1;

while(!q.empty()){

    int now=q.front();q.pop();
    ans[now]=c[p];
    p--;
    
    for(auto vp:v[now]){
        if(checked[vp])continue;
        q.push(vp);
        checked[vp]=true;
    }

}

long long M=0;
rep(i,N-1){
    M+=min(ans[node[i].first],ans[node[i].second]);
}
cout<<M<<endl;
rep(i,N)cout<<ans[i]<<" ";

 return 0;
}
/*

by my self
1h 21m 37s
5
1 2
2 3
3 4
4 5
1 2 3 4 5

10
1 2 3 4 5


5
1 2
1 3
1 4
1 5
3141 59 26 53 59

197
59 26 3141 59 53

*/

Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <functional>
using namespace std;

typedef long long ll;


bool merged[100003], used[100003], w[100003], z[100003];
vector<int> edg[100003];
ll a[100003];
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > que1;
priority_queue<pair<int, pair<ll, int> > > que2;

void func(int pos) {
	merged[pos] = true;
	if (!used[pos]) que1.push({ a[pos], pos });
	for (int i : edg[pos]) {
		if (merged[i]) continue;
		func(i);
	}
}

int con(int pos) {
	w[pos] = true;
	int ret = 1;
	for (int i : edg[pos]) {
		if (w[i]) continue;
		ret += con(i);
	}
	return ret;
}

void func2(int pos, int c) {
	z[pos] = true;
	que2.push({ c, {-a[pos], pos} });
	for (int i : edg[pos]) {
		if (z[i]) continue;
		func2(i, c);
	}
}

int main() {
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < m; ++i) {
		int x, y; cin >> x >> y;
		edg[x].push_back(y);
		edg[y].push_back(x);
	}
	
	for (int i = 0; i < n; ++i) {
		if (w[i]) continue;
		int c = con(i);
		func2(i, c);
	}

	int arg = que2.top().second.second;
	func(arg);
	ll ans = 0;
	while (!que2.empty()) {
		ll c = -que2.top().second.first; int pos = que2.top().second.second; que2.pop();
		if (merged[pos] || used[pos]) continue;
		ll d; int posm;
		do {
			if (que1.empty()) {
				cout << "Impossible" << endl;
				return 0;
			}
			d = que1.top().first; posm = que1.top().second; que1.pop();
		} while (used[posm]);
		used[pos] = true; used[posm] = true;
		ans += c + d;
		func(pos);
	}
	bool flag = true;
	for (int i = 0; i < n; ++i) flag &= merged[i];
	if (flag) cout << ans << endl;
	else cout << "Impossible" << endl;
	return 0;
}

Measured memory_bytes: 13424
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    int n,x;
    cin >> n >> x;
    int l[n];
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    
    int d[n+1];
    d[0] = 0;
    int ans = 1;
    for (int i = 1; i < n+1; i++) {
        d[i] = d[i-1] + l[i-1];
        if (d[i] <= x) {
            ans++;
        } else {
            break;
        }
    }
    
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
// AtCoder Grand Contest 005
// B - Minimum Sum

#include <cstdio>
#include <algorithm>
#define MAX_N 200000
using namespace std;

typedef long long int ll;
typedef pair<int, int> PII;


// 5 4 8 1 2 6 7 3

class UnionFind{
  public:
    void init(int n);
    void unite(int a, int b);
    bool same(int a, int b);
    int left(int a);
    int right(int a);
  private:
    int root(int a);
    int par[MAX_N];
    int rank[MAX_N];
    int l[MAX_N], r[MAX_N];
};

void UnionFind::init(int n) {
  int i;

  for (i = 0; i < n; i++) {
    par[i] = i;
    l[i] = r[i] = i;
    rank[i] = 0;
  }
  return;
}

void UnionFind::unite(int a, int b) {
  a = root(a);
  b = root(b);
  if (a == b) {
    return;
  }
  if (rank[a] < rank[b]) {
    par[a] = b;
    l[b] = min(l[a], l[b]);
    r[b] = max(r[a], r[b]);
  } else {
    par[b] = a;
    l[a] = min(l[a], l[b]);
    r[a] = max(r[a], r[b]);
    if (rank[a] == rank[b]) {
      rank[a]++;
    }
  }
  return;
}

bool UnionFind::same(int a, int b) {
  return root(a) == root(b);
}

int UnionFind::root(int a) {
  if (par[a] != a) {
    par[a] = root(par[a]);
  }
  return par[a];
}

int UnionFind::left(int a) {
  return l[root(a)];
}

int UnionFind::right(int a) {
  return r[root(a)];
}


int N;
int A[MAX_N];
UnionFind uf;
ll ans;

int main() {

  PII a_sorted[MAX_N];
  int idx;

  scanf("%d", &N);
  uf.init(N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    a_sorted[i] = make_pair(A[i], i);
  }
  sort(a_sorted, a_sorted + N);

  ans = 0;
  for (int i = N - 1; i >= 0; i--) {
    idx = a_sorted[i].second;
    if (idx - 1 >= 0 && A[idx - 1] > A[idx]) {
      uf.unite(idx - 1, idx);
    }
    if (idx + 1 < N && A[idx + 1] > A[idx]) {
      uf.unite(idx + 1, idx);
    }
    // printf("A[%d] = %d, l: %d, r: %d\n", idx, A[idx], uf.left(idx), uf.right(idx));
    ans += (ll)(uf.right(idx) - idx + 1) * (idx - uf.left(idx) + 1) * A[idx];
  }

  printf("%lld\n", ans);

  return 0;

}




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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<string> vs;
const ll mod = 1e9+7;
const ll inf = 1e17;
const int INF = 1e9;
const double PI = acos(-1);
#define fo(i, a, b) for (int i = a; i < b; i++)
#define re(i, n) fo(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(s) s.begin(), s.end()
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
int main()
{
  int n;
  cin >> n;
  char c;
  bool f = false;
  re(i, n) {
    cin >> c;
    if(c == 'Y') f = true;
  }
  if(f) cout << "Four" << endl;
  else cout << "Three" << endl;

  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> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int ctoi(char c){
    return (int)(c - '0');
}

int main() {
    string S;
    cin >> S;

    int sum;
    string ans;

    const int nmax = 3;
    rep(i, 1 << (nmax)){
        ans = S[0];
        sum = ctoi(S[0]);
        bitset<nmax> bit(i);
        rep(j, nmax){
            if(bit.test(j)){
                sum += ctoi(S[j + 1]);
                ans += "+";
            } else {
                sum -= ctoi(S[j + 1]);
                ans += "-";
            }
            ans += S[j + 1];
        }
        if(sum == 7){
            break;
        }
    }

    cout << ans << "=7" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(){
    int x, y;
    cin >> x >> y;
    if(x > y)
        cout << "a > b" << endl;
    else if(x < y)
        cout << "a < b" << endl;
    else
        cout << "a == b" << endl;
    return 0;
}


Measured memory_bytes: 3088
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (long long  i = 0; i < (long long)(n); i++)






int main() {
	long long N;
	cin >> N;
	vector<int> vec(N);
	long long sm = 0;
	for (long long i = 0; i < N; i++) {
		cin >> vec.at(i);
	}
	if (N % 2 == 0) {
		rep(i, N / 2) {
			cout << vec.at(N - 2 * i - 1) << " ";
		}
		rep(i, N / 2) {
			cout << vec.at( 2 * i) << " ";
		}
	}
	else {
		rep(i, (N+1) / 2) {
			cout << vec.at(N - 2 * i-1) << " ";
		}
		rep(i, (N- 1) / 2) {
			cout << vec.at( 2 * i + 1) << " ";
		}
	}
	


}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P; 
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    map<string, int> mp;
    rep(i, n){
        string tmp;
        cin >> tmp;
        mp[tmp]++;
    }
    int count = 0;
    for (auto a: mp){
        count++;
    }

    cout << count << endl;

    
    return 0;
}

Measured memory_bytes: 19248
/* 競プロ用のテンプレ
 * SKMT
 * 作成日   2020年09月06日  16:06
 * ファイル名    bishop.cpp
 * 解けなかった...
 */
#include<bits/stdc++.h>
using namespace std;

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

int main(int argc, char const* argv[]){
	long long H,W; //表現できる値が10^9くらいでも大丈夫?
	long long res;
	cin>>H>>W;
	if(H==1 || W==1){
		cout << 1 << endl;
		res=1;
	}
	else {
		res=(H*W+1)/2;
		cout << (H*W +1)/2 << endl;
	}
	return 0;
}


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

int main(void){
    int ans, tmp, i, j, k, min, max;
    int N, M; cin >> N >> M;

    vector<int> L(M);
    vector<int> R(M);

    for (i = 0; i < M; i++) {
        cin >> L.at(i) >> R.at(i);
    }

    min = *min_element(R.begin(), R.end());
    max = *max_element(L.begin(), L.end());
    if (min - max >= 0) {
        cout << min - max + 1 << endl;
    }else {
        cout << '0' << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,k;
  cin>>n>>k;
  if(n%k==0) cout<<"0\n";
  else{
    n=n%k;
    if(n<=abs(n-k)) cout<<n<<"\n";
    else cout<<abs(n-k)<<"\n";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

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

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n, m;
bool d[4];
int dd[4];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;

  bool f = true;

  REP(i, m) {
    int s, c;
    cin >> s >> c;

    if(s == 1 && c == 0 && n != 1) {
      f = false;
    } else if(d[s] && dd[s] != c) {
      f = false;
    } else {
      d[s] = true;
      dd[s] = c;
    }
  }

  if(f) {
    FOR(i, 1, n + 1) {
      if(d[i]) cout << dd[i];
      else cout << (i == 1 && n > 1 ? 1 : 0);
    }
    cout << endl;
  } else {
    cout << -1 << endl;
  }
}


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

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

Measured memory_bytes: 1792
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int n = s.length();
    int cnt = 0;
    for(int i = 0;i < n;i+=2){
      if(s.charAt(i)=='p')cnt--;
    }
    for(int i = 1;i < n;i+=2){
      if(s.charAt(i)=='g')cnt++;
    }
    System.out.println(cnt);
  }
}

Measured memory_bytes: 24832
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  string t;
  cin >> t;
  int n = t.size();
  
  rep(i, n-1){
    if (t[i] == '?') cout << 'D';
    else cout << (t[i]);        
  }
  if (t[n-1] == '?') cout << 'D' << endl;
  else cout << (t[n-1]) << endl;        
  
return 0;
}

Measured memory_bytes: 3732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, y, a[100005], b[100005];
char s[100005], t[100005];

int main()
{
	scanf("%s%s",s+1,t+1);
	x = strlen(s+1);
	y = strlen(t+1);
	for(ll i=1;i<=x;i++) {
		a[i] = a[i-1] + (s[i] - 'A' + 1);
	}
	for(ll i=1;i<=y;i++) {
		b[i] = b[i-1] + (t[i] - 'A' + 1);
	}
	ll Q;
	scanf("%lld",&Q);
	while(Q--) {
		ll A, B, C, D;
		scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
		puts((a[B]-a[A-1])%3 == (b[D]-b[C-1])%3 ? "YES" : "NO");
	}
}


Measured memory_bytes: 2304
#include<cstdio>
#include<algorithm>
#define re register
int m,n,k,ans = 0;
template <typename T>
inline void read(T &x){
    x = 0; char ch = getchar(); int f = 1;
    for(;ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1;
    for(;ch <= '9' && ch >= '0'; ch = getchar()) x = x * 10 + ch - '0';
    x *= f;
}
int main(){
    read(m); read(n); read(k);
    ans += (n / k); ans -= (m / k);
    if(m % k == 0) ans++;
    printf("%d\n",ans);
    return 0;
}
/*

*/

Measured memory_bytes: 1596
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
 
ll d[10005] ;
 int main(){
 ll n ; cin>> n ;
  rep2(a,1,100){
    rep2(b,1,100){
      rep2(c,1,100){
       ll ans= a*a+b*b+c*c+a*b+b*c+c*a ;
        if(ans<=n) d[ans]++ ;
      }
    }
  }
  
  rep2(i,1,n){
    cout<<d[i]<<endl ;
  }

   return 0 ;
 }



Measured memory_bytes: 3596
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define itn ll
#define int ll
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
///                →,↑,←,↓,↗,↖,↙,↘
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };


static const int N = 1000;
int c[N + 1][N + 1];

int lcs(string X, string Y) {
	int maxl = 0;
	int i, j;
	int m = X.size();
	int n = Y.size();
	X = ' ' + X;
	Y = ' ' + Y;
	FOR(i, 1, m+1) {
		c[i][0] = 0;
	}
	FOR(i, 1, n+1) {
		c[0][i] = 0;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (X[i] == Y[j]) {
				c[i][j] = c[i - 1][j - 1] + 1;
			}
			else {
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
			}
			maxl = max(c[i][j], maxl);
		}
	}
	return maxl;
}

signed main() {
	ios::sync_with_stdio(false);
	int n;
	string s1, s2;
	cin >> n;
	int i;
	rep(i, n) {
		cin >> s1 >> s2;
		cout << lcs(s1, s2) << "\n";
	}
	return 0;
}


Measured memory_bytes: 11012
import sys
import random

def rd():
        return sys.stdin.readline().rstrip()

def rdi():
        return [ int(x) for x in rd().split() ]


def calc3(h, w):
        W = H = "x"
        r = []
        for a in range(h/3-3, h/3+4):
                if a < 0 or a > h:
                        continue
                for b in range(w/2-2, w/2+3):
                        if b < 0 or b > w:
                                continue
                        S1 = a * w
                        S2 = (h - a) * b
                        S3 = (h - a) * (w - b)
                        assert S1 + S2 + S3 == w * h
                        q = max(S1, S2, S3) - min(S1, S2, S3)
                        r.append(q)
                for b in range((h-a)/2-2, (h-a)/2+3):
                        if b < 0 or b > h-a:
                                continue
                        S1 = a * w
                        S2 = b * w
                        S3 = (h - a - b) * w
                        assert S1 + S2 + S3 == w * h
                        q = max(S1, S2, S3) - min(S1, S2, S3)
                        r.append(q)
        return min(r)

H, W = rdi()

print min(calc3(H, W), calc3(W, H))


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

using namespace std;

int main()
{
    string S, T;
    cin >> S;
    int count=0;
    bool flag = true;
    while(1){
        //cout << count << endl;
        if (S.size()-1 < count) break;
        if (S.substr(count, 5) == "dream"){
            if(count + 6 < S.size() && S.substr(count+5, 2) == "er"){
                if(count + 7 < S.size() && S.substr(count+7, 1) == "a"){
                    count += 5;
                }
                else{
                    count += 7;
                }
            }
            else{
                count += 5;
            }
        }
        else if(S.substr(count, 5) == "erase"){
            if(count + 5 < S.size() && S.substr(count+5, 1) == "r"){
                count += 6;
            }
            else{
                count += 5;
            }
        }
        else{
            flag = false;
            break;
        }
    }
    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}


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

int main()
{
    int n,sum=0;
    cin >> n;
    vector<int> p(2*n);
    for(int i=0;i<2*n;i++) cin >> p[i];
    sort(p.begin(),p.end());
    for(int i=0;i<2*n;i++){
        if(i%2==0){
            sum+=p[i];
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{long long n,i,sum;
 while(~scanf("%I64d",&n))
 {sum=1;
  for(i=2;i<=n;i++)
  sum=(sum*i)%(10*10*10*10*10*10*10*10*10+7);
  printf("%I64d\n",sum%(10*10*10*10*10*10*10*10*10+7));
 }
 return 0;
}


Measured memory_bytes: 128
//1DReversi.cpp (C)
#include <iostream>
#include <string>
using namespace std;

int main(){
  string S;
  char C;
  cin >> S;
  C = S[0];
  int Ans = 0;
  for(int i = 1; i < S.size(); i++){
    if(C != S[i]) ++Ans, C = S[i];
  }
  printf("%d\n", Ans);

  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll a[100100],b[100100],c[100100];
ll dp[100100],f[100100],g[100100];
int main(){
	int n;
	scanf("%d",&n);
	for(register int i=1;i<=n;i++){scanf("%lld",&a[i]);}
	for(register int i=1;i<=n;i++){scanf("%lld",&b[i]);}
	for(register int i=1;i<=n;i++){scanf("%lld",&c[i]);}
	sort(a+1,a+1+n);sort(b+1,b+1+n);sort(b+1,b+1+n);
	for(register int i=1;i<=n;i++) dp[i]=i;
	for(register int i=1;i<=n;i++){
		int k=lower_bound(a+1,a+1+n,b[i])-a;f[i]=dp[k-1];
	}
	for(register int i=1;i<=n;i++) f[i]+=f[i-1];
	for(register int i=1;i<=n;i++) {
		int k=lower_bound(b+1,b+1+n,c[i])-b;g[i]=f[k-1];
	}
	for(register int i=1;i<=n;i++) g[i]+=g[i-1];
	printf("%lld\n",g[n]);
	return 0;
} 

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

void solve(long long N, long long A, long long B, vector<long long> v){
	sort(v.begin(), v.end(), greater<ll>());
	double avg = 0.0;
	ll sum = 0, idx = 0, res = 0, start = -1;
	for (int i=0; i<A; i++) {
		avg += v[i];
	}
	avg /= A;

	idx = 0;
	for (int i=0; i<N; i++) {
		if (v[A-1] == v[i]) idx++;
		if (start == -1 && v[A-1] == v[i]) start = i+1;
	}
	
	ll idxci[idx+1];
	idxci[0] = 1;
	for (int i=1; i<idx; i++) {
		idxci[i] = idxci[i-1]*(idx-(i-1))/i;
	}
	idxci[idx] = 1;

	if (v[0] == v[A-1]) {
		for (int i=A-start+1; i<=B-start+1; i++) {
			if (idx >= i) res += idxci[i];
		}
	} else {
		for (int i=A-start+1; i<=A-start+1; i++) {
			if (idx >= i) res += idxci[i];
		}
	}

	

	printf("%.15f\n", avg);
	cout << res << endl;
}

int main(){	
	long long A;
	long long N;
	long long B;
	scanf("%lld",&N);
	vector<long long> v(N-1+1);
	scanf("%lld",&A);
	scanf("%lld",&B);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&v[i]);
	}
	solve(N, A, B, v);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;
  int part = S.size() / 2;
  
  int SS = S.size();
  
  int count = 0;
  for(int i = 0; i < part; i++){
    
    if(S.at(i) != S.at(SS - i - 1)){
      count++;
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <algorithm>
#include <iostream>
#include<string>


int main() {
  string s,t;
  cin >> s >> t;
  t.erase(t.size() - 1);
  if (s == t) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}



Measured memory_bytes: 3592
#include<stdio.h>
int main()
{
	int a,b;
	char op;
	scanf("%d %c %d",&a,&op,&b);
	if(op=='+')    printf("%d\n",a+b);
	else if(op=='-')   printf("%d\n",a-b);
	return 0;
 } 

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>
#include<map>
#include<cmath>

using namespace std;

#define ll long long

map<ll,ll> prime;//素因数分解でそれぞれの素数がいくつ出てきたかを保存するmap

set<long long> st;

//O(√n)
//整列済み(mapはkeyで自動で整列される)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    for(long long i=2;i<=l;i++){
        if(n%i==0){
        prime_factorize(i);prime_factorize((ll)(n/i));return;
        }
    }
    //mapでは存在しないkeyの場合も自動で構築される
    prime[n]++;
    st.insert(n);
    return;
}

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

	vector<long long> vec;
	for(long long i=1;i<=sqrt(n);i++)
		vec.push_back(i*(i+1)/2);
	
	long long ans=0;
	for(auto stitr = st.begin(); stitr != st.end(); ++stitr)
	{
		long long i=*stitr;
		auto itr=upper_bound(vec.begin(),vec.end(),prime[i]);
		ans+=(long long)(itr-vec.begin());
	}
	cout << ans << endl;




}

Measured memory_bytes: 11248
#include <stdio.h>

int main( void ) {
	int n, y, m, d, tmp;

	scanf( "%d", &n );

	while ( n-- ) {
		scanf( "%d %d %d", &y, &m, &d );
		y--;
		m--;
		d--;

		tmp = y / 3 * 590 + y % 3 * 195 + d;
		if ( ( y + 1 ) % 3 ) {
			tmp += m / 2 * 39;
			if ( m % 2 )
				tmp += 20;
		} else 
			tmp += m * 20;

		printf( "%d\n", 196470 - tmp );
	}

	return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<cmath>
#include<algorithm>
double a[1002][1002]={};
int n;
double d[1002];
bool used[1002];
void dijkstra(){
	for(int i=0;i<n+2;i++){
		d[i]=10000000000000;
	}
	for(int i=0;i<n+2;i++){
		used[i]=false;
	}
	d[0]=0;
	while(true){	
		int v=-1;
		for(int u=0;u<n+2;u++){
			if(!used[u] && (v==-1 || d[u]<d[v]))v=u;
		}
		if(v==-1)break;
		used[v]=true;
		for(int u=0;u<n+2;u++){
			d[u]=std::min(d[u],d[v]+a[v][u]);
		}
	}
}
int main(){
	long long int xs,ys,xt,yt;
	scanf("%lld%lld%lld%lld%d",&xs,&ys,&xt,&yt,&n);
	long long int x[n+2]={};
	long long int y[n+2]={};
	long long int r[n+2]={};
	x[0]=xs;
	y[0]=ys;
	x[n+1]=xt;
	y[n+1]=yt;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&x[i],&y[i],&r[i]);
	}
	for(int i=0;i<n+2;i++){
		for(int j=0;j<n+2;j++){
			a[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-(r[i]+r[j]);
			if(a[i][j]<0)a[i][j]=0;
		}
	}
	dijkstra();
	printf("%.11e",d[n+1]);
	return 0;
}

Measured memory_bytes: 8064
#include <stdio.h>

int main(void)
{
    
    int a,b,c,sum=0,ans=0;
    
    scanf("%d %d %d",&a,&b,&c);
    
    while(sum!=-1){
        sum=sum+a;
        ans=sum%b;
        if(ans==c){
            printf("YES");
            return 0;
        }
        if(sum>10000)sum=-1;
    }
    printf("NO");
    
    return 0;
}

Measured memory_bytes: 128