akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int cmp(char s[100001],char t[100001],int st,int fin)
{
    if(strlen(t)>(fin-st+1))
    {
        return 0;
    }
    int j=0;
    for(int i=st;i<=fin;i++)
    {
        if(s[i] != t[j])
        {
            break;
        }
        j++;
    }
    if(j==(fin-st+1))
    {
        return 1;
    }
    else
    {
        return 0;
    }
    
}
int main(void)
{
    int point=0,judge=0;
    char s[100001],t[100001];
    fgets(s,sizeof(s),stdin);
    int len = strlen(s) - 1;
    while(point<len-4)
    {
        if(cmp(s,"dream",point,point+4))
        {
            judge = 1;
            point = point + 5;
            if(s[point] == 'e'&&s[point+1] == 'r'&&cmp(s,"erase",point,point+4)==0)
            {
                point = point+2;
            }
        }
        if(cmp(s,"erase",point,point+4))
        {
            judge = 1;
            point = point + 5;
            if(s[point] == 'r')
            {
                point++;
            }
        }
        if(judge==0)
        {
            printf("NO");
            return 0;
        }
        else
        {
            judge = 0;
        }
        
    }
    
    if(point==len)
    printf("YES");
    else
    {   
        printf("NO");
    }
    
    
}

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

using namespace std;

typedef long long ll;

int main(){
    ll n;
    cin >> n;
    
    ll ans = 0;
    
    if(n % 2 == 0){
        ans = n / 2 * (n + 1) - n;
    }
    else{
        ans = (n + 1) / 2 * n - n;
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
n, y = map(int, input().split())

for i in range(n+1):
    for j in range(n+1):
        k = n - i - j
        if 0 <= k <= n and 10000*i + 5000*j + 1000*k == y:
            print(i, j, k)
            exit()

print(-1, -1, -1)


Measured memory_bytes: 9064
import decimal
import math

N, K = map(int, input().split())
#coin = [decimal.Decimal('0.5')**k for k in range(10**4)]
ans = 0

for i in range(1,N+1):
    tmp = math.log(K/i, 2)
    x = int(math.log(K/i,2))
    if i >= K:
        ans += 1/N
    else:
        if tmp - x != 0:
            x += 1
        ans += 1/N * (0.5)**x

print(ans)


Measured memory_bytes: 60012
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define llu unsigned long long int
#define Endl endl
#define mod  998244353
#define mkp make_pair
#define pb push_back
#define cin(n) scanf("%d",&n)
#define cout(n) printf("%d ",n)
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d ",n)
#define bitget(n) __builtin_popcountll(n)
ll dx[] = {1,1,0,-1,-1,-1,0,1};
ll dy[] = {0,-1,-1,-1,0,1,1,1};
ll dxx[] = {1,-1,0,0};
ll dyy[] = {0,0,-1,1};
ll modexpo(ll x,ll y){if(y==0)return 1;if(y%2){ll viky=modexpo(x,y/2);
return (((x*viky)%mod)*viky)%mod;}else{ll viky=modexpo(x,y/2);return (viky*viky)%mod;
}}
bool isvalid(ll x,ll y,ll n, ll m) { return (x>=0&&x<n&&y>=0&&y<m); }

int main() {
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll a,b,c;
    cin>>a>>b>>c;

    cout<<(a^b^c);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 2;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const ld DINF = 1e12;
const ld PI = acos(-1.0);
const ld EPS = 1e-11;

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

int n;

void dfs(vector<int> &v, int Max)
{
  int sz = v.size();
  if (sz == n)
  {
    for (auto i : v)
    {
      cout << (char)(i + 'a');
    }
    cout << "\n";
    return;
  }
  for (int i = 0; i <= Max; ++i)
  {
    v.push_back(i);
    dfs(v, Max);
    v.pop_back();
  }
  v.push_back(Max + 1);
  dfs(v, Max + 1);
  v.pop_back();
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);

  cin >> n;
  vector<int> v;
  dfs(v, -1);
  return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define rep(i,r) for (int i = 0; i < r; i++)
#define repeq(i,r) for (int i = 0; i <= r; i++)

int main() {
  int X;
  cin >> X;
  cout << X / 500 * 1000 + X % 500 / 5 * 5 << endl;
  return 0;
}


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

int main() {
  int N, M;
  cin >> N;
  vector<string> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  cin >> M;
  vector<string> B(M);
  for (int i = 0; i < M; i++) cin >> B.at(i);

  int X = 0, ans = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (A.at(i) == A.at(j)) X++;
    }
    for (int k = 0; k < M; k++) {
      if (A.at(i) == B.at(k)) X--;
    }
    ans = max(ans, X);
    X = 0;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
  int n,a[110][110],rs[110][110],sum[110][110];
  cin >> n;
  rep(i,n)rep(j,n)cin >> a[i][j];

  rep(i,n)rs[0][i] = 0;
  rep(i,n){
    rs[i+1][0] = 0;
    rep(j,n){
      rs[i+1][j+1] = rs[i+1][j] + a[i][j];
    }
  }

  rep(i,n+1){
    sum[0][i] = 0;
    rep(j,n){
      sum[j+1][i] = sum[j][i] + rs[j+1][i];
    }
  }

  int ans = -1000000000;
  rep(i,n)rep(j,n)rep(k,n+1)rep(l,n+1){
    if(i<k && j<l){
      ans = std::max(ans,sum[k][l]-sum[k][j]-sum[i][l]+sum[i][j]);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1300
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
     
using namespace std;
int main()
{
	int n , o, p , q, w;
    while(~scanf("%d", &n))
    {
    		o = n / 1000;
    		p = n / 100 - o * 10;
    		q = n / 10 - p * 10 - o * 100;
    		w = n % 10;
    		//printf("%d %d %d %d\n", o ,p , q ,w);
    		int a, b , c, d, e ,f;
    		if((o + p + q + w) == 7)
    			printf("%d+%d+%d+%d=7",o,p,q,w);
    		else if((o+p+q-w) ==7)
    			printf("%d+%d+%d-%d=7",o,p,q,w);
    		else if((o + p - q -w)==7)
    				printf("%d+%d-%d-%d=7",o,p,q,w);
    		else if((o-p-q-w)==7)
    				printf("%d-%d-%d-%d=7",o,p,q,w);
    		else if((o-p-q+w)==7)
    				printf("%d-%d-%d+%d=7",o,p,q,w);
    		else if((o-p+q+w)==7)
    				printf("%d-%d+%d+%d=7",o,p,q,w);
    		else if((o-p+q-w)==7)
    				printf("%d-%d+%d-%d=7",o,p,q,w);
    		else if((o+p-q+w)==7)
    				printf("%d+%d-%d+%d=7",o,p,q,w);
     
    	}
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;
 
 
int main() {
    int n, k, min = 1e9 + 1;
    cin >> n >> k;
    vector<int>as(n);
    for (int i = 0; i < n; i++){
        cin >> as[i];
    }
    sort (as.begin(), as.end());
    for (int i = 0; i < n - k + 1; i++){
        if(as[i + k - 1] - as[i] < min){
            min = as[i + k - 1] - as[i];
        }
    }
    cout << min << endl;
}

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

typedef struct{
	long long nr,dr;
} Frac;


long long gcd(long long a,long long b){
	if(a % b == 0){
		return b;
	}
	return gcd(b,a%b);
}
long long lcm(long long a,long long b){
	long long g = gcd(a,b);
	return a / g * b;
}

Frac lcm_f(Frac f1,Frac f2){
	long long cdr = lcm(f1.dr,f2.dr);
	long long f1t = cdr / f1.dr;
	long long f2t = cdr / f2.dr;
	long long f1n = f1.nr * f1t;
	long long f2n = f2.nr * f2t;
	long long cnr = lcm(f1n,f2n);
	long long g = gcd(cnr,cdr);
	Frac ret;
	ret.nr = cnr / g;
	ret.dr = cdr / g;
	return ret;
}

long long cal(Frac fr,long long d,long long v){
	return fr.nr * v / fr.dr / d;
}

int main(){
	long long n;
	long long d[11],v[11];
	Frac f[11];
	while(cin >> n,n!=0){
		for(long long i = 0; i < n; i++){
			cin >> d[i] >> v[i];
			f[i].nr = d[i];
			f[i].dr = v[i];
		}
		for(long long i = 1; i < n; i++){
			f[i] = lcm_f(f[i-1],f[i]);
		}
		for(long long i = 0; i < n; i++){
			cout << cal(f[n-1],d[i],v[i]) << endl;
		}
	}
	return 0;
}



Measured memory_bytes: 2992
#include <stdio.h>
#include <math.h>
#define MAX 1000000
int main(){
    int i,j,ch[1000000],max;

    max=sqrt(MAX);

    for(i=0;i<MAX;i+=2){ch[i]=0;ch[i+1]=1;}

    ch[1]=0;
    ch[2]=1;

    for(i=3;i<max;i+=2) if(ch[i]) for(j=i+i;j<MAX;j+=i) ch[j]=0;

    for(i=3;i<MAX;i++) ch[i]+=ch[i-1];

    while(scanf("%d",&i)!=EOF) printf("%d\n",ch[i]);

    return 0;
}

Measured memory_bytes: 4500
#include<cstdio>
#include<algorithm>


#define INF 1e13
#define NMAX 1005
#define MMAX 2005 

typedef long long ll;

using namespace std;

int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	int a[MMAX],b[MMAX],c[MMAX];
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&a[i],&b[i],&c[i]);
	}
	ll max[NMAX];
	for(int i=1;i<=n;i++){
		max[i]=-INF;//从1出发到所有点的最长路径 
	} 
	max[1]=0;//1号点到一号点距离为0
	for(int i=1;i<=n;i++){//找最长路径 
		for(int j=1;j<=m;j++){
			if(a[j]==INF) continue;//不能到达这个起点，就跳过
			if(max[b[j]]<max[a[j]]+c[j]){//如果从a【j】出发到b【j】距离更长，就更新 
				max[b[j]]=max[a[j]]+c[j]; 
			} 
		} 
	}
	ll ans=max[n];//已经找到最大值，看有没有回路
	bool loop[NMAX]={0};
	for(int i=1;i<=n;i++){//找回路 
		for(int j=1;j<=m;j++){
			if(a[j]==INF) continue;//不能到达这个起点，就跳过
			if(max[b[j]]<max[a[j]]+c[j]){//如果从a【j】出发到b【j】距离还可以更长，说明有回路 
				loop[b[j]]=1;
			} 
			if(loop[a[j]]){//起点有回路，终点也有回路 
				loop[b[j]]=1;
			} 
		} 
	}
	if(loop[n]){
		printf("inf");
	} 
	else printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long int
#define v vector<ll>
#define vv vector<v>
ll MOD=1e9+7;
ll n,m;
ll LIM=1e5+10;
vv adj(LIM);
v down(LIM,1);
v ans(LIM,1);
vv children(LIM);
void dfs(ll n,ll par)
{
	for (ll i=0; i<adj[n].size(); i++)
	{
		if (adj[n][i]!=par)
		{
			children[n].push_back(adj[n][i]);
			dfs(adj[n][i],n);
			down[n]=(down[n]*(1+down[adj[n][i]]))%m;
		}
	}
}
void dfs2(ll n,ll par, ll up)
{
	ans[n]=(down[n]*(1+up))%m;
	ll k=(int)(children[n].size());
	if (k==0)
		return;
	v left(k,1),right(k,1);
	right[k-1]=(1+down[children[n][k-1]]);
	left[0]=(1+down[children[n][0]]);
	for (ll i=1; i<k; i++)
		left[i]=(left[i-1]*(1+down[children[n][i]]))%m;
	for (ll i=k-2; i>=0; i--)
		right[i]=(right[i+1]*(1+down[children[n][i]]))%m;
	for (ll i=0; i<children[n].size(); i++)
	{
			ll temp;
			if (i==0 && i==k-1)
				temp=1;
			else if (i==0)
				temp=right[i+1];
			else if (i==k-1)
				temp=left[i-1];
			else
				temp=(left[i-1]*right[i+1])%m;
			temp=(temp*(1+up))%m;
			dfs2(children[n][i],n,temp);
	}
}
int main() 
{ 
	cin>>n>>m;
	for (ll i=1; i<n; i++)
	{
		ll a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1,1);
	dfs2(1,1,0);
	for (int i=1; i<=n; i++)
		cout<<ans[i]<<endl;
    return 0;
} 

Measured memory_bytes: 23680
#include<cstdio>
#include<cctype>


int main(){
	char ch;
	while(1){
	scanf("%c",&ch);
	if(isalpha(ch)){
		if(islower(ch)) printf("%c",toupper(ch));
		else printf("%c",tolower(ch));
	}
	else printf("%c",ch);
	if(ch==  '\n') break;
	}
  return 0;
}


Measured memory_bytes: 2608
#pragma region header
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#include <cstring>
#include <array>
// ===============================================================
//using系
#pragma region header
using namespace std;
using ll = long long;
using lint = long long;
using ld = long double;
using ulint = unsigned long long;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
constexpr lint mod = 1000000007;
constexpr long double pi = 3.141592653589793238462643383279;
#pragma endregion
// ========================================================================
//define
#define INF (lint)10000000000000000
#define mod = (int)1000000007;
#pragma endregion
int n, m;
vector<vector<int>> v;
bool h[100005];
int ans[100005];

void input() {
	cin >> n >> m;
	v.resize(n + 5);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	return;
}
void solve() {
	queue<int> q;
	q.push(1);
	h[1] = 1;
	while (!q.empty()) {
		int s = q.front();
		q.pop();
		for (int i : v[s]) {
			if (!h[i]) {
				ans[i] = s;
				h[i] = 1;
				q.push(i);
			}
		}
	}
	return;
}

int main(void) {
	input();
	solve();
	printf("Yes\n");
	for (int i = 2; i <= n; i++) {
		printf("%d\n", ans[i]);
	}

	return 0;
}

Measured memory_bytes: 10324
package main

import "fmt"

func main() {
	var s int
	fmt.Scan(&s)
	seen := map[int]bool{s: true}
	for i := 2; true; i++ {
		next := f(s)
		if seen[next] {
			fmt.Println(i)
			return
		}
		s, seen[next] = next, true
	}
}

func f(i int) int {
	if i&1 == 0 {
		return i >> 1
	}
	return 3*i + 1
}


Measured memory_bytes: 1852
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		double p = 0;

		if(N < K) {

			for(int i=1;i<=N;i++) {
				if(K%i == 0 && ispow2(K/i)) {
					p += Math.pow(2, -1*((int)(log2(K/i))));
				}else {
					p += Math.pow(2, -1*((int)(log2(K/i) + 1)));
				}
			}

			p /= N;
		}else {
			for(int i=1;i<K;i++) {
				if(K%i == 0 && ispow2(K/i)) {
					p += Math.pow(2, -1*((int)(log2(K/i))));
				}else {
					p += Math.pow(2, -1*((int)(log2(K/i) + 1)));
				}
			}
			p /= N;

			p += (double)(N-K+1)/(double)N;
		}
		System.out.println(p);
	}

	public static boolean ispow2(int a) {
		int x = a & (a-1);
		if(x == 0) {
			return true;
		}else {
			return false;
		}
	}

	public static double log2(double a) {
		return Math.log(a)/Math.log(2);
	}
}


Measured memory_bytes: 20692
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int x = sc.nextInt();
        StringJoiner sj = new StringJoiner(" ");
        for (int i = x - k + 1; i <= x + k - 1; i++) {
            sj.add(String.valueOf(i));
        }
        System.out.println(sj.toString());
    }

}


Measured memory_bytes: 21844
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<utility>
#include<map>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K
#define INF 1e18
#define MOD 100000007
#define SIZE 100005
#define PI 	3.14159265358979323846

int N,M;
pair<ll,pair<int,int>> PY_set[100100];
//作成年(ll)→M市に位置→入力順
pair<int,int> PY_ans[100100];
int country[100100] = {0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    REP(i,M){
        cin >> PY_set[i].second.first >> PY_set[i].first;
        PY_set[i].second.second = i;
    }
    sort(PY_set,PY_set+M);//作成年順にソート
    REP(i,M){
        country[PY_set[i].second.first]++;
        PY_ans[PY_set[i].second.second].first = PY_set[i].second.first;
        PY_ans[PY_set[i].second.second].second = country[PY_set[i].second.first];
    }
    REP(i,M){
        printf("%06d%06d\n",PY_ans[i].first,PY_ans[i].second);
    }
    return 0;
}

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

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

Measured memory_bytes: 3924
import java.util.Scanner;
class Main {
	public void watch() {
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int h = S / 60 / 60;
		int m = (S - h * 60 * 60) / 60;
		int s = S - (h * 60 * 60 + m * 60);
		System.out.println(h + ":" + m + ":" + s);
	}
	public static void main(String[] args) {
		new Main().watch();
	}
}

Measured memory_bytes: 17360
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
int main(){
    ll n,k;cin>>n>>k;
    vl a(n);rep(i,n) cin>>a[i];
    sort(a.rbegin(),a.rend());
    ll mx=a[0];
    ll g=a[0];
    rep(i,n){
        g=gcd(g,a[i]);
    }
    cout<<((k%g==0&&k<=mx)?"POSSIBLE":"IMPOSSIBLE")<<endl;
    return 0;
}

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

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> cnt(m, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        int x;
        std::cin >> x;
        --x;
        ++cnt[x][i];
    }

    for (auto& v : cnt) {
        for (int i = 1; i <= n; ++i) {
            v[i] += v[i - 1];
        }
    }

    std::vector<int> dp(1 << m, n);
    dp[0] = 0;
    for (int b = 0; b < (1 << m); ++b) {
        int l = 0;
        for (int i = 0; i < m; ++i) {
            if ((b >> i) & 1) l += cnt[i].back();
        }
        for (int i = 0; i < m; ++i) {
            if ((b >> i) & 1) continue;
            int r = l + cnt[i].back();
            int d = cnt[i].back() - (cnt[i][r] - cnt[i][l]);
            dp[b | (1 << i)] = std::min(dp[b | (1 << i)], dp[b] + d);
        }
    }

    std::cout << dp.back() << std::endl;
}

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

    solve();

    return 0;
}



Measured memory_bytes: 14840
N = int(input())
S = []
for i in range(N):
  Ss = input()
  S.append(Ss)
r = 0
for i in range(N):
  T = S[i:]+S[:i]
  ok = True
  for i in range(N):
    for j in range(i+1, N):
      if T[i][j] != T[j][i]:
        ok = False
        break
  if ok:
    r += 1
r *= N
print(r)


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

using namespace std;

#define MAX_N 101

int a[MAX_N];

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-1; j++) {
                if (a[j] > a[j+1]) {
                    swap(a[j], a[j+1]);
                    count++;
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}

Measured memory_bytes: 0
N = int(input())
S = input()
S = S[-1] + S + S[0]

# sheep:1, wolf:0
isOK = False
for x, y in [(1, 1), (1, 0), (0, 1), (0, 0)]:
    A = [-1] * len(S)
    A[0] = x
    A[1] = y
    for i in range(1, len(S)-1):
        if A[i]:  # 羊の場合
            A[i + 1] = A[i - 1] if S[i] == "o" else 1 - A[i - 1]
        else:  # 狼の場合
            A[i + 1] = A[i - 1] if S[i] == "x" else 1 - A[i - 1]

    if A[0] == A[-2] and A[1] == A[-1]:
        isOK = True
        break

if isOK:
    ans = ["S" if i else "W" for i in A[1:-1]]
    ans = "".join(ans)
else:
    ans = -1

print(ans)


Measured memory_bytes: 5716
package main

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

func main() {
	buf := make([]byte, 0)
	scanner.Buffer(buf, 100000)

	s := getString()
	s = reverse(s)

	ans := "YES"
L:
	for i := 0; i < len(s); {
		switch {
		case len(s)-i >= 5 && (s[i:i+5] == "maerd" || s[i:i+5] == "esare"):
			i += 5
		case len(s)-i >= 6 && s[i:i+6] == "resare":
			i += 6
		case len(s)-i >= 7 && s[i:i+7] == "remaerd":
			i += 7
		default:
			ans = "NO"
			break L
		}
	}

	fmt.Println(ans)
}

func reverse(s string) string {
	rs := []rune(s)
	n := len(rs)

	for i := 0; i < n/2; i++ {
		rs[i], rs[n-i-1] = rs[n-i-1], rs[i]
	}

	return string(rs)
}

// -----------------------------------------

var scanner = wordScanner()

func wordScanner() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}

func getInt() int {
	scanner.Scan()
	i, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	scanner.Scan()
	s := scanner.Text()
	return s
}


Measured memory_bytes: 1408
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>   
#include <stdio.h>    
 
using namespace std;
     
#define F first
#define S second
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)2e5 + 123;
const ll inf = (ll)3e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-10;
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n;
ld x[N], y[N];
char d[N];

inline ld f (ld c) {
   ld mx_x = -inf, mx_y = -inf, mn_x = inf, mn_y = inf;
   for (int i = 1; i <= n; i ++) {
      if (d[i] == 'D') {
         ld val = y[i] - c;
         if (mx_y < val) mx_y = val;
         if (mn_y > val) mn_y = val;
         if (mx_x < x[i]) mx_x = x[i];
         if (mn_x > x[i]) mn_x = x[i];
      }  
      if (d[i] == 'U') {
         ld val = y[i] + c;
         if (mx_y < val) mx_y = val;
         if (mn_y > val) mn_y = val;
         if (mx_x < x[i]) mx_x = x[i];
         if (mn_x > x[i]) mn_x = x[i];
      }
      if (d[i] == 'R') {
         ld val = x[i] + c;
         if (mx_x < val) mx_x = val;
         if (mn_x > val) mn_x = val;
         if (mx_y < y[i]) mx_y = y[i];
         if (mn_y > y[i]) mn_y = y[i];
      }
      if (d[i] == 'L') {
         ld val = x[i] - c;
         if (mx_x < val) mx_x = val;
         if (mn_x > val) mn_x = val;
         if (mx_y < y[i]) mx_y = y[i];
         if (mn_y > y[i]) mn_y = y[i];
      }
   }
   return (mx_x - mn_x) * (mx_y - mn_y);
}

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n;
   for (int i = 1; i <= n; i ++) cin >> x[i] >> y[i] >> d[i];
   ld l = 0.0, r = 100000000.0;
   ld ans;
   for (int it = 0; it <= 400; it ++) {
      ld h = (r - l) / 3.0;
      ld m1 = l + h;
      ld m2 = m1 + h; 
      ld M1 = f (m1), M2 = f (m2);
      if (M1 < M2) r = m2, ans = M1;
      else l = m1, ans = M2;
   }
   cout << fixed << setprecision (9) << ans;
}                                     

main () {                                       
// freopen (".in", "r", stdin);    
// frexopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
// cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}


Measured memory_bytes: 6016
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int i = (m); (i) < (n); (i)++)
typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<ll> ms(N + 1), hero(N);
    rep(i, N + 1) cin >> ms[i];
    rep(i, N) cin >> hero[i];
    ll res = 0;
    rep(i, N) {
        ll a = min(ms[i], hero[i]);
        ms[i] -= a;
        hero[i] -= a;
        ll b = min(ms[i + 1], hero[i]);
        ms[i + 1] -= b;
        hero[i] -= b;
        res += a + b;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;

typedef pair<int, int> P;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

int D[31][39];
int cnt[3][31];
int main() {
	int N, C;

	
	ll cost = INF;
	cin >> N >> C;
	REP(i,C) {
		REP(j,C) {
			cin >> D[i][j];
		}
	}
	REP(i, N) {
		REP(j, N) {
			int c;
			cin >> c;
			if ((i + j) % 3 == 0)cnt[0][c - 1] += 1;
			if ((i + j) % 3 == 1)cnt[1][c - 1] += 1;
			if ((i + j) % 3 == 2)cnt[2][c - 1] += 1;
		}
	}


	for (int i = 0; i < C; i++) {
		for (int j = 0; j < C; j++) {
			if(i!=j)for (int k = 0; k < C; k++) if(i!=k&&j!=k){
				ll cost2 = 0;
				REP(l, 3) {
					REP(m,C) {
						if (l == 0)cost2 += cnt[0][m] * D[m][i];
						if (l == 1)cost2 += cnt[1][m] * D[m][j];
						if (l == 2)cost2 += cnt[2][m] * D[m][k];
					}
				}
				if (cost2 < cost)cost = cost2;
			}
		}
	}
	cout << cost << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
     
     
typedef long long ll;
typedef vector <int> vi;
typedef pair <int,int> pi;
typedef tuple <int,int,int> ti;

#define forn(i,a,n) for(int i = a; i < n ; i++)
#define mem(str,a) memset(str, a, sizeof(str));
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(nullptr)
const int MOD = 1e9+7, N = 1e7 + 10, E = 1e-9;
/*
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//vector <int> show;
//for (auto x : show)
//   cout << x << " ";
getline(cin,s);


*/

int main() {
    int a,b;
    cin >> a >> b;
    if(a == 1 || b == 1) {
        if(a > b)
            cout << "Bob" << endl;
        else if(a < b)
            cout << "Alice" << endl;
        else
            cout << "Draw" << endl;
    }
    else{
        if(a > b)
            cout << "Alice" << endl;
        else if(a<b)
            cout << "Bob" << endl;
        else
            cout << "Draw" << endl;
    }
    return 0;
}


Measured memory_bytes: 384
n = int(input())
z = 1000000000
 
if n==z*z:
	print(z, 0, 0, z, 0, 0)
elif n > z:
    a = n//z
    b = n%z
    print(a+1, b, 0, z, 1, 0)
else:
    print(n, 0, 1, 1, 0, 0)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 30;
const double EPS = 1e-10;
const double pi = 3.14159265359;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

int w, h, n;
int l = -1, r = 111, u = 111, d = -1;

int main()
{
	cin >> w >> h >> n;
	l = 0, r = w, u = h, d = 0;
	for (int i = 0;i < n;i++) {
		int x, y, a;
		cin >> x >> y >> a;
		if (a == 1)	l = max(l, x);
		if (a == 2)	r = min(r, x);
		if (a == 3)	d = max(d, y);
		if (a == 4)	u = min(u, y);
	}
	if (r < l) {
		cout << 0 << endl;
	}
	else if (u < d) {
		cout << 0 << endl;
	}
	else {
		cout << (r - l) * (u - d) << endl;
	}

	return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//3人1チームで、2番目に強い人の強さがチームの強さ
//3N人をNチームに分け、強さの和のmaxを求める
//aをでかい順に並べ、一個おきに足していく　N回
int main(){
  int N;
  cin >> N;
  vector<int> num(101);//num[i]はiがいくつあるか
  vector<int> d(N);

  rep(i,N){
    cin >> d[i];
  }
for(int i =1 ;i<=100;i++){
  int c = 0;//配列dの中のiの個数
  for(int j = 0;j<N;j++){
    if(d[j] == i) c++;
  }
  num[i] = c;
}
  int ans  =0;
  rep(i,101){
    if(num[i] != 0) ans++;
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<functional>
#include<iterator>
#include<complex>
#include<fstream>
#include<random>
#include<ctype.h>
#include<stdio.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using PII = pair<ll, ll>;
using piii = pair<pii, pii>;
using Pi = pair<int, pii>;
using Graph = vector<vector<int>>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
bool check(int x, int y) {
	if (0 <= x && x<55 && 0 <= y && y<55)return true;
	else return false;
}
const ll INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;

//iの逆元mod inf
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const double PI = 3.14159265358979323846;
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
double Euclidean_distance(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//素因数分解
map<int, int>prime_factor(int n) {
	map<int, int>res;
	for (int i = 2; i*i <= n; ++i) {
		while (n%i == 0) {
			++res[i];
			n /= i;
		}
	}
	if (n != 1)res[n] = 1;
	return res;
}


ll powmod(ll a, ll k, ll mod) {
	ll ap = a, ans = 1;
	while (k) {
		if (k & 1) {
			ans *= ap;
			ans %= mod;
		}
		ap = ap * ap;
		ap %= mod;
		k >>= 1;
	}
	return ans;
}
ll invi(ll a, ll mod) {
	return powmod(a, mod - 2, mod);
}
#define PI 3.14159265358979323846  // 円周率
//逆元Aを足したときのmodで割った余りは
//+=invi(A)
//Yで割ることはY^(10^9+7)-2を掛けることは同値
///////////////////////////////////////
bool is_prime(int n) {
	for (int i = 2; i*i <= n; ++i) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


int main() {
	for (int i = 0; i < 5; ++i) {
		int k; cin >> k;
		if (k == 0) {
			cout << i + 1 << endl;
		}
	}
	return 0;
}


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

int isprime(int n);

int main()
{
	int i,n,ans;

	while(cin >> n){
		if(!n) break;
		for(i=n; i-2>2; i--){
			if(isprime(i) && isprime(i-2)){
				ans=i;
				break;
			}
		}

		cout << ans-2 << " " << ans << "\n";
	}

	return 0;
}

int isprime(int n)
{
	for(int i=2; i*i<=n; i++)
		if(n%i==0) return 0;
	return 1;
}

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

int q;

int main() {
    cin >> q;
    llong b, x;
    cin >> x >> x >> b;
    priority_queue<llong> small;
    priority_queue<llong, vector<llong>, greater<llong>> large;
    small.push(x);
    llong sum_small = x, sum_large = 0;
    for (int z = 1; z < q; z++) {
        int type;
        cin >> type;
        if (type == 1) {
            int ta, tb;
            cin >> ta >> tb;
            b += tb;
            if (ta < small.top()) {
                sum_small += ta;
                small.push(ta);
                if (small.size() > large.size() + 1) {
                    sum_large += small.top();
                    sum_small -= small.top();
                    large.push(small.top());
                    small.pop();
                }
            } else {
                sum_large += ta;
                large.push(ta);
                if (small.size() < large.size()) {
                    sum_small += large.top();
                    sum_large -= large.top();
                    small.push(large.top());
                    large.pop();
                }
            }
        } else {
            llong ans = 0;
            ans += (llong)small.top() * (llong)small.size() - sum_small;
            ans += sum_large - (llong)small.top() * (llong)large.size();
            ans += b;
            cout << small.top() << " " << ans << endl;
        }
    }
}

Measured memory_bytes: 3828
n = int(input())
a = list(map(int,(input().split())))
b = list(map(int,(input().split())))
c = list(map(int,(input().split())))

score = 0
for i in range(n):
  score += b[a[i]-1]
  
  if (i != 0) and a[i] == a[i-1] + 1:
    score += c[a[i]-2]
#    print ('DEBUG ' + str(score) + ' : ' + str(c[i-1]) + ' : ' + str(i))
  
print(score)

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

#define pb push_back
#define mp make_pair
#define F(i, a, n, b) for(int i=a;i<n;i+=b)
#define REVF(i, a, b, c) for(int i=a;i>=b;i-=c)
#define REP(i, n) F(i, 0, n, 1)
#define REP1(i, n) F(i, 1, n+1, 1)
#define REV(i, n) REVF(i, n, 0, 1)
#define PTR(it, x) for(auto it=x.begin();it!=x.end();++it)
#define MOD 1000000007

typedef long long ll;

const int MAX = 1e6 + 5;

int n,cnt = 1;
string s;
char c;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>s;
	char c = s[0];
	REP1(i,n-1){
		if(c != s[i]){
			c = s[i];
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

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

#define int long long

signed main(){
  int n,d;
  cin >> n >> d;
  
  vector<int> v[n];
  
  for(int i = 0;i<n;i++){
    for(int j = 0;j<d;j++){
      int t;
      cin >> t;
      v[i].push_back(t);
    }
  }
  
  vector<string> s;
  
  for(int i = 0;i<n-1;i++){
    for(int j = i+1; j<n;j++){
      double cur = 0.0;
      for(int k = 0;k<d;k++){
        //cout << sqrt(pow(v[i][k]-v[j][k],2))<< endl; 
        cur+=pow(v[i][k]-v[j][k],2);
      }
      cur = sqrt(cur);          
      //cout << cur << endl;
      s.push_back(to_string(cur));
                  
    }
   }
  int ans = 0; 
   for(int i = 0;i<(int)s.size(); i++){
     int t = s[i].size();
     //cout << s[i] << endl;
     bool vis = false, flag = true;
     for(int j = 0;j<t;j++){
       if(s[i][j]=='.'){
         vis = true;
         continue;
       }
       if(vis){
         if(s[i][j]!='0')flag = false;
       }
     }
     if(flag)ans++;
   }
   cout << ans << endl;
         
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

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

	int a, b, k;
	cin >> a >> b >> k;
	for (int i = a; i < min(a + k, b + 1); i++) cout << i << "\n";
	for (int i = max(a + k, b - k + 1); i <= b; i++) cout << i << "\n";
}


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

#define int long long 

main()
{
  int n, k;
  int a[100005];
  int sum = 0;

  cin >> n >> k;
  
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    if(a[i] > 0) sum += a[i];
  }
  
  int part1 = 0, part2 = 0, minv;
  for(int i = 0; i < k; i++) {
    if(a[i] < 0) part1 -= a[i];
    else part2 += a[i];
  }
  minv = min(part1, part2);
  for(int i = k; i < n; i++) {
    if(a[i - k] < 0) part1 += a[i - k];
    else part2 -= a[i - k];
    if(a[i] < 0) part1 -= a[i];
    else part2 += a[i];
    minv = min(minv, min(part1, part2));
  }
  
  cout << sum - minv << endl;

  return (0);
}

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

short dp[3003][3003];
int main() {
  string s, t;
  cin >> s >> t;
  int ss, ts;
  ss = s.size();
  ts = t.size();
//  int dp[ss+1][ts+1];
  rep(i, ts+1) dp[0][i] = 0;
  rep(i, ss+1) dp[i][0] = 0;
  rep(i, ss) {
    rep(j, ts) {
      if ((s[i] == t[j]) && (dp[i][j] == dp[i][j+1]) && (dp[i][j] == dp[i+1][j])) {
        dp[i+1][j+1] = dp[i][j] + 1;
      } else {
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
      }
    }
  }
//  rep(i, ss+1) {rep(j, ts+1) cout << dp[i][j]; cout << endl;}
  if (dp[ss][ts] == 0) cout << "" << endl;
  else {
    string ans = "";
    for (int i = ss, j = ts; (i > 0) && (j > 0);) {
//      cout << ss-si << "," << ts-ti << endl;
      if (dp[i][j] == dp[i-1][j]) i--;
      else if (dp[i][j] == dp[i][j-1]) j--;
      else {ans = t[j-1] + ans; j--;}
    }
    cout << ans << endl;
  }
}


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


void solve(long long N){
    while(N/1000 != 0){
        //cout << N << endl;
        N = N % 1000;
    }
    if(N == 0) cout << N << endl;
    else cout << 1000 - N << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    ll a[3];rep(i,3)cin>>a[i];
    sort(a,a+3);
    co(a[0]*a[1]*(a[2]%2));
}

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

using namespace std;

int h, m, s;
void solve(int v)
{
  h = v/3600, m = (v%3600)/60, s = (v%3600)%60;
  printf("%02d:%02d:%02d\n", h, m, s);

  return ;
}

int main()
{
  while(cin>>h>>m>>s && (h+m+s) != -3){
    int t = 7200 - ((h*60+m)*60+s);
    solve(t);
    solve(t*3);
  }

  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9+7
int main()
{
	int n,k;
	cin>>n>>k;
	vector<int> h;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		h.push_back(x);
	}
	vector<int> dp(n,INF);
	dp[0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<=i+k;j++)
		{
			if(j<n)
			{
				dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
			}
		}
	}
	cout<<dp[n-1];
	return 0;
}

Measured memory_bytes: 1144
# # Make IO faster
# import sys
# input = sys.stdin.readline

# # get single (or) multiple str
# X = input()

# # get single int
# N = int(input())
# # get multiple int (e.g., 2)
# X, Y = map(int, input().split())
# # get multiple int (e.g., 2) for N lines
# XY = [list(map(int, input().split())) for _ in range(N)]

# from IPython import embed; embed(); exit();

# 全部入り
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def INT(): return int(input())
N = INT()
K = INT()
X = INT()
Y = INT()

if N >= K:
    print(K * X + (N - K) * Y)
else:
    print(N * X)



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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

using PDI = pair<double, int32>;

const int64 mod = 1e9+7;

int main(void){
	int32 a, b;
	cin >> a >> b;
	if(b >= a) cout << a << endl;
	else cout << a-1 << endl;
}


Measured memory_bytes: 256
{-# LANGUAGE OverloadedStrings #-}

import qualified Data.Text as T
import qualified Data.Text.IO as T
import Control.Monad (replicateM)
import Control.Applicative ((<$>))

revise :: T.Text -> T.Text
revise = T.replace "Hoshino" "Hoshina"

main :: IO ()
main = do
    n <- readLn
    T.putStr . T.unlines =<< (replicateM n $ revise <$> T.getLine)

Measured memory_bytes: 4536
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define P 1000003
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int Q,fac[P],inv[P];
int ksm(int a,int  k)
{
	int s=1;
	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
	return s;
}
int I(int a){return ksm(a,P-2);}
signed main()
{
	Q=read();
	fac[0]=1;for (int i=1;i<P;i++) fac[i]=1ll*fac[i-1]*i%P;
	inv[0]=inv[1]=1;for (int i=2;i<P;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;
	for (int i=2;i<P;i++) inv[i]=1ll*inv[i-1]*inv[i]%P;
	while (Q--)
	{
		int x=read(),d=read(),n=read();
		if (d==0) {printf("%d\n",ksm(x,n));continue;}
		x=1ll*x*I(d)%P;
		if (x+n-1>=P) printf("%d\n",0);
		else printf("%d\n",1ll*fac[x+n-1]*(x==0?1:inv[x-1])%P*ksm(d,n)%P);
	}
	return 0;
	//NOTICE LONG LONG!!!!!
} 

Measured memory_bytes: 8704
#include "bits/stdc++.h"

#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
using ull = unsigned long long;
using ll = long long;

struct __INIT {
    __INIT() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __init;

int main() {
    ull N, M;
    cin >> N >> M;
    ll sum = 0;
    if(M == 1){
        sum = 0;
    }else if(N * 2 >= M){
        sum = M / 2;
    }else{
        sum = N;
        M -= 2 * sum;
        sum += M / 4;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = int(1e9+7)
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr
    
def f(n,a,c,K):
    now = 0
    for i in range(n):
        now += math.ceil(a[i]/c)-1
    return now <= K

def main():
    N,K = [int(x) for x in stdin.readline().rstrip().split()]
    A = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    l,r = 0,int(1e9)
    while r-l > 1:
        c = (l+r)//2
        # print(c,f(N,A,c,K))
        if f(N,A,c,K):
            r = c
        else:
            l = c
            
    print(r)
main()

Measured memory_bytes: 49444
import java.util.Scanner;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner((System.in));
		long n = sc.nextLong() ;
		long m = sc.nextLong();
		sc.close();
		long count = 0;
		if((n==1) || (m==1)) {
			if(n > m) {
				count = n - 2;
			}else if(m > n) {
				count = m -2;
			}else {
				count = 1;
			}
		}else {
			count = (n-2)*(m-2);
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 23764
first = true
until (n = gets.to_i) == 0
  result = {}
  n.times do
    team, win, lose, draw = gets.split
    result[team] = win.to_i * 3 + draw.to_i
  end
  i = 0
  puts unless first
  result.sort_by {|k, v| [-v, i += 1]}.each {|item| puts item.join(",")}
  first = false
end

Measured memory_bytes: 8700
#include <iostream>

using namespace std;

int main()
{

    string firstType, secondType, chosenType;
    int firstTypeNumber, secondTypeNumber;

    cin >> firstType >> secondType >> firstTypeNumber
    >> secondTypeNumber >> chosenType;

    if (chosenType == firstType){
        firstTypeNumber--;
    }

    else{
        secondTypeNumber--;
    }

    cout << firstTypeNumber << " " << secondTypeNumber;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
int main(){
  int a,b;
  int temp;
  int i;
  int gcd,lcm;
  int64 A,B;
  while(scanf("%d %d",&a,&b) != EOF){
    A = a;
    B = b;
    while(b != 0){
      temp = a % b;
      a = b;
      b = temp;
    }
    gcd = a;
    lcm = (A * B) / gcd;
    cout << gcd << " " <<  lcm << endl;
  }
}

Measured memory_bytes: 1208
# ABC137B - One Clue
def main():
    K, X = tuple(map(int, input().rstrip().split()))
    mi, ma = max(-1000000, X - K + 1), min(1000000, X + K - 1)
    ans = [i for i in range(mi, ma + 1)]
    print(*ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060