akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<class T> void DEBUG(string str, T e){if(DEBUG_OUT == false)return;std::cout <<str << ">>" << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == 1)return;for(const auto& v : vv){ DEBUG(v); } }
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T> void SORT_(std::vector<T>& v,bool GREATER = 0){if(GREATER == 0)sort(v.begin(),v.end());else{sort(v.begin(),v.end(),std::greater<T>());}}

//CODE
void solve(void)
{
  int N;
  cin>>N;
  int K;
  cin>>K;
  vector<int> data(N);
  for (int i = 0; i < N; i++)
  {
    cin>>data[i];
  }
  SORT_(data);
  int ANS = INF;
  for (int i = 0; i <= N - K ; i++)
  {
    ANS = min(ANS,abs(data[i + K -1] - data[i]));
  }
  
  cout<<ANS<<endl;
  
  return;
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

 
  return 0;
}

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

ll mod = 1e9+7;
int main() {
    int n; cin >> n;
    ll ans = 1, num = 1, res = 1;
    for(int i=0; i<n; i++) {
        ans *= 10;
        num *= 9;
        res *= 8;
        ans %= mod;
        num %= mod;
        res %= mod;
    }
    num *= 2;
    num %= mod;
    cout << (ans - num + res + mod) % mod << endl;
}

Measured memory_bytes: 3616
#include<iostream>
#include<stdio.h>
using namespace std;

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

int main()
{
    int min,max,a,b;
    while(scanf("%d %d",&a,&b)!=EOF)
    {
    max = gcd(a,b);
    min = (a/max)*(b/max)*max;
    cout << max << " " << min<<endl;
    }
    return 0;
}



Measured memory_bytes: 3164
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 2e5 + 10 , M = N * 4;
int n , du[N] , col[N] , odd[N] , h[N] , cur[N];
int ne[M] , to[M] , vis[M] , e;
inline void add(int u,int v){
    to[e] = v;ne[e] = h[u];
    h[u] = e++;
}
inline void link(int u,int v){
    du[u]++;
    du[v]++;
    add(u , v);
    add(v , u);
}

int top;
void dfs(int c){
    for(int &k=cur[c];~k;k=ne[k]){
        if(vis[k >> 1]) continue;
        vis[k >> 1] = true;
        dfs(to[k]);
    }
    if(top != -1) {
        int a = top , b = c , f = 1;
        if(a > b) swap(a , b) , f = -1;
        if(a < n && a + n == b && odd[a]) {
            col[a] = f;
        }
    }
    top = c;
}

int main(){
    scanf("%d",&n);
    int rt = n + n;
    rep(i,0,rt+1) h[i] = -1;
    rep(t,0,2) {
        rep(i,0,n) {
            int a;
            scanf("%d",&a);
            if(a == -1) link(rt , i + t * n);
            else {
                a = a - 1 + t * n;
                link(a , i + t * n);
            }
        }
    }
    rep(i,0,n) {
        if((du[i] + du[i + n]) & 1){
            return puts("IMPOSSIBLE") , 0;
        }
        if(du[i] & 1) {
            link(i , i + n);
            odd[i] = true;
        }
    }
    rep(i,0,rt+1) cur[i]=h[i];
    top = -1;
    dfs(rt);
    puts("POSSIBLE");
    rep(i,0,n) printf("%d%c",col[i]," \n"[i+1==n]);
    return 0;
}


Measured memory_bytes: 22016
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  if(a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0) cout << "Possible" << endl;
  else cout << "Impossible" << endl;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,a,b) for(int i=(int)(a-1);i>=b;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

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

#define INF LONG_MAX / 3

ll sum[200001];

int main(){
    cin.sync_with_stdio(false);
    int n, a;
    cin >> n;
    repl(i, 1, n + 1) {
        cin >> a;
        sum[i] = sum[i - 1] + a;
    }
    ll mini = INF;
    repl(i, 1, n) minch(mini, abs((sum[n] - sum[i]) - sum[i]));
    cout << mini << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = 2000000000;
// const ll MOD = 1000000007;

string S;

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

  // case 01...
  int min0 = 0;
  for (int i = 0; i < S.size(); i++) {
    if (i % 2 == 0) {
      if (S[i] == '1') {
        min0++;
      }
    } else {
      if (S[i] == '0') {
        min0++;
      }
    }
  }

  // case 10...
  int min1 = 0;
  for (int i = 0; i < S.size(); i++) {
    if (i % 2 == 0) {
      if (S[i] == '0') {
        min1++;
      }
    } else {
      if (S[i] == '1') {
        min1++;
      }
    }
  }

  cout << min(min0, min1) << endl;
  return 0;
}

Measured memory_bytes: 512
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair
#include <cmath>
#include <random>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

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

template <class InputIterator, class T>
bool contains_itr(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class T>
bool contains_set(set<T> st, const T &value)
{
    if (st.find(value) == st.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

random_device seed_gen;
mt19937 engine(seed_gen());
// 0, 1, 2 のどれかが得られる一様分布
// uniform_int_distribution<> dist(0, 2);
// cout << dist(engine) << endl;
// みたいに、先に確率分布を宣言して、そこにengineを与えて使う。

// =========ここまでテンプレ============

int main()
{
      bool aho[60000000000];
    ll n, x, t;
    cin >> n >> x >> t;
    ll m = n / x;
    if (n % x != 0)
    {
        ++m;
    }
    cout << t * m << endl;
    return 0;
}


Measured memory_bytes: 3204
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define _for(i, j, k) for(int i=j; i<=k; i++)

int read() {
	int x=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) x=x*10+c-'0', c=getchar();
	return x;
}
int buf[20];
void prt(int x) {
	memset(buf, 0, sizeof(buf));
	int index=0;
	while (x) buf[++index]=x%10, x/=10;
	while (index>=1) putchar(buf[index--]+'0');
	return;
}

const int LIM = 1e5+10;

struct stu {
	int i, v;
} a[LIM];

struct cmp {
	inline bool operator () (stu a, stu b) {
		return a.v < b.v;
	}
};

int main() {
	int n=read();
	_for(i, 1, n) a[i].i=i, a[i].v=read();
	std::sort(a+1, a+1+n, cmp());
	_for(i, 1, n) prt(a[i].i), putchar(' ');
	return 0;
} 

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

typedef long long ll;
typedef pair<ll, ll> p;

ll n;
ll resv = 0;

ll dp[100][100];


ll f(int start, int end){
  // cout << start << ' ' << end << endl;
  ll tmpv = 0;
  if(start == 0) return 0;

  if(start == end && start <= n) {
    resv++;
    tmpv++;
  }

  // cout << stoi(to_string(start) + to_string(end)) << endl;
  if(stoi(to_string(start) + to_string(end)) <= n) {
    resv++;
    tmpv++;
  }

  for (int i = 0; i < 30000; i++) {
    string tmp = to_string(i);
    string res = to_string(start) + tmp + to_string(end);
    if(stoi(res) <= n){
      resv++;
      tmpv++;
    }
    if(i < 1000){
      tmp = "0" + to_string(i);
      res = to_string(start) + tmp + to_string(end);
      if(stoi(res) <= n){
        resv++;
        tmpv++;
      }
    }

    if(i < 100){
      tmp = "00" + to_string(i);
      res = to_string(start) + tmp + to_string(end);
      if(stoi(res) <= n){
        resv++;
        tmpv++;
      }
    }

    if(i < 10){
      tmp = "000" + to_string(i);
      res = to_string(start) + tmp + to_string(end);
      if(stoi(res) <= n) {
        resv++;
        tmpv++;
      }
    }
  }
  return dp[start][end] = tmpv;
}

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

  for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
      dp[i][j] = -1;
    }
  }

  for (int i = 1; i <= n; i++) {
    if(i < 10) f(i, i);
    else {
      int n = int(to_string(i).size());
      if(dp[to_string(i)[n-1] - '0'][to_string(i)[0] - '0'] == -1)
        f(to_string(i)[n-1] - '0', to_string(i)[0] - '0');
      else resv += dp[to_string(i)[n-1] - '0'][to_string(i)[0] - '0'];
    }
    // cout << resv << endl;
  }

  cout << resv << endl;
}


Measured memory_bytes: 512
n=int(input())
h=[int(x) for x in input().split()]

m=max(h)
c=0

for i in range(1,m+1):
  s=-1
  for j in range(n):
    if s==-1 and h[j]>=i:
      s=j
    if s!=-1 and h[j]<i:
      s  =-1
      c += 1
  else:
    if s!=-1:
      c += 1

print(c)


Measured memory_bytes: 3064
def main():
    from collections import deque

    N = int(input())

    dq = deque()
    dq.append(0)

    ans = 0
    while dq:
        x = dq.popleft()
        for a in (7, 5, 3):
            t = x * 10 + a
            if t > N: continue
            if all(c in str(t) for c in '753'):
                ans += 1
            dq.append(t)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 4076
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		UnionFind uf = new UnionFind(n + 1);
		for (int i = 0; i < k; i++) {
			int m = sc.nextInt();
			int r = sc.nextInt();
			for (int j = 0; j < m - 1; j++) {
				int nr = sc.nextInt();
				uf.unite(r, nr);
				r = nr;
			}
		}
		int R = sc.nextInt();
		Set<Integer> set = new HashSet<Integer>();
		for (int i = 0; i < R; i++) {
			int p = sc.nextInt();
			int q = sc.nextInt();
			if (uf.same(p, q)) {
				set.add(p);
				set.add(q);
			}
		}
		System.out.println(set.size());
	}
}

class UnionFind {
	public int par[];
	public int rank[];

	UnionFind(int n) {
		par = new int[n];
		rank = new int[n];
		for (int i = 0; i < n; i++) {
			par[i] = i;
		}
	}

	public int find(int x) {
		if (par[x] == x) {
			return x;
		} else
			return par[x] = find(par[x]);
	}

	public void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)
			return;
		if (rank[x] > rank[y]) {
			par[y] = x;
		} else {
			par[x] = y;
			if (rank[x] == rank[y])
				rank[y]++;
		}
	}

	public boolean same(int x, int y) {
		return find(x) == find(y);
	}
}

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

int H, W, D;
int A[300][300];
int X[90010];
int Y[90010];
ll sum[90010];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	cin >> H >> W >> D;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			cin >> A[i][j];
			X[A[i][j]] = j;
			Y[A[i][j]] = i;
		}
	}

	for(int i = 1; i <= H * W; i++){
		sum[i + D] += sum[i] + abs(X[i] - X[i + D]) + abs(Y[i] - Y[i + D]);
	}

	int Q;
	cin >> Q;
	while(Q--){
		int L, R;
		cin >> L >> R;
		cout << sum[R] - sum[L] << endl;
	}
}


Measured memory_bytes: 2944
#include <stdio.h>

int main(void)
{
	int result;
	int value;
	char op[2];

	scanf("%d", &result);
	while (scanf("%s", op), *op != '='){
		scanf("%d", &value);
		switch (*op){
		  case '+':
		  	result += value;
		  	break;
		  case '-':
		  	result -= value;
		  	break;
		  case '*':
		  	result *= value;
		  	break;
		  case '/':
		  	result /= value;
		  	break;
		}
	}
	printf("%d\n", result);

	return (0);
}

Measured memory_bytes: 596
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	int a,b,c,k;
	scanf("%d",&k);
	if(k==1)printf("Hello World\n");
	else{
		scanf("%d%d",&a,&b);
		c=a+b;
		printf("%d\n",c);
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long gcd(long long a,long long b)
{
    if (a%b==0) return(b);
    else return(gcd(b,a%b));
}
 long long lcm(long long a,long long b){
 long long g = gcd(a,b);
 return a / g * b; 
 }
int main(void){
    int n,m; cin>>n>>m;
    string s,t; cin>>s>>t;
    ll sl=s.size(), tl=t.size();
    ll mi = lcm(sl,tl);
    vector <int> checks, checkt;
    int x = 0;
    while(x<=sl){
        checks.push_back(x);
        x+= mi/tl;
    }
    x = 0;
    while(x<=tl){
        checkt.push_back(x);
        x+= mi/sl;
    }
    for(int i=0;i<checks.size();i++){
        
        if(s[checks[i]] != t[checkt[i]]) {cout<<-1<<endl; return 0;}
    }
    cout<<mi<<endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> fill(int r, int c, T t){return v2<T>(r, vector<T>(c, t));}

const int MOD = 998244353;
inline int add(int a, int b){return (a+b)%MOD;}
inline int sub(int a, int b){return ((a-b)%MOD + MOD)%MOD;}
inline int mul(int a, int b){return ((ll)a*b)%MOD;}

int a, b, c, d;
v2<int> dp;
void solve(){
    cin >> a >> b >> c >> d;
    dp = fill(c+1, d+1, -1);
    for(int i = a; i <= c; i++){
        for(int j = b; j <= d; j++){
            if(i==a && j==b) dp[i][j] = 1;
            else if(i==a) dp[i][j] = mul(dp[i][j-1], i);
            else if(j==b) dp[i][j] = mul(dp[i-1][j], j);
            else dp[i][j] = sub(add(mul(dp[i][j-1], i), mul(dp[i-1][j], j)), mul(mul(i-1, j-1), dp[i-1][j-1]));
        }
    }
        
    cout << dp[c][d] << '\n';
}

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


Measured memory_bytes: 38556
//Abhinav ---IIIT_A
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define f(i,x,n) for(int i=x;i<(int)n;++i)
#define vpii vector<pair<int,int>> 
ld pie=3.141592653589793238462643383279;
int mod=1e9+7;
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};


int dig(int a){
  int r=0;
  while(a!=0){
    int xp=a%10;
    a/=10; if(xp==1) ++r;
  }
  return r;
}

int fact[2000005];
int infact[2000005];

int inv(int a){
  int y=mod-2;
  int r=1;
  while(y!=0){
    if(y&1){
      r*=a; r%=mod;
    }
    y/=2; a*=a; a%=mod;
  }
  return r;
}

int po(int a,int y){
  int r=1;
  while(y!=0){
    if(y&1){
      r*=a; r%=mod;
    }
    y/=2; a*=a; a%=mod;
  }
  return r; 
}

void facto(){
  fact[0]=1;
  f(i,1,2000005) {fact[i]=i*fact[i-1]; fact[i]%=mod;}
  f(i,0,2000005) infact[i]=inv(fact[i]); 
}

int nck (int n,int k){
  if(k<0 || k>n) return 0;
  int ret=fact[n]; ret*=infact[k]; ret%=mod;
  ret*=infact[n-k]; ret%=mod;
  return ret;
}
void q1(){
  string s; cin>>s;
  if(s>="a" && s<="z") cout<<"a";
  else cout<<"A";
}
void q2(){
  int n,k; cin>>n>>k;
  int a[n]; f(i,0,n) cin>>a[i];
  sort(a,a+n);
  int s=0;
  f(i,0,k)s+=a[i];
  cout<<s;
}
void q3(){
  string ret="";
  int a; cin>>a;
  while(a!=0){
    a--;
    ret+=(a%26 +'a');
    a/=26;
  }
  reverse(ret.begin(),ret.end());
  cout<<ret;
}
void q4(){
  int n; cin>>n;
   int a[100005]={0};
   int s=0;
  f(i,0,n){
    int x; cin>>x;
    s+=x;
    a[x]++;
  }
  int q; cin>>q;
  while(q--){
    int b,c; cin>>b>>c;
    s-=a[b]*b;
    s+=a[b]*c;
    a[c]+=a[b];
    a[b]=0;
    cout<<s<<"\n";
  }
 
}
void q5(){
  int n; cin>>n;
  int x=0;
  int a[n]; f(i,0,n){
    cin>>a[i];
    x^=a[i];
  } 
   f(i,0,n) cout<<(x^a[i])<<" ";
}
int32_t main(){
#ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  q1();
  return 0;
  facto();
  int k; cin>>k;
  string s; cin>>s;
  int l=k+s.size();
  int xp=s.size();
  // total = 26^l - those which do not contain subsequence
  // --- i= 0 to  xp-1 prefix present as subseqeunce and remaining have 25^(l-i)
  int ret=1;
  f(i,0,l){
    ret*=26; ret%=mod;
  }
  int sub=0;

  f(i,0,xp){
    // l choose i
    sub+= (nck(l,i)*po(25,l-i));
    sub%=mod; 
  }

  cout<<((ret-sub)%mod + mod) %mod <<"\n";
  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int count = 0, maxval = 0;
  string s;
  cin >> s;
  for(int i = 0; i < 3; i++){
    if(s[i] == 'S'){
      count = 0;
    }else count++;
    maxval = max(maxval, count);
  }
  cout << maxval << endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int CommomSubsequencesCount(vector<int>s,vector<int>t) 
{ 
	int n1 = s.size(); 
	int n2 = t.size(); 
	long long int dp[n1+1][n2+1]; 

	for (int i = 0; i <= n1; i++) { 
		for (int j = 0; j <= n2; j++) { 
			dp[i][j] = 0; 
		} 
	} 

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

		for (int j = 1; j <= n2; j++) { 

			if (s[i - 1] == t[j - 1]) 
				dp[i][j] = ((long long int)1 + dp[i][j - 1] + dp[i - 1][j])%mod;			 
			else
				dp[i][j] =(((dp[i][j - 1] + dp[i - 1][j]) -	dp[i - 1][j - 1])+mod)%mod;			 
		} 
	} 

	return (dp[n1][n2]+1)%mod;
} 
 
int main() 
{ 
    vector<int>s,t;
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int b;
        cin>>b;
        s.push_back(b);
    }
    
    for(int i=0;i<m;i++)
    {
        int b;
        cin>>b;
        t.push_back(b);
    }
	cout << CommomSubsequencesCount(s, t)%mod << endl; 
	return 0; 
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>0;(i)--)
#define rrep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define rrepr(i,n,m) for(int (i)=(n);(i)>(m);(i)--)
#define esort(s) sort((s).begin(),(s).end())

typedef long long ll;
typedef pair<int,int> ipair;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

const int INF = 1000000000;
const ll LINF = 1000000000000000000;
const double PI = acos(-1.0);
const double EPS = 1e-10;

const ll MOD = 1000000007ll;
const int MAX=510000;

void solve(){
    int N,T;cin>>N>>T;
    vector<pair<int,int>> P(N);
    rep(i,N){
        cin>>P[i].first>>P[i].second;
    }
    sort(P.begin(),P.end());
    // for(auto p:P){
    //     cout<<p.second<<" "<<p.first<<"\n";
    // }
    int ans=0;
    int dp[N+10][T+10];
    rep(i,T) dp[0][i]=0;
    rrep(i,1,N+1){
        rep(j,T){
            ans=max(ans,dp[i-1][j]+P[i-1].second);
            if(j>=P[i-1].first) dp[i][j]=max(dp[i-1][j],dp[i-1][j-P[i-1].first]+P[i-1].second);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<ans<<endl;
}

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

    solve();
    return 0;
}

Measured memory_bytes: 35712
S = input()
N = len(S)
def kaibun(s,n):
    for i in range(n//2):
        if(s[i]!=s[n-i-1]):
            return False
    return True

if(kaibun(S,N) & kaibun(S[0:(N+1)//2-1],N//2) & kaibun(S[N:(N+3)//2-2:-1],N//2)):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
n = gets.to_i
dish = Array.new(n).map{Array.new(2, 0)}
for i in 0..n-1
  dish[i] = gets.split.map(&:to_i)
end
tk = Array.new(n, 0)
ao = 0
ans = 0
for i in 0..n-1
  tk[i] = dish[i][0] + dish[i][1]
  ao += dish[i][1]
end
tk.sort!
for i in 1..n
  if i % 2 == 1
    ans += tk[-i]
  end
end
puts ans - ao


Measured memory_bytes: 19448
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long M = sc.nextLong();
		long ans = 0;


		if (N > M) {
			System.out.println(M/2);
			System.exit(0);
		}

		if (N == 1 && M ==1) {
			System.out.println(0);
			System.exit(0);
		}

		if (N == 2 && M ==1) {
			System.out.println(0);
			System.exit(0);
		}

		if (N * 2 > M) {
			System.out.println(M/2);
			System.exit(0);
		}

		ans = N + ((M - N * 2) / 4);

//		for (;;){
//			if (M - 2 >= (N + 1) * 2) {
//				M = M - 2;
//				N = N + 1;
//			} else {
//				break;
//			}
//		}



		System.out.println(ans);
		sc.close();
	}



}



Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s[0]=='S' && s[1]=='S' && s[2]=='S') cout<<"0\n";
    else if(s[0]=='R' && s[1]=='R' && s[2]=='R') cout<<"3\n";
    else if( (s[0]=='R' && s[1]=='S' && s[2]=='S') || (s[0]=='S' && s[1]=='R' && s[2]=='S') || (s[0]=='S' && s[1]=='S' && s[2]=='R') || (s[0]=='R' && s[1]=='S' && s[2]=='R') )cout<<"1\n";
    else if( (s[0]=='R' && s[1]=='R' && s[2]=='S') || (s[0]=='S' && s[1]=='R' && s[2]=='R') ) cout<<"2\n";


}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int f=1,x=0;
    char ch;
    do{
        ch=getchar();
        if(ch=='-'){
            f=-1;
        }
    }while(ch<'0'||ch>'9');
    do{
        x=x*10+ch-48;
        ch=getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}
int main(){
    int a=read(),b=read();
    int c=a*b;
    if(c%2==1){
        cout<<"Odd";
    }
    else{
        cout<<"Even";
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int n, m , c; cin >> n >> m >> c;
    vector<int> B(m); REP(i, m) cin >> B[i];
    int ans = 0;
    REP(i, n){
        int count = 0;
        REP(j, m){
            int tmp;
            cin >> tmp;
            count += tmp * B[j];
        }
        count += c;
        if(count > 0) ans++;
    } 
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
const int M = 1'000'000'007;

int main() {
    int n, k;
    cin >> n >> k;
    ll ans = 0;
    for (ll i = k; i <= n + 1; i++) {
        ll mi = i * (i - 1) / 2, ma = mi + i * (n - i + 1);
        ans = (ans + (ma - mi + 1)) % M;
    }
    cout << ans << "\n";
}


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

using namespace std;
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n;
pair < int, int > a[N];



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

	for (int i = 1; i <= n; i ++) {
		int x, l;
		cin >> x >> l;
		a[i] = mp(x + l, x - l);
	}
	sort(a + 1, a + n + 1);
	int R = -inf;
	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		int l, r;
		tie(r, l) = a[i];
		if (R <= l) {
			ans ++;
			R = r;
		}
	}

	cout << ans;
	
   	return Accepted;
}

// B...a

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

int main()
{
    int a[3][3];
    int n;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            cin >> a[i][j];
        }
    }
    cin >> n;
    int b[n];
    for(int i=0; i<n; i++){
        cin >> b[i];
    }

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<n; k++){
                //cout << i << ":" << j << " = " << a[i][j] << ", b = " << b[k] << endl;
                if(a[i][j] == b[k]) a[i][j] = -1;
            }
        }
    }
    /*
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            cout << a[i][j] << ",";
        }
        cout << endl;
    }
    */
    
    // 縦
    for(int i=0; i<3; i++){
        if(a[i][0] == -1 && a[i][1] == -1 && a[i][2] == -1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    // 横
    for(int i=0; i<3; i++){
        if(a[0][i] == -1 && a[1][i] == -1 && a[2][i] == -1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    // 斜め
    if(a[0][0] == -1 && a[1][1] == -1 && a[2][2] == -1){
        cout << "Yes" << endl;
        return 0;
    }
    if(a[0][2] == -1 && a[1][1] == -1 && a[2][0] == -1){
        cout << "Yes" << endl;
        return 0;
    }   
    cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  int X; std::cin >> X;

  int ans = 1;
  for(int i=2; i<=std::sqrt(X); i++) {
    for(int p=2; ; p++) {
      if ( (int)std::pow(i,p) > X ) break;
      ans = std::max(ans, (int)std::pow(i,p) );
    }
  }
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{

    int x[5];
    for(int i=0;i<3;i++)
    {
        cin>>x[i];
    }
    sort(x,x+3);
    int s=x[2]-x[1];
    int d=x[0]+s;
    int l=x[2]-d;
    if(l%2==0)
    {
        cout<<s+(l/2)<<endl;
    }
    else
    {
        cout<<s+((l+1)/2)+1<<endl;
    }
return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
  
  public static List<Integer> parseAndSort(String[] sides) {
    List<Integer> list = new ArrayList<Integer>();
    for(String s: sides) {
      list.add(Integer.parseInt(s));
    }
    Collections.sort(list, Collections.reverseOrder());
    return list;
  }
  
  public static boolean isDrawPolygon(List<Integer> sideList) {
    int sum = 0;
    for(int i = 1; i < sideList.size(); i++) {
      sum += sideList.get(i);
    }
    return sideList.get(0) < sum ? true : false;
  }
      
  
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    
    while(scanner.hasNextLine()) {
      int n = Integer.parseInt(scanner.nextLine());
      
      String[] sides = scanner.nextLine().split(" ", 0);
      
      List<Integer> sideList = parseAndSort(sides);
      String result = isDrawPolygon(sideList) ? "Yes" : "No";
      System.out.println(result);
    }
  }
}

Measured memory_bytes: 23252
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N,L=rl()
azi = [L+i-1 for i in range(1,N+1)]
S = sum(azi)
ind = 0
M = INF
for i in range(N):
    a = azi[i]
    if abs(a) < M:
        M = abs(a)
        ind = i

print(S-azi[ind])

Measured memory_bytes: 3192
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cctype>
#include <string>
#include <vector>
#include <stack>
using namespace std;

#define Fill(ar, val) memset(ar, val, sizeof(ar))
#define MAX(i, j) ((i) > (j)) ? (i) : (j)
#define MIN(i, j) ((i) < (j)) ? (i) : (j)
#define ABS(i) (i) < 0 ? -(i) : i
#define PI (2 * acos(0))
#define SZ 100

int main(){

    int a, b, c;

    scanf("%d%d%d", &a, &b, &c);

    if((a < b || b > c)&& c == a){
        puts("NO");
        return 0;
    }
    if((a > b || b < c)&& c == a){
        puts("NO");
        return 0;
    }


    if((ABS(b - a)) == (ABS(c - b))) puts("YES");
    else puts("NO");

    return 0;

}


Measured memory_bytes: 256
using System;
using System.Linq;
 
public class Program
{
	public static void Main()
	{
		int[] input = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
		string[] arr = new string[input[0]];
		for (int i = 0; i < input[0]; i++)
		{
			arr[i] = Console.ReadLine();
		}
		Array.Sort(arr);
		Console.WriteLine(string.Join("", arr));
	}
}

Measured memory_bytes: 3288
#include<stdio.h>

int less(int a,int b){
  if(a<b) return a;
  else return b;
}

int least(int a,int b,int c){
  if(less(a,b)==a && less(a,c)==a) return a;
  else if(less(a,b)==b && less(b,c)==b) return b;
  else return c;
}

int main(void){
  int p[3],j[2],price;
  for(int i=0;i<3;i++){ scanf("%d",&p[i]); }
  for(int i=0;i<2;i++){ scanf("%d",&j[i]); }
  price=least(p[0],p[1],p[2])+less(j[0],j[1])-50;
  printf("%d\n",price);
  return 0;
}



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

import sys
from itertools import combinations

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = MAP()
A = LIST()

ans = 0
for a, b in combinations(A, 2):
    ans += a * b
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007ll;

//from https://drken1215.hatenablog.com/entry/2018/06/08/210000
const int MAX = 2010000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n == k)
    {
        return 1;
    }
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll mpow(ll base, ll num)
{
    if (num == 0)
    {
        return 1;
    }
    ll prev = mpow(base, num / 2);

    if (num % 2 == 0)
    {
        return (prev * prev) % MOD;
    }
    else
    {

        return (((prev * prev) % MOD) * base) % MOD;
    }
}

int main()
{
    COMinit();
    int k;
    cin >> k;
    string s;
    cin >> s;
    int n = s.size();
    ll ans = 0;
    rep(i, n, n + k + 1)
    {
        //cerr << mpow(25, i - n) << endl;

        // ((COM(i, n) * mpow(25, i - n) % MOD) * mpow(26, n + k - i)) % MOD << endl;
        //  cerr << "*" << COM(i - 1, n - 1) << " " << mpow(25, i - n) << " " << mpow(26, n + k - i) << endl;
        ll tmp = (((COM(i - 1, n - 1) * mpow(25, i - n)) % MOD) * mpow(26, n + k - i)) % MOD;
        //cerr << tmp << endl;
        ans += tmp % MOD;
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 52440
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }


 
int main(int argc, char const *argv[]) {
  int n;
  cin >> n;
  int cnt=0;
  rep(i,n){
    int p;
    cin >> p;
    if(i+1!=p) cnt++;
  }

  if(cnt<=2) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a,b,c,cnt[4][101010];
string s[101010];
vector<char>ans;
int main()
{
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
	}
	for(int i=n;i>=1;i--)
	{
		if(s[i]=="AB")
		{
			cnt[1][i]=cnt[1][i+1]+1;
			cnt[2][i]=cnt[2][i+1]+1;
		}
		else if(s[i]=="AC")
		{
			cnt[1][i]=cnt[1][i+1]+1;
			cnt[3][i]=cnt[3][i+1]+1;
		}
		else
		{
			cnt[2][i]=cnt[2][i+1]+1;
			cnt[3][i]=cnt[3][i+1]+1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(s[i]=="AB")
		{
			if(a==0 && b==0)
			{
				cout<<"No"<<endl;
				return 0;
			}
			if((a<b) || (a==b && cnt[1][i]>cnt[2][i]))
			{
				a++;
				b--;
				ans.push_back('A');
			}
			else
			{
				a--;
				b++;
				ans.push_back('B');
			}
		}
		else if(s[i]=="AC")
		{
			if(a==0 && c==0)
			{
				cout<<"No"<<endl;
				return 0;
			}
			if((a<c) || (a==c && cnt[1][i]>cnt[3][i]))
			{
				a++;
				c--;
				ans.push_back('A');
			}
			else
			{
				a--;
				c++;
				ans.push_back('C');
			}
		}
		else
		{
			if(b==0 && c==0)
			{
				cout<<"No"<<endl;
				return 0;
			}
			if((b<c) || (b==c && cnt[2][i]>cnt[3][i]))
			{
				b++;
				c--;
				ans.push_back('B');
			}
			else
			{
				b--;
				c++;
				ans.push_back('C');
			}
		}
	}
	cout<<"Yes"<<endl;
	for(int i=0;i<ans.size();i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 8112
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
typedef pair<int,int> PP;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE cout << -1 << endl;return 0
#define MM <<" "<<
#define Endl endl

const int maxV=314514;
struct edge{int end;int cost;};
typedef pair<int,int> P;
int V,d[maxV];
vector<edge> G[maxV];

void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P>> que;
    for(int i=0;i<maxV;i++){d[i]=INF;}
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v]<p.first)continue;
        for(int i=0;i<G[v].size();i++){
            edge e = G[v][i];
            if(d[e.end]>d[v]+e.cost){
                d[e.end] = d[v]+e.cost;
                que.push(P(d[e.end],e.end));
            }
        }
    }
}


signed main(void){
    int N,M;
    int u[114514],v[114514];
    int S,T;
    
    cin >> N >> M;
    REP(i,M){
        cin >> u[i] >> v[i];
        u[i]--;v[i]--;
    }
    cin >> S >> T;
    S--;T--;
    edge h;
    REP(i,M){
        h.cost=1;
        h.end=v[i]+N;
        G[u[i]].push_back(h);
        h.end=v[i]+2*N;
        G[u[i]+N].push_back(h);
        h.end=v[i];
        G[u[i]+2*N].push_back(h);
    }
    dijkstra(S);
    if(d[T]==INF){
        cout << -1 << endl;
    }else{
        cout << d[T]/3 << endl;
    }
    return 0;
}



Measured memory_bytes: 20992
#include <bits/stdc++.h>
using namespace std;
char a[3010],b[3010];
int long_a,long_b;
int dp[3010][3010];
int times[3010][3010];
int main(){
	scanf("%s",a+1);
	scanf("%s",b+1);
	long_a=strlen(a+1);
	long_b=strlen(b+1);
	for(int i=1;i<=long_a;++i){
		for(int j=1;j<=long_b;++j){
			dp[i][j]=dp[i-1][j];
			times[i][j]=1;
			if(dp[i][j-1]>dp[i][j]){
				dp[i][j]=dp[i][j-1];
				times[i][j]=2;
			}
			if(a[i]==b[j]&&dp[i-1][j-1]+1>dp[i][j]){
				dp[i][j]=dp[i-1][j-1]+1;
				times[i][j]=3;
			}
		}
	}
	string s;
	while(long_a>0 && long_b>0){
		if(times[long_a][long_b]==1)long_a--;
		else if(times[long_a][long_b]==2)long_b--;
		else {
			s+=a[long_a];
			long_a--;
			long_b--;
		}
	}
	for(int i=s.size()-1;i>=0;--i){
		cout<<s[i];
	}
	return 0;
} 

//改编自chenxia25大佬 

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

int main() {
    char chars[5] = "KUPC";
    string line;
    while (cin >> line) {
        int kupc[4] = {};
        for (string::iterator it = line.begin(); it != line.end(); it++) {
            for (int i = 0; i < 4; i++) {
                if (*it == chars[i]) {
                    kupc[i]++;
                    break;
                }
            }
        }
        int min = 1000;
        for (int i = 0; i < 4; i++) {
            if (kupc[i] < min) {
                min = kupc[i];
            } 
        }
        cout << min << endl;
    }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define maxn 120000
using namespace std;
map<int, int> mp;
vector<int> G[maxn];
int f(int u){
	if(mp.count(u)) return mp[u];
	mp[u] = 0;
	for(int v : G[u]) mp[u] = max(mp[u], f(v) + 1);
	return mp[u];
}
int main(){
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	while(M --){
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
	}
	int ans = 0;
	for(int i = 1; i <= N; i += 1) ans = max(ans, f(i));
	cout << ans;
} 

Measured memory_bytes: 14976
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 100000000;
const int MAX_N = 300;
int main() {
	int N, K;
	cin >> N >> K;
	int A[N + 1];
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	N -= K;
	int cnt = 1;
	while (N > 0) {
		N -= (K - 1);
		cnt++;
	}
	cout <<  cnt << endl;
}


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

int main() {

	int N, M;
	
	while(cin >> N >> M, N + M > 0) {
	
		int P[1111];
		vector<int> PP;
		
		for(int i= 0; i < N; i++) {
			cin >> P[i];
		}
		
		P[N++] = 0;
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				PP.push_back(P[i] + P[j]);
			}
		}
		
		sort(PP.begin(), PP.end());
		
		int ans = 0;;
		
		for(int i = 0, m; i < PP.size(); i++) {
			m = M - PP[i];
			if(m < 0) continue;
			int it = *(upper_bound(PP.begin(), PP.end(), m) - 1);
			ans = max(ans, PP[i] + it );
			//cout << PP[i] << " " << it << endl;
		}
		
		cout << ans << endl;
	}

	return 0;

}

Measured memory_bytes: 9188
#include <iostream>
using namespace std;
int main()
{
	string S1, S2, S3;
	string ans="";
	cin >> S1 >> S2 >> S3;
	char H1 = S1.at(0);
	char H2 = S2.at(0);
	char H3 = S3.at(0);


	cout << H1;
	cout << H2;
	cout << H3 << endl;
}

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

int main(){
	int W, a, b, tmp;
	cin >> W >> a >> b;
	if(a>b){
		tmp=a;
		a=b;
		b=tmp;
	}
	
	int ans = b-(a+W);
	if(ans>0)	cout << ans << endl;
	else		cout << 0 << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a[100005],b[100005];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    long long n,h;
    while(cin>>n>>h){
        for(int i=0;i<n;i++){
            cin>>a[i]>>b[i];
        }
        sort(a,a+n,cmp);
        long long maxn=a[0],s=0;
        sort(b,b+n,cmp);
        for(int i=0;i<n;i++){
            if(b[i]>=maxn&&h>=maxn){
                h-=b[i];
                s++;
            }
        }
        if(h>=0){
            s+=h/maxn;
            if(h%maxn!=0) s++;
        }

        cout<<s<<endl;
    }
    return 0;
}


Measured memory_bytes: 1792
#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 ll long long
#define lll __int128
#define ull unsigned long long
#define fi first
#define se second
#define db double
#define ld long double
#define lld __float128

/// order_of_key, find_by_order

template<class T, class COMP>
using custom_set = tree<T, null_type, COMP, rb_tree_tag, tree_order_statistics_node_update>;

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

template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::steady_clock::now().time_since_epoch().count());

bool comp(pair<ll, ll> a, pair<ll, ll> b)
{
    if(a.fi * (b.se+1ll) > b.fi * (a.se+1ll))
        return 1;
    return 0;
}

ll dp[200005][35];

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

    ll n, T; cin >> n >> T; T;
    pair<ll, ll> dat[n];
    for(int i = 0; i < n; i++)
    {
        cin >> dat[i].fi >> dat[i].se;
    }
    vector<pair<ll, ll> > vc;
    vector<ll> v;
    for(int i = 0; i < n; i++)
    {
        if(dat[i].fi)
        {
            vc.push_back(dat[i]);
        }
        else
        {
            v.push_back(dat[i].se);
        }
    }
    for(int i = 0; i <= vc.size(); i++)
    {
        for(int j = 0; j < 35; j++)
        {
            dp[i][j] =T+1;
        }
    }
    sort(vc.begin(), vc.end(), comp);
    sort(v.begin(), v.end());
    dp[0][0] = 0;
    for(int i = 0; i < vc.size(); i++)
    {
        for(int j = 0; j < 35; j++)
        {
            if(dp[i][j] > T)
                continue;
            if(j < 34)
            {
                ll mt = dp[i][j] + vc[i].fi * (dp[i][j]+1) + vc[i].se + 1;
                dp[i+1][j+1] = min(dp[i+1][j+1], mt);
            }
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        }
    }
    ll ans = 0;
    for(int j = 0; j < 35; j++)
    {
        if(dp[vc.size()][j] > T)
            continue;
        ll sm = T-dp[vc.size()][j], res = j;
        for(int i = 0; i < v.size(); i++)
        {
            if(v[i]+1 > sm)
                break;
            res++;
            sm -= v[i]+1;
        }
        ans = max(ans, res);
    }
    cout << ans << '\n';
}






































/// shche ne vmerla Ykraina


Measured memory_bytes: 61292
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main(){
    string s;
    cin >>s;
    int n = s.size();

    vector<bool> t(n+1);
    rep(i,n) t[i+1] = (s[i]=='1');
    t[0] = true;

    bool ok = !t[n] & t[1] & t[n-1];
    for(int i=1; i<n; ++i) ok &= (t[i]==t[n-i]);
    if(!ok){
        cout << -1 << "\n";
        return 0;
    }

    int par = n;
    for(int i=n-1; i>0; --i){
        cout << par << " " << i << "\n";
        if(i<n-1 && t[i]) par = i;
    }
    return 0;
}


Measured memory_bytes: 1664