akhauriyash/Code-Regression huggingface dataset:
n, k = map(int, input().split())

num_list = list(range(1, n+1))
count = 0

if k % 2 == 1:
    count = (n // k) ** 3  

else:
    count = (n // k) ** 3  + ((n + k // 2) // k )** 3

print(count)

Measured memory_bytes: 64140
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	vector<int>v;
	int a;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		v.push_back(a);
	}
	sort(v.begin(),v.end());
	int alice=0,bob=0;
	reverse(v.begin(),v.end());
	for(int i=0;i<v.size();i++)
	{
		if(i%2==0)alice+=v[i];
		else bob+=v[i];
	}
	cout<<alice-bob;
	return 0;
}

Measured memory_bytes: 256
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
data = []
for i in range(m):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    data.append([a - 1, b - 1])

ans = 0

def dfs(queue, a, b):
    while len(queue) != 0:
        x = queue.popleft()
        for i in range(len(graph[x])):
            if (min(graph[x][i], x) != a or max(x, graph[x][i]) != b) and visited[graph[x][i]] == 0:
                queue.append(graph[x][i])
                visited[graph[x][i]] = 1

for i in range(m):
    visited = [0] * n
    visited[0] = 1
    queue = deque()
    queue.append(0)
    dfs(queue, data[i][0], data[i][1])
    if sum(visited) != n:
        ans += 1

print(ans)

Measured memory_bytes: 74180
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll s[110000];
bool ok;
ll ans;
ll m, n;
ll a, b;
int main() {
	cin >> n;
	n %= 12;
	cin >> a >> b;
	REP(i, n) {
		ll c = a, d = b;
		if(i % 2 == 0) a = c - d;
		else b = c + d;
	}
	cout << a << " " << b << endl;
}




Measured memory_bytes: 3108
<?php
list($N, $M, $K) = fscanf(STDIN, '%d %d %d\n');
$result = 'No';
for ($i=0;$i<=$N;$i++){
    for($j=0;$j<=$M;$j++){
        if ($j * ($N-$i) + $i * ($M-$j) === $K){
            $result =  'Yes';
        }
    }
}
echo $result;

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

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

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

    int cnt;

    for(int i=0;i<n;i++){
        if(x==s[i]){
            cnt = i;
            break;
        }
    }
    cnt++;
    int sum=0;
    while(cnt<n){
        sum += t[cnt];
        cnt++;
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(a.begin(), a.end());
	cout << a[n - 1] - a[0] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long int ll;

int main(){
    ll n;
    std::cin >> n;
    std::vector<ll>vec(n);
    std::string s="YES";
    for(ll i=0;i<n;++i){
        std::cin >> vec[i];
    }
    std::sort(vec.begin(),vec.end());
    for(ll i=0;i<n-1;++i){
        if(vec[i]==vec[i+1]){
            s="NO";
            break;
        }
    }
    std::cout << s << std::endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int x, y;
  cin >> x >> y;
  int ans = 0;
  int base = 100000;
  ans += max(0, (4 - x) * base);
  ans += max(0, (4 - y) * base);
  if(x == y && x == 1) ans += 4 * base;
  cout << ans << endl; 
}

Measured memory_bytes: 256
n, k = map(int, input().split())
buildings = list(map(int, input().split()))

ans = float('inf')
for i in range(2 ** n):
    res = 0
    cnt = 0
    prev_build = buildings[0]
    for j in range(n):
        if (i >> j) & 1 == 1:
            cnt += 1
            if prev_build >= buildings[j] and not j == 0:
                res += ((prev_build + 1) - buildings[j])
                prev_build = prev_build + 1
            else:
                prev_build = buildings[j]
        else:
            if prev_build < buildings[j]:
                prev_build = buildings[j]

    if cnt == k:
        ans = min(ans, res)

print(ans)

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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    string s;
    cin >> s;
    string t;
    t += s[0];
    ll cnt = s[0] - '0';
    for (int i = 0; i < s.size()-1; i++) {
        t += '9';
        cnt += 9;
    }
    if(s == t){
        cout << cnt << endl;
    } else {
        cout << cnt-1 << endl;
    }
}

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

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using ull = unsigned long long;

#define NL '\n'
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define sii(x, y) scanf("%d%d",&x, &y)
#define sll(x, y) scanf("%lld%lld",&x, &y)

#define xx first
#define yy second
#define ins insert
#define mp make_pair
#define pb push_back
#define mdx ((l+r)>>1)
#define ldx ((idx<<1))
#define rdx ((idx<<1)|1)
#define sz(x) x.size()
#define pi 2.0*acos(0.0)
#define sqr(x)  ((x) * 1ll * (x))
#define all(x) (x).begin(),(x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define file_in(); freopen("input.txt", "r", stdin);
#define file_out(); freopen("output.txt", "w", stdout);
#define file_err(); freopen("serr.txt", "w", stderr);
#define rep(ii,aa,bb) for(ll (ii)=ll(aa);(ii)<(ll)(bb);++(ii))
#define _fastIO() ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define _runtime() cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

template<class T> T setbit(T n, T pos){n=n|(1<<pos); return n;}
template<class T> T checkbit(T n, T pos){n=n&(1<<pos); return n;}
template<class T> T gcd(T a, T b ) {return b<=0?a:gcd(b,a%b);}
template<class T> T lcm(T a, T b) {return ((a / gcd(a,b) ) * b);}





const int mxx = 1e5+9;
int n, a[mxx], dp[mxx];

int fun(int pos){
	if(pos + 1 == n) return 0;
	if(dp[pos] == -1){
		dp[pos] = (abs(a[pos+1]-a[pos]) + fun(pos + 1));
		if(pos + 2 != n) dp[pos] = min(dp[pos], (abs(a[pos+2]-a[pos]) + fun(pos + 2)));
	}
	return dp[pos];
}

int main(){
	_fastIO();
	mem(dp, -1);
	cin >> n; rep(i, 0, n) cin >> a[i];
	cout << fun(0) << NL;
}

Measured memory_bytes: 4224
import java.io.*;
import java.util.*;
 
public class Main{
	int N, M, K;
	public void solve(){
		N = nextInt();
		M = nextInt();
		K = nextInt();
		int max = N * M;
		for(int i = 0; i <= N; i++){
			for(int j = 0; j <= M; j++){
				int num = (i * ((M - j))) + (j * (N - i));
				if(K == num || (max - num) == K){
					out.println("Yes");
					return;
				}
			}
		}
		out.println("No");
	}
	
	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}
	
	public static int nextInt(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}
	
	public static long nextLong(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}
	public static String next(){
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	
	
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
}

Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll lcm(ll A[],int n){
  ll ans=A[0];
  for(int i=1;i<n;i++){
    ans=(ans*A[i])/(__gcd(ans,A[i]));
  }
  return(ans);
}
int main(){
	int n,m;
  	cin>>n>>m;
  	ll A[n];
  	for(int i=0;i<n;i++) {
      cin>>A[i];
      A[i]/=2;
    }
  	set<int> all_power;
  	for(int i=0;i<n;i++){
      ll x=A[i];
      int power=0;
      while(!(x%2)){
        x/=2;
        power++;
      }
      all_power.insert(power);
      if(all_power.size()>1){
        cout<<0;
        return(0);
      }
    }
  	ll l=lcm(A,n);
  	m/=l;
  	ll ans=(m+1)/2;
  	cout<<ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int a; cin>>a;
	string s; cin>>s;
	if(a>=3200) cout<<s;
	else cout<<"red";
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,ans,s;
map<int,int> m;
vector<int> v;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>s;
		if(m[s]==0) v.push_back(s);
		m[s]++;
	}
	for(int i=0;i<v.size();i++) 
		if(m[v[i]]>=v[i]) ans+=m[v[i]]-v[i];
		else ans+=m[v[i]];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5112
#include <stdio.h>

char str[1005];
char p[1005];

int main()
{
   int q, a, b;
   char op[10], *x, *y, c;
    
   scanf("%s%d", str, &q);
   while (q--) {
       scanf("%s%d%d", op, &a, &b);
       if (op[2] == 'i') {             // print
           b++, c = *(str+b), *(str+b) = 0, puts(str+a), *(str+b) = c;
       } else if (op[2] == 'v') {      // reverse
           x = str+a, y = str+b;
           while (x < y) {
               c = *x, *x = *y, *y = c;
               x++, y--;
           }
       } else {                        // replace
           scanf("%s", p);
           x = str+a, y = p;
           while (*y) *x++ = *y++;
       }
   }
   return 0;
}


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

int main(){
    int P,Q,R;
    cin >> P>>Q>>R;
    if(P>=Q&&P>=R){
        printf("%d\n",Q+R);
        return 0;
    }else if(Q>=P&&Q>=R){
        printf("%d\n",P+R);
        return 0;
    }else{
        printf("%d\n",P+Q);
        return 0;
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sumitrust2019_A
{
    class Program
    {
        static void Main(string[] args)
        {
            var md1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var md2 = Console.ReadLine().Split().Select(int.Parse).ToArray();

            Console.WriteLine(md2[0] - md1[0]);
        }
    }
}


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

const int N = 1e3 + 5;
int sum[30], s[5];

int main()
{
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string S; cin >> S;
		for (int j = 0; j < m; j++) sum[S[j] - 'a']++;
	}
	for (int i = 0; i < 26; i++)
	{
		s[4] += sum[i] / 4;
		sum[i] %= 4;
		s[2] += sum[i] / 2;
		s[1] += sum[i] % 2;
	}
	int a = 0, b = 0, c = 0;
	a = (n / 2) * (m / 2);
	if (n & 1) b += m / 2;
	if (m & 1) b += n / 2;
	if (n % 2 && m % 2) c = 1;
//	cout << a << " " << b << " " << c << endl;
	int ans = 1;
	if (s[4] < a) ans = 0;
	s[4] -= a; s[2] += s[4] * 2;
	if (s[2] < b) ans = 0;
	s[2] -= b; s[1] += s[2] * 2;
	if (s[1] < c) ans = 0;
	puts(ans ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <queue>

#define fti(i, x, y) for(int i = (x), _y = (y); i <= _y; ++ i)
#define ftd(i, x, y) for(int i = (x), _y = (y); i >= _y; -- i)
#define pb push_back

using namespace std;

const int oo = 1e9, N = 302;
typedef pair <int, int> ii;
typedef pair <ii, int> iii;
vector <ii> a[N];
int n, m, L, res[N][N];
ii d[N];
priority_queue <iii, vector<iii>, greater<iii> > pq;

void inp()
{
    int p, q, m, w;
    scanf("%d %d %d", &n, &m, &L);
    fti(i, 1, m) {
        scanf("%d %d %d", &p, &q, &w);
        a[p].pb(ii(w, q));
        a[q].pb(ii(w, p));
    }
}
//#include <iostream>

void dijkstra(int s)
{
    int u, v, du1, du2, uv;
    fti(i, 1, n) d[i] = ii(oo, 0);
    d[s] = ii(0, L);
    pq.push(iii(ii(0, 0), s));
    while (!pq.empty()) {
        u = pq.top().second;
        du1 = pq.top().first.first;
        du2 = pq.top().first.second;
        //cout << u << " " << du1 << " " << L - du2 << "\n";
        pq.pop();
        if (du1 != d[u].first || du2 != L - d[u].second) continue;
        fti(i, 0, int(a[u].size() - 1)) {
            uv = a[u][i].first;
            v = a[u][i].second;
            if(uv > L) continue;

            int tg = 0, tg2 = L - du2 - uv;
            if(tg2 < 0) tg = 1, tg2 = L - uv;

            if(d[v].first == du1 + tg)
                if(d[v].second < tg2) d[v].second = tg2, pq.push(iii(ii(d[v].first, L - d[v].second), v));
            if(d[v].first > du1 + tg) d[v] = ii(du1 + tg, tg2), pq.push(iii(ii(d[v].first, L - d[v].second), v));
        }
    }
}
void proc()
{
    fti(i, 1, n) {
        dijkstra(i);
        fti(j, 1, n) {
            if(d[j].first == oo) res[i][j] = -1;
            else res[i][j] = d[j].first;
            //cout << res[i][j] << " ";
        }
        //cout << "\n";
    }
    int q, x, y;
    scanf("%d", &q);
    while(q -- ) {
        scanf("%d %d", &x, &y);
        printf("%d\n", res[x][y]);
    }
}

int main()
{
    inp();
    proc();
    return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++) 
#define ll long long
#define ld long double
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)  

int main()
{
  ll n;
  cin >> n;
  ll sum = 0;
  
  for(ll i = 1; i <= n; i++)
  {
    if(i % 3 != 0 && i % 5 != 0)
    {
      sum += i;
    }
  }
  
  cout << fixed << sum << endl;
 
  
  return 0;
}


Measured memory_bytes: 3676
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
	int N;
  	cin >> N;
    string S;
  	cin >> S;
  	int init =0;
  	int samp =0;
  	for (int i=0; i<N; ++i) {
      if (i == 0) {//最初だけは特別に、初期値を設定する。
        for (int j=1; j<N; ++j) {
          if (S[j] == 'E') init +=1;
        }
        samp = init; //初期値と仮値を同じにする
        continue;
      }
      if (S[i] == 'E') {
        samp -= 1; //もしEの人がリーダーになった場合
      }
      if (S[i-1] == 'W') { 
        samp += 1; //もしWの人がリーダーより西側に行った場合
      }
      if (samp < init) init = samp;
    }
  	cout << init;
  	return 0;
}

Measured memory_bytes: 900
#include <iostream>
#include <map>
#include <initializer_list>
using namespace std;

int main()
{
  int N; cin >> N;
  map<string, int> dic;
  for (int i = 0; i < N; i++) {
    string str; cin >> str;
    if (dic[str]) dic[str]++;
    else dic[str] = 1;
  }
  int M; cin >> M;
  for (int i = 0; i < M; i++) {
    string str; cin >> str;
    if (dic[str]) dic[str]--;
  }
  int MAX = 0;
  for (auto itr = dic.begin(); itr != dic.end(); itr++)
    MAX = max(MAX, itr->second);
  cout << MAX << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define all(X) X.begin(),X.end()

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   str.substr (x) : returns a substring str[x],... end of string
   str.find(qtr) : returns the first occurenece of qtr in str */

const int M = (1<<20)+5;
const int md = 1e9+7;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

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

	ll m1,m2,d1,d2;

	cin >> m1 >> d1 >> m2 >> d2;

	if(m2 == m1+1)
		cout << 1 << endl;
	else
		cout << 0 << endl;

	return 0;
}


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

int main(){
  int k,a,b;
  cin >> k >> a >> b;
  int n = b-a+1;
  int ans = 0;
  rep(i,n){
    if(a%k == 0) {
      ans = 1;
      break;
    }
    a++;
  }
  if(ans == 1) cout << "OK" << endl;
  else cout << "NG" << endl;
}

Measured memory_bytes: 3596
H, W = map(int, input().split())
S = [input() for _ in range(H)]

dx = [-1,0,1,-1,1,-1, 0, 1]
dy = [1, 1,1, 0,0,-1,-1,-1]

for y in range(H):
    for x in range(W):
        s = S[y][x]
        if s == "#":
            tmp = "#"
        else:
            bomb = 0
            for k in range(8):
                x_next = x + dx[k]
                y_next = y + dy[k]

                if x_next < 0 or y_next < 0 or x_next >= W or y_next >= H:
                    continue

                if S[y_next][x_next] == "#":
                    bomb += 1
            tmp = str(bomb)
        print(tmp, end="")
    print("")

Measured memory_bytes: 3444
A, B, C, X, Y = [int(i) for i in input().split()]

price = min(A+B, 2*C) * min(X, Y)
need_A = max(0, X-Y)
need_B = max(0, Y-X)

if need_A > 0:
    price += need_A * min(A, 2*C)
if need_B > 0:
    price += need_B * min(B, 2*C)

print(price)

Measured memory_bytes: 3064
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

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

int num[100010];

int func(int x){
  if(x%2==0)return (x/2);
  else return (3*x+1);
}

int main()
{
  int s;
  cin >> s;
  num[s]++;
  int k = s;
  int i = 1;
  while (1)
  {
    k = func(k);
    if(num[k]==1){
      cout << i + 1 << endl;
      break;
    }
    num[k]++;
    i++;
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] abc = new int[3];
		for(int i=0;i<3;i++) {
			abc[i] = in.nextInt();
		}
		int[] l = new int[n];
		int num = 1;
		for(int i=0;i<n;i++) {
			l[i] = in.nextInt();
			num *= 4;
		}
		int ans = Integer.MAX_VALUE;
		for(int i=0;i<num;i++) {
			int[] tmp_l = new int[3];
			int mod = 1;
			int tmp_ans = 0;
			for(int j=0;j<n;j++) {
				if((i/mod)%4==0) {
					if(tmp_l[0]!=0) tmp_ans += 10;
					tmp_l[0] += l[j];
				}
				else if((i/mod)%4==1) {
					if(tmp_l[1]!=0) tmp_ans += 10;
					tmp_l[1] += l[j];
				}
				else if((i/mod)%4==2) {
					if(tmp_l[2]!=0) tmp_ans += 10;
					tmp_l[2] += l[j];
				}
				mod *= 4;
			}
			if(tmp_l[0]==0 || tmp_l[1]==0 || tmp_l[2]==0) {
				//continue;
			}else {
				tmp_ans += Math.abs(abc[0]-tmp_l[0]) + Math.abs(abc[1]-tmp_l[1]) + Math.abs(abc[2]-tmp_l[2]);
				if(tmp_ans<ans) ans = tmp_ans;
			}
		}
		System.out.println(ans);
		in.close();

	}

}


Measured memory_bytes: 26452
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
LL mod = 1e9+7;

int main(){
    string S;
    cin >> S;
    int n = S.size();
    vector<LL>  dpa(n+1, 0), dpb(n+1, 0), dpc(n+1, 0), dpsum(n+1, 0);
    dpsum[0] = 1;
    for(int i = 0;i < n;i++){
        dpa[i+1] = dpa[i];
        dpb[i+1] = dpb[i];
        dpc[i+1] = dpc[i];
        dpsum[i+1] = dpsum[i];
        if(S[i] == 'A'){
            dpa[i+1] += dpsum[i];
            dpa[i+1] %= mod;
        }else if(S[i] == 'B'){
            dpb[i+1] += dpa[i];
            dpb[i+1] %= mod;
        }else if(S[i] == 'C'){
            dpc[i+1] += dpb[i];
            dpc[i+1] %= mod;
        }else{
            dpa[i+1] += dpsum[i]+dpa[i]*2;
            dpa[i+1] %= mod;
            dpb[i+1] += dpa[i]+dpb[i]*2;
            dpb[i+1] %= mod;
            dpc[i+1] += dpb[i]+dpc[i]*2;
            dpc[i+1] %= mod;
            dpsum[i+1] += dpsum[i]*2;
            dpsum[i+1] %= mod;
        }
    }
    cout << dpc[n] << endl;
}

Measured memory_bytes: 3584
from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
v = list(map(int, input().split()))
v1, v2 = [v[i] for i in range(n) if i % 2 == 0], [v[i] for i in range(n) if i % 2]
c1, c2 = Counter(v1).most_common(), Counter(v2).most_common()
l1, l2 = len(c1), len(c2)
if l1 == 1 and l2 == 1:
    if c1[0][0] == c2[0][0]:
        print(n // 2)
    else:
        print(0)
elif l1 == 1:
    if c1[0][0] == c2[0][0]:
        print(n//2 - c2[1][1])
    else:
        print(n//2 - c2[0][1])
elif l2 == 1:
    if c1[0][0] == c2[0][0]:
        print(n//2 - c1[1][1])
    else:
        print(n//2 - c1[0][1])
else:
    if c1[0][0] == c2[0][0]:
        if c1[0][1] + c2[1][1] < c1[1][1] + c2[0][1]:
            print(n - c1[1][1] - c2[0][1])
        else:
            print(n - c1[0][1] - c2[1][1])
    else:
        print(n - c1[0][1] - c2[0][1])

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

class Main{

	static int[] a;
	static	int N ;

	public static void main(String[] args) {


		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		a = new int[N];
		for(int i = 0;i < a.length;i++){
			a[i] = scanner.nextInt();
		}
		Arrays.sort(a);
		
		
		int[] data = new int [100000];
		for(int i = 0;i <a.length;i++){
			data[a[i]]++;
		}

		int ans = 0;

		for(int i = 1;i < data.length-1;i++){
			ans = Math.max(ans, data[i]+data[i+1]+data[i -1]);
			
		}
		
//		
//		for(int i = 0;i < a.length;i++){
//			int count1 = 0;
//			int count2 = 0;
//			int count3 = 0;
//
//			int k = a[i];
//
//			for(int j = 0;j < a.length;j++){
//				if(Math.abs(a[j] - k)<= 1){
//					count1++;
//				}	
//				if(a[j] > k + 1){
//					break;
//				}
//			}
//			for(int j = 0;j < a.length;j++){
//				if(Math.abs(a[j] - (k - 1))<= 1){
//					count2++;
//				}	
//				if(a[j] > k + 2){
//					break;
//				}
//			}
//			for(int j = 0;j < a.length;j++){
//				if(Math.abs(a[j] - (k + 1))<= 1){
//					count3++;
//				}	
//				if(a[j] > k - 1){
//					break;
//				}
//			}
//			
//
//			ans = Math.max(ans, Math.max(count1, Math.max(count2, count3)));
//
//
//		}
		
		System.out.println(ans);


	}


}

class Pair implements Comparable{
	int from;
	int middle;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}





Measured memory_bytes: 50228
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
int main()
{
    int n,k;
    ll MIN;
    cin>>n>>k;
    ll h[n];
    for(int i=0;i<n;i++)cin>>h[i];
    ll dp[n];
    memset(dp,0,n);
    dp[0]=0;
    for(int i=1;i<n;i++){
            MIN=1e+9;
            for(int j=i-1;j>=max(i-k,0);j--){
                MIN=min(MIN,dp[j]+abs(h[i]-h[j]));
            }
        dp[i]=MIN;
    }
    cout<<dp[n-1];
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    sort(p.begin(), p.end());
    ans -= p.back() / 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
using namespace std;

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

const int N = 3e5 + 5, md = 1e9 + 7;

inline int add(int x, int y) {
    x += y;
    if(x >= md) x -= md;
    return x;
}

inline int sub(int x, int y) {
    x -= y;
    if(x < 0) x += md;
    return x;
}

inline int mul(int x, int y) { return 1ll * x * y % md; }

ll a[N];
int n, ans;

int main() {
   
  
  cin>>n;
for(register int i = 1; i <= n; i++)
	cin>>a[i];

 
 for(register int j = 0; j < 60; j++) {
	 int cnt = 0;
        for(register int i = 1; i <= n; i++)
		cnt += ((a[i]>>j)&1);
	//ll temp = 1LL<<j;
	//ans= (ans + ((temp % mod) * (cnt*(n-cnt)) ) % mod);
	ans = add (ans , mul((1LL << j) %md , mul(cnt,n-cnt)));
}

cout<<ans;
    return 0;
}


Measured memory_bytes: 2560
A, B, K = map(int, input().split())
k = 0
x = 1
l = [0]


for x in range(min([A, B])+1):
    if x != 0:
        if (A % x == 0) & (B % x == 0):
            l.append(x)
l.reverse()

print(l[K-1])


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

int main()
{
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int count = 0;


    for (int i = 0; i < a+1; i++)
    {
        for (int j = 0; j < b+1; j++)
        {
            for (int k = 0; k < c+1; k++)
            {
                if (i*500 + j*100 + k*50 == x) count++; 
            }
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    K, X = LI()
    if K * 500 >= X:
        print("Yes")
    else:
        print("No")
    return


# B
def B():
    n = I()
    s = S()
    cnt = 0
    for i in range(n - 2):
        if s[i] == "A":
            if s[i + 1] == "B"  and s[i + 2] == "C":
                cnt += 1
    print(cnt)
    return


# C
def C():
    return


# D
def D():
    return


# E
def E():
    return


# F
def F():
    return


# Solve
if __name__ == "__main__":
    B()


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n, x;
  cin >> n;
  vector<int> b;
  rep(i, n) {
    cin >> x;
    x--;
    b.push_back(x);
  }
  int now = 0, c = 0;
  while(true){
    if(now == 1) {
      cout << c << endl;
      break;
    }
    if(c >= n){
      cout << -1 << endl;
      break;
    }
    now = b[now];
    c++;
  }
}


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

int main() {
	int length;
	long long sum = 0;
	cin >> length;
	int *a = new int[length];
	for (int i = 0; i < length; i++) {
		cin >> a[i];
		sum += a[i];
	}
	long long sum1 = a[0];
	long long min = abs(sum - 2 * sum1);
	for (int i = 1; i < length-1; i++) {
		sum1 += a[i];
		if (abs(sum-2*sum1) < min)
			min = abs(sum-2*sum1);
	}
	cout << min << endl;
}

Measured memory_bytes: 1024
n = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a = prime_factorize(n)
counter = 0
for i in set(a):
    cou = a.count(i)
    tmp = 0
    j = 1
    while tmp < cou:
        tmp += j
        j += 1
        if tmp <= cou:
            counter += 1
print(counter)

Measured memory_bytes: 9220
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

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

using namespace std;

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

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

string S;

int main() {
    cin >> S;
    cout << string(S.length(), 'x') << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K,Q;
  cin>>N>>K>>Q;
  vector<int> A(N);
  for(int i=0;i<Q;i++){
    int x;
    cin>>x;
    A.at(x-1)++;
  }
  for(int i=0;i<N;i++){
    string S=Q-A.at(i)<K?"Yes":"No";
    cout<<S<<endl;
  }
}


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

struct State{
	int t, s, d;
	State(int t_, int s_, int d_){
		t = t_; s = s_; d = d_;
	}
	State(){}
};
bool operator<(const State &a, const State &b){
	return a.t < b.t;
}

int main(){
	int N, M;
	while( cin >> N >> M, N || M ){
		vector<bool> c(N, false);
		c[0] = true;
		vector<State> v;
		for(int i=0 ; i < M ; i++ ){
			int t, s, d;
			cin >> t >> s >> d;
			s--, d--;
			v.push_back(State(t, s, d));
		}
		sort(v.begin(), v.end());
		for(int i=0 ; i < v.size() ; i++ ){
			if( c[v[i].s] ) c[v[i].d] = true;
		}
		int ans = 0;
		for(int i=0 ; i < N ; i++ ){
			if( c[i] ) ans++;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1680
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
#include <climits>
using namespace std;
string s;
int main() {
    cin >> s;
    int n=s.size();
    sort(s.begin(), s.end());
    bool flag = true;
    if(n%2!=0) flag=false;
    int cnt=0;
    for(int i=0; i<n-1; ++i){
        if(s[i] == s[i+1]) {
            cnt++;
        }
        else
        {
            if(cnt%2==0) flag = false;
            cnt=0;
        }
        if(!flag) break;
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define ff fflush(stdout)
#define eps 1e-6
#define PI atan(1) * 4
#define mod 1000000007
#define inf 1000000000000000000
using namespace std;
int num[10005];
int res[105][105];
int main () {
	int a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q;
	scanf("%d %d", &a, &b);
	scanf("%d", &c);
	for (i = 1; i <= c; i++) {
		scanf("%d", &num[i]);
	}
	d = 1;
	for (i = 1, j = 1, k = 1; i <= a; j += d) {
		if (j > b) {
			j = b; i++; d = -1;
		} else if (j < 1) {
			j = 1; i++; d = 1;
		}
		if (i > a) break;
		while (num[k] == 0) k++;
		res[i][j] = k;
		num[k]--;
	}
	for (i = 1; i <= a; i++) {
		for (j = 1; j <= b; j++) {
			printf("%d%c", res[i][j], (j == b) ? '\n' : ' ');
		}
	}
	return 0;
}

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

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

  int A;
  
  int X;
  int minX;
  
  minX = 0;
  
  for(int i = 0; i < N; i++){

    cin >> A;
    X = 0;
    
    while( (A % 2) == 0){
		X++;
        A = A / 2;
    }
    
    if (X == 0){
      minX = X;
      break;
    }
    
    //初回は最小値にそのまま代入
    if (i == 0){
      minX = X;
    }
    //2回目以降は最小値を比較
    else{
      if(X < minX){
        minX = X;
      }
    }
  }
  
  cout << minX << endl;
}


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

int main(){
  Int N, A, B;
  cin >> N >> A >> B;
  
  if ((A - B) % 2 == 0) {
	cout << abs(A-B) / 2 << endl;
    return 0;
  }
  
  else {
    Int x, y;
    x = min(A, B);
    y = max(A, B);
    
    if (x-1 <= N-y) {
      cout << x + (y-x-1) / 2 << endl;
    }
    else {
      cout << N - y + 1 + (y-x-1) / 2 << endl;
    }
  }
}


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

typedef pair<int, int> P;

struct Edge {
  int to, cost;
};

int n;
vector<vector<Edge> > G;

vector<int> dij() {
  priority_queue<P, vector<P>, greater<P> > Q;
  vector<int> d(n, -1);
  Q.push({0, 0});
  while ( !Q.empty() ) {
    P p = Q.top(); Q.pop();
    int v = p.second, c = p.first;

    if ( d[v] >= 0 ) continue;
    d[v] = c;
    
    for ( Edge e: G[v] ) {
      Q.push({c+e.cost, e.to});
    }    
  }

  return d;
}

int main() {
  cin >> n;

  G = vector<vector<Edge> >(n);
  for ( int i = 0; i < n; i++ ) {
    int u, k;
    cin >> u >> k;
    for ( int i = 0; i < k; i++ ) {
      int v, c;
      cin >> v >> c;
      G[u].push_back({v, c});      
    }
  }

  vector<int> d = dij();
  for ( int i = 0; i < n; i++ ) {
    cout << i << " " << d[i] << endl;
  }
  
  return 0;
}



Measured memory_bytes: 11760
def main():
    x, y = map(int,input().split())

    if x % y == 0:
        print(-1)
        exit()


    i=0
    while True:
        if x * i % y == 0:
            i+=1
        else:
            print(x)
            exit()


if __name__ == "__main__":
        main()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define ford(i,a,b) for(int i=(a);i>=b;i--)
#define rep(i,a,b) for(int i=(a);(i)<=(b);(i)++)
#define ll long long
#define mp map<int,int>
using namespace std;
int a[200005],b[200005];
int main() {
	int n;
	cin>>n;
	rep(i,1,n) cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	rep(i,1,n) {
		if(a[i]<b[n]) cout<<b[n]<<"\n";
		else cout<<b[n-1]<<"\n";
	}
	return 0;
}


Measured memory_bytes: 3200
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func main() {
	N, K := nextInt(), nextInt()
	Hs := nextInts(N)
	fmt.Println(solve(K, Hs))
}

func solve(K int, Hs []int) int {
	N := len(Hs)
	dp := make([]int, N)
	dp[0] = 0

	for i := 1; i < N; i++ {
		dp[i] = math.MaxInt32
		for j := 1; j <= K; j++ {
			if i-j >= 0 {
				dp[i] = Min(dp[i], dp[i-j]+Abs(Hs[i]-Hs[i-j]))
			}
		}
	}
	return dp[N-1]
}

func Min(xs ...int) int {
	min := xs[0]
	for _, x := range xs[1:] {
		if min > x {
			min = x
		}
	}
	return min
}

func Abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Buffer(make([]byte, 256), 1e9)
	sc.Split(bufio.ScanWords)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}


Measured memory_bytes: 2816
//package solution;

import java.io.*;
import java.util.*;
import java.math.*;
import java.awt.Point;

public final class Main {
    BufferedReader br;
    StringTokenizer stk;

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    {
        stk = null;
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    void run() throws Exception {
        int n = ni();
        long[] a = new long[n];
        for(int i=0; i<n; i++) a[i] = nl();
        
        long[] dp = new long[n];
        dp[0] = 0; dp[1] = Math.abs(a[0] - a[1]);
        for(int i=2; i<n; i++) {
            dp[i] = Math.min(dp[i-1] + Math.abs(a[i] - a[i-1]), dp[i-2] + Math.abs(a[i] - a[i-2]));
        }
        
        pl(dp[n - 1]);
    }
    
    //Reader & Writer
    String nextToken() throws Exception {
        if (stk == null || !stk.hasMoreTokens()) {
            stk = new StringTokenizer(br.readLine(), " ");
        }
        return stk.nextToken();
    }

    String nt() throws Exception {
        return nextToken();
    }

    String ns() throws Exception {
        return br.readLine();
    }

    int ni() throws Exception {
        return Integer.parseInt(nextToken());
    }

    long nl() throws Exception {
        return Long.parseLong(nextToken());
    }

    double nd() throws Exception {
        return Double.parseDouble(nextToken());
    }

    void p(Object o) {
        System.out.print(o);
    }

    void pl(Object o) {
        System.out.println(o);
    }
    
    void selector() {
        Random rd = new Random();
        String[] s = new String[] {"Strings", "Sorting", "Search"
                , "Graph theory", "Greedy", "Dynamic programming"
                , "Constructive algos", "Bit manipulation", "Recursion"};
        pl(s[rd.nextInt(s.length)] + " " + (rd.nextInt(5)+1));
    }
}

Measured memory_bytes: 32212
N = int(input())
X = int(N / 1.08)
flag = False
if int(X*1.08) == N:
    flag = True
    ans = X
elif int((X+1)*1.08) == N:
    flag = True
    ans = X + 1
if flag:
    print(ans)
else:
    print(':(')

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static String s = sc.next();
    static String p = sc.next();

    public static void main(String[] args) {
        String ss = s + s;
        if (ss.contains(p))
            System.out.println("Yes");
        else
            System.out.println("No");

    }
}


Measured memory_bytes: 26324
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <queue>

using namespace std;



int main() {
  string s, t;
  cin >> s;
  cin >> t;

  // sのi番目までを使用した場合と
  // tのj番目までを使用した場合の最長の部分文字列
  int table[s.size()+1][t.size()+1];
  for (int i = 0; i <= s.size(); ++i) {
    table[i][0] = 0;
  }
  for (int i = 0; i <= t.size(); ++i) {
    table[0][i] = 0;
  }

  for (int i = 0; i < s.size(); ++i) {
    for (int j = 0; j < t.size(); ++j) {
      if(s[i] == t[j]){
        table[i+1][j+1] = table[i][j] + 1;
      }else{
        table[i+1][j+1] = max(table[i+1][j], table[i][j+1]);
      }
    }
  }

//  cout << table[s.size()][t.size()] << endl;
//
//  //
//  for (int i = 1; i <= s.size(); ++i) {
//    for (int j = 1; j <= t.size(); ++j) {
//      cout << table[i][j] << " ";
//    }
//    cout << endl;
//  }


//  int n = table[0][0];
//  for (int i = 1; i <= s.size(); ++i) {
//    for (int j = 1; j <= t.size(); ++j) {
//      if(table[i][j] > n){
//        cout << s[i-1];
//        n++;
//      }
//    }
//  }
//  cout << endl;


  int i = s.size(), j = t.size();
  string ans = "";
  while(i && j) {
    if(table[i][j] == table[i-1][j]) {
      i--;
    } else if(table[i][j] == table[i][j-1]) {
      j--;
    } else {
      ans+=s[i-1];
      i--; j--;
    }
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;


  return 0;
}




Measured memory_bytes: 35456
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <string>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=998244353;
//
struct poi{
	int X;int Y;int Z;
	bool operator<(const poi&R)const{
		return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
	}
};
/*
ll GCD(ll A,ll B){
  return (B==0)?(A):(GCD(B,A%B));
}
ll LCM(ll A,ll B){
  return A/GCD(A,B)*B;
}
*/
int N,K;
int A[100000];
int main(){
	cin>>N>>K;
	int n;
	FOR(i,0,N){
		cin>>A[i];
		if(A[i]==1){
			n=i;
		}
	}
	if(N==K){
		cout<<1<<endl;
	}else if(K==2){
		cout<<N-1<<endl;
	}else if(n<K||n+K>=N){
		cout<<1+(N-K+(K-1)-1)/(K-1)<<endl;
	}else{
		int num=(n+(K-1)-1)/(K-1)*(K-1)+1;
		cout<<(n+(K-1)-1)/(K-1)+(N-num+(K-1)-1)/(K-1)<<endl;
	}
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#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 UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using ll = long long;

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

    ll minw, val;
    cin >> minw >> val;
    vector<vector<ll>> v(4, vector<ll>(1, 0));
    v[0].push_back(val);

    rep(i, n-1){
        int we;
        cin >> we >> val;
        v[we - minw].push_back(val);
    }

    rep(i, 4) sort(rall(v[i]));

    ll ans = 0;

    rep(i, v[0].size()){
        rep(j, v[1].size()){
            rep(k, v[2].size()){
                rep(l, v[3].size()){
                    ll we = (minw)*i + (minw+1)*j + (minw+2)*k + (minw+3)*l;
                    if(we <= w){
                        ll tmp = 0;
                        rep(m, i) tmp += v[0][m];
                        rep(m, j) tmp += v[1][m];
                        rep(m, k) tmp += v[2][m];
                        rep(m, l) tmp += v[3][m];
                        ans = max(ans, tmp);
                    }
                }
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
const ll M=1000000007;
//------------------------------------------//

int main(){
    int S;cin>>S;
    ll dp[3000];
    dp[0]=1;
    dp[1]=0;
    dp[2]=0;
    for(int i=0;i<=S;i++){
        dp[i+3]=dp[i+2]+dp[i];
        dp[i+3]%=M;
        //cout<<dp[i]<<endl;
    }
    cout<<dp[S]<<endl;
}


Measured memory_bytes: 3624
N, x = map(int,input().split())
a = list(map(int,input().split()))

res = 0

for i in range(1,N):
	if a[i-1] + a[i] > x:
		eaten = (a[i-1] + a[i]) - x
		res += eaten
		a[i] = max(a[i] - eaten, 0)

print(res)

Measured memory_bytes: 14540
#include <bits/stdc++.h>
using namespace std;
#define ll long long;
int n,m;
int a[105],sum,num;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    	sum+=a[i];
	}
	double x=sum/(4.0*m);
	for(int i=1;i<=n;i++)
	{
		if(a[i]>=x)
		  num++;
	}
	if(num>=m)
	  cout<<"Yes";
	else
	  cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=100005;
//i_am_noob
int a[3];

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	rep(3) cin >> a[i];
	sort(a,a+3);
	print1(a[2]*10+a[0]+a[1]); 
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string N;
  cin >> N;
  int size = N.size();
  int sum  = 0;
  for (int i = 0; i < size; i++) {
  	sum += N[i] - '0';
  }
  cout << (sum % 9 == 0 ? "Yes" : "No") << endl;
  return 0;
}

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

#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define pb push_back
#define len(x) (int)(x).size()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
const int N = 1e5 + 10;
#define int long long
int cnt[N] , sum[N];
void add(int *fen, int pos , int val){
    for(;pos < N; pos += (pos & -pos))
        fen[pos] += val;
}
int get(int *fen , int pos){
    int ans = 0;
    for(;pos > 0 ; pos -= (pos & -pos)){
        ans += fen[pos];
    }
    return ans;
}

signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n;cin >> n;
    vector<int>a(n);
    for(auto &i : a)cin >> i;
    vector<int>zip = a;


    map<int,int>zipka;
    for(auto i : a)
        zipka[i] = 1;
    int cntZ = 1;
    for(auto &i : zipka)i.se = cntZ++;
    for(auto &i : zip)
        i = zipka[i];

    for(int j = 0; j < n; ++j){
        add(cnt , zip[j] , +1);
        add(sum , zip[j] , +a[j]);
    }
    map<int,int>revzip;
    for(auto &i : zipka)
        revzip[i.se] = i.fi;
    revzip[0] = 0;



    set < int > have;
    int MX = 0;
    for(int i = 0 ; i < n; ++i){
        auto it = have.upper_bound(zip[i]);
        int prev;
        if(it == have.begin())prev = 0;
        else prev = *(--it);
        /// calculate
        if(MX >= zip[i]){
                cout << 0 << '\n';
        }else{
        int cntmore = get(cnt , N-1) - get(cnt, zip[i]-1);

        ll ans = 1ll * (cntmore) * (revzip[zip[i]] - revzip[prev]);
        ll lulzsum = get(sum , zip[i]-1) - get(sum , prev-1);
        ll lulzcnt = get(cnt , zip[i]-1) - get(cnt , prev-1);
        ans += lulzsum - 1ll * lulzcnt * (revzip[prev]);
            cout << ans << '\n';
        }
        MX = max(MX , zip[i]);
        have.insert(zip[i]);
        add(cnt , zip[i] , -1);
        add(sum , zip[i] , -a[i]);

    }
    return 0;
}


Measured memory_bytes: 23572