akhauriyash/Code-Regression huggingface dataset:
/*  -*- coding: utf-8 -*-
 *
 * 1595.cc: Traffic Tree
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

typedef vector<int> vi;
typedef queue<int> qi;

/* global variables */

vi nbrs[MAX_N];
int ps[MAX_N], cns[MAX_N];
int ts0[MAX_N], ts1[MAX_N], rs0[MAX_N], rs1[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    nbrs[u].push_back(v);
    nbrs[v].push_back(u);
  }

  ps[0] = -1;
  qi q;
  q.push(0);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    //printf("%d: ps=%d\n", u, ps[u]);
    int &up = ps[u];
    vi &nbru = nbrs[u];
    for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &v = *vit;
      if (v != up) {
	cns[u]++;
	ps[v] = u;
	q.push(v);
      }
    }
  }

  for (int u = 0; u < n; u++)
    if (cns[u] == 0) q.push(u);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    int &up = ps[u], ut0 = ts0[u] + 1;

    if (up >= 0) {
      if (ts0[up] < ut0)
	ts1[up] = ts0[up], ts0[up] = ut0;
      else if (ts1[up] < ut0)
	ts1[up] = ut0;
      if (--cns[up] == 0) q.push(up);
    }
  }
  //for (int i = 0; i < n; i++) printf("%d: %d,%d\n", i, ts0[i], ts1[i]);

  q.push(0);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    int &up = ps[u];

    rs0[u] = ts0[u], rs1[u] = ts1[u];
    if (up >= 0) {
      int pr = ((rs0[up] == ts0[u] + 1) ? rs1[up] : rs0[up]) + 1;
      if (rs0[u] < pr)
	rs1[u] = rs0[u], rs0[u] = pr;
      else if (rs1[u] < pr)
	rs1[u] = pr;
    }

    vi &nbru = nbrs[u];
    for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &v = *vit;
      if (v != up) q.push(v);
    }
  }

  int sum = (n - 1) * 2;
  for (int i = 0; i < n; i++) printf("%d\n", sum - rs0[i]);
  return 0;
}



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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

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

    int N,M,Q;
    cin >> N >> M >> Q;
    VI L(M),R(M);
    VVI sum(N+1,VI(N+1.0));
    for (int i = 0; i < M; i++) {
        cin >> L[i] >> R[i];
        sum[L[i]][R[i]]++;
    }

    // 累積和のテーブル作成
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            sum[i][j] += sum[i-1][j];
            sum[i][j] += sum[i][j-1];
            sum[i][j] -= sum[i-1][j-1];
        }
    }

    VI p(Q),q(Q);
    for (int i = 0; i < Q; i++) {
        cin >> p[i] >> q[i];
    }

    for (int i = 0; i < Q; i++) {
        int ans;
        int l = p[i],r = q[i];
        ans = sum[r][r] - sum[l-1][r] - sum[r][l-1] + sum[l-1][l-1];
        cout << ans << endl;
    }
    return 0;
}


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


int main() {
    int n;
    scanf("%d", &n);
    double ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += 1.0 * i / 2.0 * floor(1.0 * n / i) * floor(1.0 * n / i + 1);
    }
    printf("%.0f\n", ans);
    return 0;
}


Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s,t; cin>>s>>t;
    int n=s.length(),m=t.length();
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0 or j==0) {dp[i][j]=0; continue;}
            if(s[i-1]==t[j-1])
            {
             dp[i][j]=dp[i-1][j-1]+1;   
            }
            else{
              dp[i][j]=max(dp[i][j-1],dp[i-1][j]);  
            }
            
        }
    }
    string ans="";
    int i=n,j=m;
    while(i>=1 and j>=1)
    {
            if(s[i-1]==t[j-1])
            {
                ans+=s[i-1]; i--;j--;
            }
            else if(dp[i-1][j]>dp[i][j-1]) 
            {
                i--;
            }
            else j--;
    }
    //cout<<ans<<" "<<dp[n][m];
    reverse(ans.begin(),ans.end());
    cout<<ans;
}

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

int main()
{
   string str;
   long long int a;
   
   cin>> str;
   
   for (int i = 0; i < str.size(); ++i)
   {
       a = a + str[i]-'0';
   }
    
    if(a%9==0)
    cout<<"Yes";
    else
    cout<<"No";
    
    return 0;
}

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

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;


int main(){
  ll n, m;
  cin >> n >> m;
  vector<pair<ll,ll>> v;
  rep(i, n){
    ll a, b;
    cin >> a >> b;
    v.push_back(make_pair(a, b));
    // cin >> v.first >> v.second;
  }
  sort(v.begin(), v.end());
  ll ans = 0;
  int count = 0;
  for(auto a: v){
    // cout << a.first << endl;
    if(count < m){
      ans += min(m-count, a.second) * a.first;
      count += a.second;
    }
    // if(a.first)
  }
  cout << ans << endl;
  return 0;

}



Measured memory_bytes: 2420
<?php
fscanf(STDIN, "%s", $S);
$arrS = str_split($S);
$cntS = count($arrS);
$cntL[0] = 0;
$cntR[$cntS] = 0;
for ($i = 0; $i < $cntS; $i++) {
    //echo $i . PHP_EOL;
    if ($arrS[$i] === "<") {
       // echo "inc";
        $cntL[$i+1] = $cntL[$i] + 1;
    } else {
        //echo "reset";
        $cntL[$i+1] = 0;
    }
    if ($arrS[$cntS-$i-1] == ">") {
        $cntR[$cntS-$i-1] = $cntR[$cntS-$i] + 1;
    } else {
        $cntR[$cntS-$i-1] = 0;
    }
}
$ans = 0;
for ($i = 0; $i < $cntS + 1; $i++) {
    $ans += max($cntR[$i], $cntL[$i]);
}
echo $ans;


Measured memory_bytes: 72176
h, w, k = map(int, input().split())

ans = [0] + [1] + [0] * w
n_ans = [a for a in ans]
fact = [1, 2, 3, 5, 8, 13, 21]
mod = 10 ** 9 + 7

for _ in range(h):
    for i in range(1, w + 1):
        # connect i-1 i
        tmp = fact[max(i - 3, 0)] * fact[max(w - i - 1, 0)]
        # print("i-1 i", tmp)
        n_ans[i] = (ans[i - 1] * tmp) % mod

        # no connect
        tmp = fact[max(i - 2, 0)] * fact[max(w - i - 1, 0)]
        # print("non", tmp)
        n_ans[i] = (n_ans[i] + ans[i] * tmp) % mod

        # connect i i+1
        tmp = fact[max(i - 2, 0)] * fact[max(w - i - 2, 0)]
        # print("i i+1", tmp)
        n_ans[i] = (n_ans[i] + ans[i + 1] * tmp) % mod

        # print(n_ans, ans)
    ans = [a for a in n_ans]
    # print(ans)


print(ans[k])

Measured memory_bytes: 3064
h,w = map(int, input().split())

a = [list(input()) for i in range(h)]
a = [x for x in a if "#" in x]

aT = list(zip(*a))
aT = [x for x in aT if "#" in x]

a = list(zip(*aT))

for i in a:
    print("".join(i))

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

#define int long long

using namespace std;

signed main(void){
    int N;
    cin >> N;
    int ans = 0;
  	set<int> s;
    for(int n = 0; n <= 1048576; n++){
        int nn = n;
        int b = 0;
        while(nn > 0){
            b *= 10;
        	if(nn % 4 != 0) b += 1 + 2 * (nn % 4);
            nn /= 4;
        }
        if(b > N) continue;
      	if(s.find(b) != s.end()) continue;
      	s.insert(b);
        vector<bool> f(10, false);
        while(b > 0){
            f[b % 10] = true;
            b /= 10;
        }
        if(!f[0] && f[3] && f[5] && f[7]){
          ans++;
          //cout << b << endl;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9472
/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
*/
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    int n,i,j,k,x,y,ans,temp,curr,m;
    ll a,b,c;
    cin >> a >> b >> c;
    ll chaeng = 0;
    ll sum = b + c;
    ll need = a / sum;
    chaeng += need*b;
    ll sisa = a % sum;
    chaeng += min(b, sisa);
    cout << chaeng << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <numeric>

#define rep(i,n) for(int i = 0;i < (n);i++)
#define repp(i,j, n) for(int i = (j);i < (n);i++)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define INF 1e9

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpi;
typedef vector<pair<ll, ll> > vpl;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, T;
  cin >> N >> T;
  vl t(N);
  rep(i, N) cin >> t[i];
  ll sum = N*T;
  rep(i, N-1){
    sum -= max(T-(t[i+1]-t[i]), (ll)0);
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std ; 
#define int long long int 
#define mod 1000000007
int dp[1010][1010] ; 
int mat[1010][1010] ; 



void fn(int r, int c)
{

	dp[1][1]=1 ; 
	for(int k=2; k<=c; k++)
	{
		if(mat[1][k]==9)
		{
			break ; 
		}
		dp[1][k]=1; 
	}

	for(int k=2; k<=r; k++)
	{
		if(mat[k][1]==9)
		{
			break ; 
		}
		dp[k][1]=1; 
	}


	for(int i=2; i<=r; i++)
	{
		for(int j=2; j<=c; j++)
		{
			if(mat[i][j]==9)
			{
				dp[i][j]=0 ; 
			}
			else
			{
				dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod ; 
			}			

		}
	}

	// for(int i=1; i<=r; i++)
	// {
	// 	for(int j=1; j<=c; j++)
	// 	{
	// 		cout<<dp[i][j]<<" "; 	

	// 	}
	// 	cout<<endl ; 
	// }



	cout<<dp[r][c]; 
}

int32_t main()
{
	int r, c;
	cin>>r>>c; 
	memset(dp,0,sizeof(dp)) ; 

	for(int i=1 ; i<=r; i++)
	{
		for(int j=1 ; j<=c; j++)
		{
			char ch ; 
			cin>>ch ; 
			if(ch=='.')
			{
				mat[i][j]=0 ; 
			}
			else
				mat[i][j]=9 ; 
		}
	} 
	// for(int i=1 ; i<=r; i++)
	// {
	// 	for(int j=1 ; j<=c; j++)
	// 	{
	// 		cout<<mat[i][]
	// 	}
	// } 

	fn(r, c);  

}

Measured memory_bytes: 16128
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define inf 9223372036854775807
#define mini 9223372036854775807
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
pair<ll,ll>s4[4]={{-1,0},{1,0},{0,-1},{0,1}};
pair<ll,ll>s8[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,1},{1,0},{1,-1}};
ll power(ll a,ll b)
{
	if(b==0)
		return 1;
	ll c=power(a,b/2);
	if(b%2==0)
		return ((c%mod)*(c%mod))%mod;
	else
		return ((((c%mod)*(c%mod))%mod)*a)%mod;
}
int main()
{
	boost
	ll n;
	cin>>n;
	double d[n];
	for(ll i=0; i<n; i++)
		cin>>d[i];
	double ans=0;
	for(ll i=0; i<n; i++)
		ans=ans+(1/d[i]);
	ans=1/ans;
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
n,q= map(int,input().split())
s = input()
l = [list(map(int,input().split())) for i in range(q)]
sa = [0]*n
for i in range(0,len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        sa[i+1] = sa[i] + 1
    else:
        sa[i+1] = sa[i]

""" A C D D D A C A C """
"""0 1 1 1 1 1 2 2 3  """
for si, syu in l:
    print(sa[syu-1] - sa[si-1])


Measured memory_bytes: 68984
n, m = map(int, input().split())

ac = 0
wa = 0
res1 = [0]*n
res2 = [0]*n
for i in range(m):
  p, s = list(map(str, input().split()))
  if s == 'AC' and res1[int(p)-1] == 0:
    ac += 1
    res1[int(p)-1] = 1
    wa += res2[int(p)-1]
  elif s == 'WA' and res1[int(p)-1] == 0:
    res2[int(p)-1] += 1
print(ac, wa)

Measured memory_bytes: 4724
/*************************************************************************
  >         File: D.cc
  >       Author: Yuan Lei
  >         Mail: yuanlei@indeed.com
  > Created Time: Sat Apr  8 21:20:34 2017
*************************************************************************/
#include <vector>
#include <cstdio>
#include <bitset>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <cstring>
#include <cassert>
#include <numeric>
#include <set>
#include <map>
#include <deque>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>
constexpr int MO = 1e9 + 7;
constexpr int N = 2e5;

int a[N], b[N];

void Add(int &x, int y) {
  x += y;
  if (x >= MO) x -= MO;
}

int get(int n) {
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    Add(ans, 1LL * i * (n - i) % MO * b[i] % MO);
  }
  return ans;
}

int main() {
  std::ios::sync_with_stdio(0);
  int cnt[2];
  for (int i = 0; i < 2; ++i) {
    std::cin >> cnt[i];
  }
  int ans = 1;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < cnt[i]; ++j) {
      std::cin >> a[j];
    }
    for (int j = 1; j < cnt[i]; ++j) {
      b[j] = a[j] - a[j - 1];
    }
    ans = 1LL * ans * get(cnt[i]) % MO;
  }
  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 1024
// AOJ 1348: Space Golf
// 2017.12.31 bal4u@uu

#include <stdio.h>
#include <math.h>


#define N 100
#define EPS 1e-7
#define PI4 0.78539816339744830961566084581988  // = PI/4
#define INF 1e20

int p[12], h[12];
 
double calcH(double m, double a)
{
	return m*m*sin(2*a);
}
 
double calcV(double x, int n, int b, double a)
{
	int i, j;
	double l, m, r, s, t, y;

	l = 0; r = INF;
	i = N; while (i--) {
		m = (l+r)/2;
		if (calcH(m, a) > x) r = m; else l = m;
	}

	s = 0;
	for (i = 0; i < b; i++, s += x) for (j = 0; j < n; j++) {
		if (s <= p[j] && p[j] <= s+x) {
			t = (p[j] - s)/(l*cos(a));
			y = (l*sin(a) - t/2) * t;
			if (h[j] > y+EPS) return INF;
		}
	}
	return l;  
}
 
double calc(double x, int n, int b)
{
	int i;
	double l, m, r, t, ans;

	l = PI4, r = 2*l, ans = INF;
	i = N; while (i--) {
		m = (l+r)/2;
		if ((t = calcV(x, n, b, m)) < INF) r = m; else l = m;
		if (t != INF) ans = t;
	}
	return ans;
}
 
int main()
{
	int d, n, b, i;
	double ans, t;

	scanf("%d%d%d", &d, &n, &b);
	for (i = 0; i < n; i++) scanf("%d%d", p+i, h+i);

	ans = INF;
	i = 0; while (i++ <= b) {
		t = calc((double)d/i, n, i);
		if (t < ans) ans = t;
	}
	printf("%.5lf\n", ans);
	return 0;
}

Measured memory_bytes: 2116
/*
 * main.cpp
 *
 *  Created on: 2020/04/07
 *      Author: SkAaO
 */

#include <iostream>
#include <string>

using namespace std;

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

	/*
	char swap;
	int length = (int)S.size();
	for(int i = 0; i < length; i++){
		for(int j = i + 1; j < length; j++){
			if(S.at(i) > S.at(j)){
				swap = S.at(i);
				S.at(i) = S.at(j);
				S.at(j) = swap;
			}
		}
	}

	char min = 0;
	char pre, cre;
	for(int i = 1; i < length; i++){
		pre = S.at(i-1);
		cre = S.at(i);
		char dist = cre - pre;
		if(dist >= 2){
			min = pre + 1;
			cout << min << endl;
			break;
		}else{
			if(i == length - 1){
				cout << "None" << endl;
				break;
			}
			continue;
		}
	}
	*/

	bool exist[26] = {false};
	int length = (int)S.size();
	for(int i = 0; i < length; i++){
		exist[(S.at(i) - 'a')] = true;
	}
	for(int i = 0; i < 26; i++){
		if(exist[i] == false){
			char word = i + 'a';
			printf("%c", word);
			break;
		}else{
			if(i == 25){
				cout << "None" << endl;
				break;
			}
			continue;
		}
	}

	return 0;
}




Measured memory_bytes: 512
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

//     int root(int x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

int main(void) {
    string S;
    set<char> T1;
    multiset<char> T2;
    cin >> S;
    for (int i=0;i<S.size();i++) {
        T1.insert(S[i]);
        T2.insert(S[i]);
    }
    if (T1.size() != 2) {
        cout << "No" << endl;
        return 0;
    } else {
        for (auto itr : T2) {
            if (T2.count(itr) != 2) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String ans="No";
		for(int i=1;i<=9;i++){
			for(int k=1;k<=9;k++){
				if(i*k==N){
				ans="Yes";
				}
			}
		}
		System.out.println(ans);
    }
}

Measured memory_bytes: 22996
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>

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

using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    int ans;
    ans = min(n*a, b);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define tcase int _; cin >> _; while(_--)
const int MAX = 1e6;

int n;
string v[MAX];
int ans[4];

void solve() {
	memset(ans, 0, sizeof ans);
	cin >> n;
	for(int i=0; i<n; i++) cin >> v[i];
	for(int i=0; i<n; i++) {
		if(v[i][0] == 'A') ans[0]++;
		else if(v[i][0] == 'W') ans[1]++;
		else if(v[i][0] == 'T') ans[2]++;
		else ans[3]++;
	}
	cout << "AC x " << ans[0] << "\n";
	cout << "WA x " << ans[1] << "\n";
	cout << "TLE x " << ans[2] << "\n";
	cout << "RE x " << ans[3] << "\n";
}

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

 	solve();

  	return 0;
}



Measured memory_bytes: 34804
n = int(input())
dp = [float('inf')]*(n+1)
dp[0] = 0
cost = [int(input()) for _ in range(n-1)]
for i in range(1,n):
    for j in range(i):
        if dp[i-j]+cost[i-1] < dp[j]: dp[j] = dp[i-j]+cost[i-1]# = min(dp[j],dp[i-j]+cost[i-1])
        if dp[j]+cost[i-1] < dp[i-j]: dp[i-j] = dp[j]+cost[i-1]# = min(dp[i-j],dp[j]+cost[i-1])
    #print(dp)
print(dp[n//2])

Measured memory_bytes: 8152
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n,k = map(int,input().split())
    eprint('math.log(n,k) ', end=':\n')
    eprint(math.log(n,k))
    d = math.ceil(math.log(n,k))
    print(1 if d ==0 else d)

if __name__ == '__main__':
    main()

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

#define ll long long
#define ld long double
#define inf 100000000000000000
#define rep(i,a) for(ll i=0; i<a; ++i)
#define pb push_back

ld x1;
ld Y1;
ld x2, y2, x3, y3;
ld a,b,c,s,delta,r;
ld acc=0.000000001;

ld dist(ld xx1, ld yY1, ld xx2, ld yy2) {
  return sqrt((xx1-xx2)*(xx1-xx2) + (yY1-yy2)*(yY1-yy2));
}

ld getAns(ld a, ld r) {
  ld beg=0, end=r;
  while(end-beg>acc) {
    ld mid = (beg+end)/2;
  //  cout<<fixed<<setprecision(11)<<beg<<" "<<end<<" "<<mid<<" "<<end-beg<<" "<<acc<<endl;
    ld l = a*(1-mid/r);
    if (abs(l-2*mid)<acc) {
      return mid;
    }
    if (l>2*mid) {
      beg = mid;
    } else {
      end = mid;
    }
  }
  return beg;
}

int main() {
  ios::sync_with_stdio(false);
  cin>>x1>>Y1>>x2>>y2>>x3>>y3;
  a = dist(x1,Y1,x2,y2);
  b = dist(x2,y2,x3,y3);
  c = dist(x1,Y1,x3,y3);

  s = (a+b+c)/2;
  delta = sqrt(s*(s-a)*(s-b)*(s-c));
  r = delta/s;

  ld ans1 = getAns(a,r);
  ld ans2 = getAns(b,r);
  ld ans3 = getAns(c,r);
  //cout<<fixed<<setprecision(15)<<ans1<<" "<<ans2<<" "<<ans3<<endl;
  cout<<fixed<<setprecision(15)<<max(ans1,max(ans2,ans3))<<endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
	ll N,K;
	cin >> N >> K;
	if(N > K)
	N = N%K;
	if(N == 0 )
	{
		cout << 0 << endl;
		return 0;
	}
	else if(N>K-N)
	cout << K-N <<endl;
	else cout << N << endl;
	
}

Measured memory_bytes: 256
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

const int MX = 1 << 18, md = 1000000007;

unordered_map<int, int> here[18];
bool old[18];

int a[MX];

int main() {
	int h = 18;
	ignore = scanf("%d", &h);
	
	int n = 1 << (h - 1);
	for (int i = 0; i < n; i++) ignore = scanf("%d", a + i);
//	srand(42);
//	iota(a, a + n, 1);
//	random_shuffle(a, a + n);
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int u = n + i, p = 1, d = 0; u != 1; d++, u /= 2) {
			p = p * 1LL * u % md;
			
			if (u % 2 == 0) {
				if (old[d]) {
					here[d].clear();
					old[d] = false;
				}
				
				for (int v = n + a[i] - 1, q = p; v != 1; v /= 2) {
					q = q * 1LL * v % md;
					
					int& val = here[d][v];
					val += q;
					if (val >= md) val -= md;
				}
			}
			else {
				old[d] = true;
				
				for (int v = n + a[i] - 1, q = p; v != 1; v /= 2) {
					q = q * 1LL * v % md;
					
					auto it = here[d].find(v ^ 1);
					if (it != here[d].end()) {
						int there = it->second;
						ans += q * 1LL * there % md * (v / 2) % md * (u / 2) % md;
						if (ans >= md) ans -= md;
					}
				}
			}
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}


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

int N, x, p;
int sum = 0; 
int MIN = 100000000;
int X[110];

int main(){
  cin >> N;
  for(int i = 0; i < N; i++) cin >> X[i]; 

  for(p = 1; p <= 100; p++){
    sum = 0;  //リセット
    for(int i = 0; i < N; i++) sum += (X[i]-p)*(X[i]-p);
    MIN = min(MIN, sum);
  }
  
  cout << MIN << endl;    
  return 0;
}


    

Measured memory_bytes: 256
MOD = 10**9+7           # 問題に合わせて適宜書き換え
list_size = 10**5+100    # 問題に合わせて適宜書き換え

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

def comb(n,r):
    if n < r:
        return 0
    if n == 0 or r == 0 or n == r:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD

N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
ans = 0
for i in range(N):
    ans -= (A[i]*comb(N-i-1,K-1))
    ans %= MOD
for j in range(N):
    ans += (A[-1-j]*comb(N-j-1,K-1))
    ans %= MOD
print(ans)

Measured memory_bytes: 22612
date = list(map(str,input().split()))
Num = 0
Size = 0
for tag in sorted(set(date), key=date.index):
    if date.count(tag) > Num:
        Num = date.count(tag)
        Ooi = tag
    if len(tag) > Size:
        Size = len(tag)
        Msiz = tag
print(Ooi,Msiz)
    

Measured memory_bytes: 7392
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 2048
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
typedef long double ld;
const double PI = acos(-1.0);
#define dbg(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;


typedef vector<ll> vcL;
typedef vector<vcL> vvL;
const ll mod = 1e9 + 7;
ll X[maxn], Y[maxn];
//ll dp[maxn][maxn];
ll n, m;


void solve()
{
    vvL dp( n+1, vcL( m+1, 1 ) );
   // vector<vector<ll> > dp(n+1, vector<ll> (m+1, 1));
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            if(X[i] == Y[j]) dp[i][j] += dp[i - 1][j - 1];
            dp[i][j] = (dp[i][j] + 10 * mod) % mod;

        }
    }
    cout << dp[n][m]<< "\n";
}


int main()
{
    FASTIO
    /*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
//*/
    cin >> n >> m;
    for(ll i = 1; i <= n; i++) cin >> X[i];

    for(ll i = 1; i <= m; i++) cin >> Y[i];
    //memset(dp, 0, sizeof dp);
   // dp[0][0] = 1;
    solve();
    //double end_time = clock();
    //prllf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

    return 0;
}


Measured memory_bytes: 31616
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
const int mod = 1e9 + 7;
const int INF = 1e9;
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    int a[n];

    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int ans = 1;
    for(int i = 1; i < n; i++){
        bool can = true;
        for(int j = 0; j < i; j++){
            if(a[i] < a[j]){
                can = false;
            }
        }
        if(can) ans++;
    }
    cout << ans;
}


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

long long a[100005],sum1[100005],sum2[100005],ans;
int n,k;

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
		sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];
		if(a[i]>=0)
		sum1[i]=sum1[i-1]+a[i];
		else sum2[i]=sum2[i-1]+a[i];
	}
	ans=sum1[n];
	long long ma=(1e15);
	for(int i=1;i<=n-k+1;++i)
	{
		ma=min(sum1[i+k-1]-sum1[i-1],ma);
		ma=min(sum2[i-1]-sum2[i+k-1],ma);
	}
	printf("%lld",ans-ma);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll          long long
#define pb          push_back
#define eb 			emplace_back
#define mp 			make_pair
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define all(a)      (a).begin(),(a).end()
#define fi          first
#define si          second
#define sz(x)       (ll)x.size()
#define endl        '\n'
#define checkbit(n, b) ((n >> b) & 1)
#define mod        1000000007
#define inf        1000000000000000000
#define puts(n)		cout<<n;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define setbits(x) __builtin_popcount(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,x;
	cin>>x>>n;
	map<ll,bool>  m;
	for(ll i=0;i<n;i++){
		ll p;
		cin>>p;
		m[p]=true;
	}
	ll ans,diff=0,val=x;
	while(true){
		if(m[val]){
			val--;
			continue;
		}
		diff=x-val;
		ans=val;
		break;
	}
	val=x;
	while(true){
		if(m[val]){
			val++;
			continue;
		}
		if(abs(x-val) <diff){
			ans=val;
		}
		break;
	}
	cout<<ans;
	
	
	
	return 0;
}

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

int main(int argc,char ** argv){
  int a,b,c;
  cin>>a>>b>>c;
  int a2,b2,c2;
  if(a==b && b==c){
    if(a==1){
      cout<<"0"<<endl;
      return 0;
    }
    cout<<"-1"<<endl;
    return 0;
  }
  int i=0;
  int flag=true;
  while(1){
    if((a%2) || (b%2) || (c%2)){
      break;
    }
    a2=(b+c)/2;
    b2=(a+c)/2;
    c2=(a+b)/2;
    a=a2;
    b=b2;
    c=c2;
    i++;
  }
  cout<<i<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String []args){
		//????????£?????????????????????
		Scanner sc = new Scanner(System.in);

		//??°?????????
		while(true){
			//??°???a?????????
			int a = sc.nextInt();
			//op?????????
			String op = sc.next();
			//??°???b?????????
			int b = sc.nextInt();
			//???????????? ???
			if(op.equals("+")){
				System.out.println(a + b);
			//???????????? ???
			}else if(op.equals("-")){
				System.out.println(a - b);
			//???????????? ???
			}else if(op.equals("*")){
				System.out.println(a * b);
			//???????????? ???
			}else if(op.equals("/")){
				System.out.println(a / b);
			//? ??????
			}else if(op.equals("?")){
				break;
			}
		}
	}
}

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

using namespace std;

typedef long long ll;
typedef pair< ll, ll > pll;
typedef pair< int, int > pii;

const double pi = 3.14159265358979323846;

// #define fio() cin.tie(0); ios::sync_with_stdio(false);
// template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
// template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define TG0 get< 0 >
#define TG1 get< 1 >
#define TG2 get< 2 >
#define F first
#define S second
#define VL vector< ll >

// to_string(123)
// atoi("123"); atoi(s.c_str());
// "abc".size()
// s.find('+') == string::npos
// 1e18

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

  ll A, B;
  cin >> A >> B;

  for (ll i = 1; i <= 10000; i++) {
    double d8 = floor(i * 0.08);
    double d10 = floor(i * 0.1);
    if (d8 == A && d10 == B) {
      cout << i << endl;
      return 0;
    }
  }

  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)
pairs = []
m.times do |i|
  pairs << gets.split.map(&:to_i)
end

hash = {}

pairs.each do |pair|
  a = pair[0]
  b = pair[1]
  if hash[a].nil?
    hash[a] = []
    hash[a] << b
  else
    hash[a] << b
  end
  if hash[b].nil?
    hash[b] = []
    hash[b] << a
  else
    hash[b] << a
  end
end

#p hash

temp_start_index = 0
count = 0

for i in 1..n do
  if hash[i].nil?
    next
  end

  hash[i].each do |j|
    if (j >= temp_start_index) && (i > j)
      #p [i, j]
      count += 1
      temp_start_index = i
      break
    else
    end
  end

end

puts count

Measured memory_bytes: 18556
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};


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

    ld a;
    ld b;
    ld ans= 0;

    cin >> a >> b;
    ans = a*b;
    cout << ll(ans)<<endl;
    return 0;
}

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

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

    ll N;
    cin >> N;
    for(int n=1; n<=3500; n++){
        for(int w=1; w<=3500; w++){
            if(N*w+N*n - 4*n*w == 0) continue;
            if(-N*n*w % (N*w+N*n - 4*n*w) == 0 && -N*n*w / (N*w+N*n - 4*n*w) > 0){
                ll h = -N*n*w / (N*w+N*n - 4*n*w);
                printf("%lld %d %d\n", h, n, w);
                return 0;
            }

        }
    }
    
    return 0;
}


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

using namespace std;

int main()
{
  int n; cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; ++i) cin >> v[i];

  map<int, int> odd, even;
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0) even[v[i]]++;
    else odd[v[i]]++;
  }

  // <頻度, 値>
  vector<pair<int, int>> oddf, evenf;
  for (auto vv : odd) {
    oddf.push_back(make_pair(vv.second, vv.first));
  }
  sort(oddf.begin(), oddf.end(), greater<pair<int, int>>());

  for (auto vv : even) {
    evenf.push_back(make_pair(vv.second, vv.first));
  }
  sort(evenf.begin(), evenf.end(), greater<pair<int, int>>());

  if (oddf[0].second == evenf[0].second) {
    cout << n - max(oddf[0].first + evenf[1].first,
                    oddf[1].first + evenf[0].first) << endl;
  } else {
    cout << n - oddf[0].first - evenf[0].first << endl;
  }
}

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

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

    int N, M;
    cin >> N >> M;
    map<int, int> ma;
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        ma[a]++;
        ma[b]++;
    }

    for (auto m : ma) {
        if (m.second % 2 != 0) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 1; i < (int)(n); i++)

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

  int64_t power = 1;

  rep(i, n + 1){
    power = (i * power) % 1000000007;
  }
  
  cout << power << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;


int main()
{
	int a;
	cin >> a;
	string b;
	cin >> b;
	for(int i=0; i<min(a, (int)b.length()); i++)
	{
		cout << b[i];
	}
	if(a<b.length())
	{
		cout << "...";
	}
}



Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int count = 0;
        for(int i = a; i <= b; i++) {
            if((c % i) == 0) {
                count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 26196
#include<stdio.h>

int main(void)
{
	int n, i, temp;
	
	scanf("%d",&n);
	temp = 100000;
	
	for(i=0;i<n;i++)
	{
		temp = temp + (temp * 0.05);
		if(temp%1000!=0)
			temp = (temp/1000 +1)*1000;
	}
	printf("%d\n",temp);
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (ll i = 0; i < (n); i++)
typedef pair<ll,ll> P;

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

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

  deque<ll> list;
  ll top; cin >> top;
  list.push_back(top);

  rep(i,n-1){
    ll x;
    cin >> x;
    auto it = lower_bound(list.begin(), list.end(),x);
    ll d = distance(list.begin(), it);
    if(d==0){
      list.push_front(x);
    }else{
      list[d-1] = x;
    }

    // sort(list.begin(), list.end(), less<ll>());
  }
  cout << list.size() << endl;

  return 0;
} 


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int main() {
  int N, A, B; std::cin >> N >> A >> B;
  fin(std::min(B, N*A));
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define SORT(x) (sort(x.begin(),x.end()))
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main() {
    int N,K,ans=0,h[100007],mi=MOD;cin >> N >>K;
    rep(i,N){
        cin >> h[i];
    }
    sort(h,h+N);
    rep(i,N-K+1){
        if(mi>h[i+K-1]-h[i]){
            mi=h[i+K-1]-h[i];
        }
    }
    cout << mi << endl;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    map<int, int> val;
    int maxValue = 0;
    for(int i = n-1; i >= 0; i--){
        chmax(maxValue, a[i]);
        val[maxValue-a[i]]++;
    }
    int ans = 0, fine = 0;
    for(auto p : val){
        if(p.first > fine){
            ans = p.second;
            fine = p.first;
        }
    }
    cout << ans << endl;
	return 0;
}

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

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


Measured memory_bytes: 256
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::Integer;
#[allow(unused_imports)]
use proconio::derive_readable;
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp;

#[fastout]
fn main() {
  input! {
    n: usize,
    a: [i64; n],
  }
  use std::collections::BTreeMap;
  let mut sum = BTreeMap::new();
  let mut ans = 0i64;
  for (i, &x) in a.iter().enumerate() {
    let diff = i as i64 - x;
    ans += sum.get(&diff).unwrap_or(&0);
    *sum.entry(x + i as i64).or_insert(0) += 1;
  }

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


Measured memory_bytes: 11644
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<double,int,double> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf=sizeof(Def)==sizeof(long long)?2e18:1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	string s;
	cin>>s;
	sort(all(s));
	bool h=true;
	rep(i,s.size()-1)if(s[i]==s[i+1])h=false;
	if(h)cout<<"yes"<<endl;
	else cout<<"no"<<endl;
}











Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<bitset>
#include<set>
#define N (100010)
#define P ()
#define M ()
#define inf (0x7f7f7f7f)
#define rg register int
#define Label puts("NAIVE")
#define spa print(' ')
#define ent print('\n')
#define rand() (((rand())<<(15))^(rand()))
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
typedef long double ld;
typedef long long LL;
typedef unsigned long long ull;
using namespace std;
namespace fastIO1{
	inline char read(){
		static const int IN_LEN=1000000;
		static char buf[IN_LEN],*s,*t;
		return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
	}
	template<class T>
	inline void read(T &x){
		static bool iosig;
		static char c;
		for(iosig=false,c=read();!isdigit(c);c=read()){
			if(c=='-')iosig=true;
			if(c==-1)return;
		}
		for(x=0;isdigit(c);c=read())x=((x+(x<<2))<<1)+(c^'0');
		if(iosig)x=-x;
	}
	inline char readc(char &c){
		for(c=read();!isalpha(c)&&!isdigit(c);c=read())
		if(c==-1)return 0;
	}
	const int OUT_LEN = 10000000;
	char obuf[OUT_LEN],*ooh=obuf;
	inline void print(char c) {
		if(ooh==obuf+OUT_LEN)fwrite(obuf,1,OUT_LEN,stdout),ooh=obuf;
		*ooh++=c;
	}
	template<class T>
	inline void print(T x){
		static int buf[30],cnt;
		if(x==0)print('0');
		else{
			if(x<0)print('-'),x=-x;
			for(cnt=0;x;x/=10)buf[++cnt]=x%10+48;
			while(cnt)print((char)buf[cnt--]);
		}
	}
	inline void flush(){fwrite(obuf,1,ooh-obuf,stdout);}
}
namespace fastIO2{
	template<class T>
	inline void read(T &x){
		static bool iosig;
		static char c;
		for(iosig=false,c=getchar();!isdigit(c);c=getchar()){
			if(c=='-')iosig=true;
			if(c==-1)return;
		}
		for(x=0;isdigit(c);c=getchar())x=((x+(x<<2))<<1)+(c^'0');
		if(iosig)x=-x;
	}
}
using namespace fastIO1;
vector<int> G[N];
int n,f[N],w[N],ans;
void dfs(int u,int pre){
	int tmp=0;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==pre)continue;
		dfs(v,u);
		tmp|=(f[u]&f[v]);
		f[u]|=f[v];
	}
//	cout<<u<<" "<<f[u]<<" "<<tmp<<endl;
	if(f[u]==0){f[u]=1;return;}
	//f[u]:至少在2个v中出现过的 sum:并
	while(((1<<w[u])&f[u])||(1<<w[u])<tmp)w[u]++;
	f[u]=(f[u]/(1<<w[u])*(1<<w[u]))|(1<<w[u]); ans=max(ans,w[u]);
}
int main(){
	read(n);
	for(int i=1,x,y;i<n;i++)
	read(x),read(y),G[x].push_back(y),G[y].push_back(x); 
	dfs(1,0); for(int i=1;i<=n;i++)ans=max(ans,w[i]);
	cout<<ans;
}

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

using namespace std;
using ll=long long ;

int D;

int res = 0;
ll pw[19];
int digit[19];

void dfs(int high, int low, ll dif, ll way, bool carry) {
    if (high < low) {
        if (dif == D) res += way;
    } else if(high == low) {
        dfs(high-1, low+1, dif, way*10, 0);
    } else {
        int d = digit[low] + carry; carry = 0;
        if (d == 10) d = 0, carry = 1;
        dfs(high-1, low+1, dif + (pw[low] - pw[high])*d, way*(10-d-(low==0 && d==0)), carry);
        if (d > 0) {
            dfs(high-1, low+1, dif + (pw[low] - pw[high])*(d-10), way*(d - (low==0)), 1);
        }
    }
}

void solve() {
    cin >> D;
    pw[0] = 1;
    for (int i = 1; i <= 18; i++) {
        pw[i] = 10*pw[i-1];
    }
    ll x = D;
    for (int i = 0; i <= 18; i++) {
        digit[i] = x%10;
        x/=10;
    }
    for (int len = 1; len <= 18; len++) {
        dfs(len-1, 0, 0, 1, 0);
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 636
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

int main()
{
  string S, T, U;
  int A, B;
  cin >> S >> T >> A>> B >>U;

  if(S==U) A--;
  if(T==U) B--;

  cout << A << " " << B << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[850000],b[850000],i;
int main()
{
  scanf("%s%s",a,b);
  if(strlen(a)>strlen(b))
   cout<<"GREATER";
  if(strlen(a)<strlen(b))
   cout<<"LESS";
  if(strlen(a)==strlen(b)) 
  {
  	i=0;
    while(a[i])
    {
    	if(a[i]>b[i])
    	{
    	 cout<<"GREATER";
    	 return 0;
	    }
	    if(a[i]<b[i])
	    {
	    	cout<<"LESS";
	    	return 0;
		}
	    i++;
	}
	cout<<"EQUAL";
   }
}

Measured memory_bytes: 256
#include <iostream>
#include <random>
#include <chrono>
#include <algorithm>
#define rep(i, x) for(ll i = 0; i < x; i++)
#define CONCAT_(x,y) x##y
#define CONCAT(x,y) CONCAT_(x,y)
#define _v1 CONCAT(qyw1, __LINE__) // unique name in same line (otherwise use __COUNTER__)
#define _v2 CONCAT(qyw2, __LINE__)
#define forbits(i, m) for (int _v1 = m, i = __builtin_ctz(_v1); _v1 != 0; _v1 ^= _v1 & -_v1, i = __builtin_ctz(_v1))
#define forsubm(s, m) for (int s = m; s >= 0; s = !s ? -1 : m & (s - 1))
int __nextXZW(int v){int t=v|(v-1);int w=(t+1)|(((~t&-~t)-1)>>(__builtin_ctz(v)+1));return w;}
#define ksets(i, n, k) for (int i = (1u << k) - 1, max = i << (n - k); i <= max; i = __nextXZW(i))
using namespace std;
typedef long long ll;
const ll MOD = (ll)1e9+7;
const ll N = 5e5+5, inf = 1e9+5000;
ll add(ll x, ll y) { x += y; if (x >= MOD) return x - MOD; return x; }
ll sub(ll x, ll y) { x -= y; if (x < 0) return x + MOD; return x; }
ll mult(ll x, ll y) { return (x * y) % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <atcoder/string>
using namespace atcoder;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  string s; cin >> s;
  int n = s.length();
  auto sa = suffix_array(s);
  auto lcpa = lcp_array(s, sa);
  ll ans = n - sa[0];
  for (int i = 0; i < lcpa.size(); i++) {
    ans += (n - sa[i+1]) - lcpa[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 15656
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    int a, b, c, k;
    cin >> a >> b >> c >> k;

    if (k < a) {
        cout << k << endl;
    } else {
        k -= a;
        if (k < b) {
            cout << a << endl;
        } else {
            k -= b;
            cout << a - k << endl;
        }
    }

    return 0;
}

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

int main(){
    string s;
    cin >> s;
    long long int K;
    cin >> K;
    for(long long int i=0; i<K; i++){
        if(s[i] != '1'){
            cout << s[i];
            return 0;
        }
    }
    cout << '1';
    return 0;
}

Measured memory_bytes: 256