akhauriyash/Code-Regression huggingface dataset:
// AOJ DPL_4_B Coin Combination Problem II
// 2018.5.10 bal4u
 
#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
 
int in()
{
    int n = 0, c = gc();
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}

long long inLL()
{
    long long n = 0, c = gc();
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}

#define MAX  ((1<<20)+5)

long long a[42]; int w;
long long s1[42][MAX]; int w1[42];
long long s2[42][MAX]; int w2[42];

int binarysearch_upper(long long *a, long long x, int r)
{
	int m, l = 0;

    while (l < r) {
        m = (l+r) >> 1;
		if (a[m] == x) return m+1;
		if (a[m] < x) l = m + 1; else r = m;
    }
	return l;
}

int binarysearch_lower(long long *a, long long x, int r)
{
	int m, l = 0;

    while (l < r) {
        m = (l+r) >> 1;
        if (a[m] < x) l = m + 1; else r = m;
    }
	return l;
}

int cmp(long long *a, long long *b)
{
	if (*a < *b) return -1;
	return (*a != *b);
}

long long combi(int n, int k)
{
	long long ans;

	if (s1[n][k]) return s1[n][k];
	if ((k << 1) > n) k = n-k;
	if (k == 0) ans = 1;
	else if (k == 1) ans = n;
	else ans = combi(n-1, k) + combi(n-1, k-1);
	return s1[n][k] = ans;
}

int main()
{
	int N, K, i, j, k, m1, m2, n, lim;
	long long L, R, x, y, ans;

	N = in(), K = in(), L = inLL(), R = inLL();

	w = 0;
	x = y = inLL(); if (y + K-1 <= R) a[w++] = y;
	for (i = 1; i < N; i++) {
		x = inLL();
		if (x != y) y = 0;
		if (x + K-1 <= R) a[w++] = x;
	}

	// identical a[i]
	if (x == y) {
		if (w >= K && (y = x*K) >= L && y <= R) printf("%lld\n", combi(w, K));
		else puts("0");
		return 0;
	}

	m1 = w-20;
	if (m1 < 1) m1 = 1;
	lim = 1 << m1;
	for (i = 0; i < lim; i++) {
		x = 0, n = 0;
		for (j = 0; ; j++) {
			if (j == m1) { s1[n][w1[n]++] = x; break; }
			if ((i >> j) & 1) {
				x += a[j];
				if (++n > K) break;
			}
		}
	}

	m2 = w - m1;
	lim = 1 << m2;
		for (i = 0; i < lim; i++) {
		x = 0, n = 0;
		for (j = 0; ; j++) {
			if (j == m2) { s2[n][w2[n]++] = x; break; }
			if ((i >> j) & 1) {
				x += a[j+m1];
				if (++n > K) break;
			}
		}
	}

	for (i = 0; i <= K; i++) qsort(s2[i], w2[i], sizeof(long long), cmp);

	ans = 0;
	for (i = 0; i <= K; i++) {
		k = K-i;
		for (j = 0; j < w1[i]; j++) {
			y = R-s1[i][j];
			if (y >= 0) {
				ans += (long long)binarysearch_upper(s2[k], y, w2[k]);
				x = L-s1[i][j];
				if (x > 0) ans -= (long long)binarysearch_lower(s2[k], x, w2[k]);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 19712
#include <iostream>
#include <set>
#include <vector>
#include <string.h>

using namespace std;

struct expr{
	set<int> num;
	char ope;
	vector<expr> exp;
	expr(){
		ope = 0;
	}
};

void print(expr e, int deep){
//	cout << "info: " << e.num.size() << " " << e.ope << " " << e.exp.size() << endl;
	if( e.num.empty() ){
		for(int i=0; i<e.exp.size(); i++){
			print( e.exp[i], deep+1 );
		}
	}
	for(int i=0; i<deep; i++)
		cout << "  ";
	if( !e.num.empty() ){
		cout << *( e.num.begin() );
	}
	cout << e.ope << endl;
}

set<int> calc(expr e){
//	cout << "calc" << endl;
//	print(e,0);
	set<int> result;
	if( e.exp.size() == 0 ){
		result = e.num;
	}else if( e.exp.size() == 1 ){
		result = calc( e.exp[0] );
	}else if( e.exp.size() == 2 ){
		set<int> t[2];
		t[0] = calc( e.exp[0] );
		t[1] = calc( e.exp[1] );
		for(set<int>::iterator it0 = t[0].begin(); it0 != t[0].end(); it0++){
			for(set<int>::iterator it1 = t[1].begin(); it1 != t[1].end(); it1++){
				switch( e.exp[0].ope ){
				case '+':
					result.insert( *it0 + *it1 );
					break;
				case '-':
					result.insert( *it0 - *it1 );
					break;
				case '*':
					result.insert( *it0 * *it1 );
					break;
				case '/':
					if( *it1 != 0 )
						result.insert( *it0 / *it1 );
					break;
				}
			}
		}
	}else{
		char b_ope = 0;
		expr tmp, t;
		tmp.exp.push_back(t);
		tmp.exp.push_back(t);
		tmp.exp[1].ope = 'e';
		tmp.exp[1].exp = e.exp;
		for(int i=0; i<e.exp.size()-1; i++){
			if( !tmp.exp[0].exp.empty() )
				tmp.exp[0].exp.back().ope = b_ope;
			tmp.exp[0].exp.push_back( e.exp[i] );
			b_ope = tmp.exp[0].exp.back().ope;
			tmp.exp[0].exp.back().ope = 'e';
			tmp.exp[0].ope = e.exp[i].ope;
			tmp.exp[1].exp.erase( tmp.exp[1].exp.begin() );
			set<int> rt = calc( tmp );
			for(set<int>::iterator it = rt.begin(); it != rt.end(); it++){
				result.insert( *it );
			}
		}
	}
//	cout << "result : " << result.size() << endl;
	return result;
}

expr *getexpr(expr *root, int deep){
	expr *pe = root;
	for(int k=0; k<=deep; k++){
		if( pe->exp.empty() || pe->exp.back().ope != 0 ){
			expr ex;
			pe->exp.push_back( ex );
		}
		pe = &( pe->exp.back() );
	}
	return pe;
}

void solve(char str[205]){
	struct expr exp;
	int tmp=0, deep=0;
	bool num_f=false;
	
	str[ strlen(str)+1 ] = '\0';
	str[ strlen(str) ] = 'e';
	for(int i=0; str[i] != '\0'; i++){
		if( str[i] >= '0' && str[i] <= '9' ){
			tmp = tmp * 10 + ( str[i]-'0' );
			num_f = true;
			continue;
		}
		if( num_f ){
			getexpr(&exp,deep)->num.insert( tmp );
			tmp = 0;
			num_f = false;
		}
		if( str[i] == '(' ){
			deep++;
		}else if( str[i] == ')' ){
			getexpr(&exp,deep)->ope = 'e';
			deep--;
		}else{
			// 演算子登録
			getexpr(&exp,deep)->ope = str[i];
		}
	}

//	print( exp, 0 );

	set<int> ans = calc( exp );
//	for(set<int>::iterator it = ans.begin(); it != ans.end(); it++){
//		cout << *it << " ";
//	}

	cout << ans.size() << endl;
}

int main(){
	char str[205];
	while(1){
		cin >> str;
		if( str[0] == '#' )
			break;
		solve(str);
	}
	return 0;
}

Measured memory_bytes: 1308
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef struct {
	int h = 0;
	int w = 0;
}rectangle;

int main() {
	rectangle rect[12000];
	rect[0].h = 1, rect[0].w = 2;
	int cnt = 0;
	for (int i = 1; i < 150; ++i) {
		for (int j = i + 1; j < 150; ++j) {
			int k;
			for (k = cnt; k > 0; --k) {
				if ((i * i + j * j) < (pow(rect[k - 1].w, 2) + pow(rect[k - 1].h, 2))) rect[k] = rect[k - 1];
				else {
					rect[k].h = i, rect[k].w = j;
					break;
				}
			}
			cnt++;
		}
	}
	
	int x, y;
	while (cin >> x >> y && (x || y)) {
		int num = 0;
		while (!(rect[num].h == x && rect[num].w == y))num++;
		cout << rect[num + 1].h << " " << rect[num + 1].w << endl;
	}


	return 0;
}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  	cin>>n;
  vector<int >cord(n,0);
  for(int i=0;i<n;i++)cin>>cord[i];
  int mini=1000000000;
  for(int i=1;i<=100;i++){
  	int dist = 0;
    for(int j=0;j<n;j++){
    	dist+=(i-cord[j])*(i-cord[j]);
    }
    mini = min(mini,dist);
  }
  cout<<mini;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
 
#define int long long
#define ll long long 
#define F first
#define sqr(x) ((x) * (x))
#define S second
#define make make_pair
#define pb push_back
#define sz(x) (ll)(x.size()) 
#define all(x) x.begin (), x.end ()

using namespace std;
                        
typedef unsigned long long ull;
typedef long double ld;

const int MOD = (int)1e9 + 7;
const int N = (int)2e6+ 222;
const ll INF = (ll)1e18;
const double eps = (double)1e-6;

void solve () {
	int x, y;
	cin >> x >> y;
	int ans = 0;
	if (x == y && x == 1) {
		cout << 1000000;
		return;		
	}
	if (x == 1) ans += 300000;
	if (x == 2) ans += 200000;
	if (x == 3) ans += 100000;
	if (y == 1) ans += 300000;
	if (y == 2) ans += 200000;
	if (y == 3) ans += 100000;
	cout << ans;	
}

signed main () {
    #ifdef Maga
        //freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);                                              
    int t = 1;
    while (t --) {
    	solve ();
    }
    return 0;
}





Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        
        int res=0;
        for(int i=0;i<n;i++) {
            int l=sc.nextInt();
            int r=sc.nextInt();
            res += r-l + 1;
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 25704
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;


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




int main() {
    ll N ,K;
    cin >> N >> K;
    ll ans = 0;
    FOR(k, K, N + 2) {
       ans += (N - k + 1) * k % MOD + 1;
    }
    cout << ans % MOD << endl;
}


Measured memory_bytes: 3676
import java.io.InputStream;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		String S = sc.next();

		sc.close();

		Map<String, Integer> m = new HashMap<>();
		m.put("SUN", 7);
		m.put("MON", 6);
		m.put("TUE", 5);
		m.put("WED", 4);
		m.put("THU", 3);
		m.put("FRI", 2);
		m.put("SAT", 1);

		out.println(m.get(S));

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 20692
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
//    sort(a.begin(),a.end());
    int ans=0;
    for(int i=0;i<n;i++){
        if(a[i]%2==1)ans++;
    }
    if(ans>0)cout<<"first"<<endl;
    if(ans==0) cout<<"second"<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>


long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;


int main(){

int N;
cin>>N;
int  A[N+1];
int B[N+1];
int C[N];

A[0]=1000;


for(int i=1;i<=N;i++){
    cin>>A[i];
}

for(int i=1;i<=N;i++){
    cin>>B[i];
}
C[0]=0;
for(int i=1;i<N;i++){
    cin>>C[i];
}
int before=100;
long long ans=0;
for(int i=1;i<=N;i++){
ans+=B[A[i]];
if(before+1==A[i]){
    ans+=C[before];
}
before=A[i];
}
cout<<ans<<endl;

 return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 998244353//1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000000
#define N 200005
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   char c;
   cin>>c;
   if(c>='A' && c<='Z')
    cout<<"A"<<endl;
   else
    cout<<"a"<<endl;

}


Measured memory_bytes: 3588
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


def solve():
    S = input()
    if len(S) % 2 != 0:
        print('No')
    else:
        for i in range(len(S) // 2):
            if S[2 * i:2 * i + 2] != 'hi':
                print('No')
                return
        print('Yes')


if __name__ == "__main__":
    solve()


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

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

  sort(s.begin(), s.end());  
  sort(t.begin(), t.end());  
  reverse(t.begin(), t.end());
  if (s < t)
    cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int n,m,r;
    int town[8];
    cin >> n >> m >> r;
    for(int i = 0; i < r; i++){
        cin >> town[i];
    }
    int cost[201][201] = {};
    for(int i = 0; i < 201; i++){
        for(int j = 0; j < 201; j++){
            if(i==j)cost[i][j] = 0;
            else cost[i][j] = 100000000;
        }
    }
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        cost[a][b] = cost[b][a] = c;
    }
    for(int k=1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
    sort(town,town+r);
    int res = 100000000;
    do{
        int tmp = 0;
        for(int i = 0; i < r - 1; i++){
            tmp += cost[town[i]][town[i+1]];
        }
        res = min(res, tmp);
    }while(next_permutation(town,town+r));
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
int main ()
{
	int a,b,c;
	while(scanf("%d %d %d", &a, &b, &c)!=EOF)
	{
		if(a == b)
		{
			printf("%d",c);
		}
		if(a == c)
		{
			printf("%d",b);
		}
		if(b == c)
		{
			printf("%d",a);
		}
	}
	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
#include <ctime>
#include <list>
using namespace std;
static const double EPS = 1e-6;
typedef long long ll;
typedef pair<int,int> PI;
#ifndef M_PI
const double M_PI=acos(-1);
#endif
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int((a).size()))
#define F first
#define S second
int dx[]={0,1,0,-1,0,0},dy[]={1,0,-1,0,0,0};
int dz[]={0,0,0,0,1,-1};

int n;
double sx[30],sy[30],sz[30];

double dist(double x,double y,double z,int id){
  double tx=x-sx[id];
  double ty=y-sy[id];
  double tz=z-sz[id];
  return sqrt(tx*tx+ty*ty+tz*tz);
}

double rad(double x,double y,double z){
  double ret=dist(x,y,z,n-1);
  rep(i,n-1)ret=max(ret,dist(x,y,z,i));
  return ret;
}

typedef struct _node{
  double x,y,z,r;
  int wh;
  _node(double x,double y,double z,int wh):
    x(x),y(y),z(z),wh(wh),r(rad(x,y,z)){};

  bool operator<(const _node& rn)const{
    if(rn.wh!=wh)return rn.wh<wh;
    return rn.r<r;
  }
}node;

int tx[]={1,1,1,1,-1,-1,-1,-1};
int ty[]={1,1,-1,-1,1,1,-1,-1};
int tz[]={1,-1,1,-1,1,-1,1,-1};
double len[1000];

void solve(){
  rep(i,n)scanf("%lf%lf%lf",sx+i,sy+i,sz+i);
  len[0]=100;
  for(int i=1;i<1000;++i)
    len[i]=len[i-1]/2;
  double ans=10000;
  rep(i,n)rep(j,i)
    ans=min(ans,rad((sx[i]+sx[j])/2,
                    (sy[i]+sy[j])/2,
                    (sz[i]+sz[j])/2));

  priority_queue<node> q;
  q.push(node(50,50,50,0));
  int cu=0;
  int bwh=-1;
  while(!q.empty()){
    node cur=q.top();
    q.pop();
    if(cu==100 && cur.wh==bwh)continue;
    if(cu==100)cu=0,bwh=cur.wh;
    ++cu;
    double rr=len[cur.wh];    
    if(ans<cur.r-rr*sqrt(3)*2+EPS)continue;
    ans=min(ans,cur.r);
    if(cur.wh>25)continue;
    //printf("%.5f %.5f %.5f %.5f %.7f %d\n",cur.x,cur.y,cur.z,cur.r,ans,cur.wh);

    rep(i,8)
      q.push(node(cur.x+rr*tx[i],cur.y+rr*ty[i],cur.z+rr*tz[i],cur.wh+1));
  }

  printf("%.5f\n",ans);
}

main(){
  while(cin>>n,n)
    solve();
}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
int main(){
  int h;
  while (cin>>h,h|h!=0){
    string temp;
    int board[h][6];
    for (int i=0;i<h;i++){
      cin>>board[i][0]>>board[i][1]>>board[i][2]>>board[i][3]>>board[i][4];
    }
    int num,count;
    int check=0;
    int score=0;
    while (1){
      check=score;
      for (int i=h-2;i>=0;i--){
	for (int j=0;j<5;j++){
	  for (int k=h-1;k>i;k--){
	    if (board[k][j]==0){
	      board[k][j]=board[i][j];
	      board[i][j]=0;
	      break;
	    }
	  }
	}
      }
      for (int i=0;i<h;i++){
	count=1;
	num=0;
	for (int j=0;j<5;j++){
	  if (board[i][j]==num){
	    count++;
	  }
	  else{
	    if (count>2)
	      break;
	    count=1;
	  }
	  num=board[i][j];
	}
	if (count<=2)
	  num=0;
	score=score+num*count;
	int ii=0;
	for (int j=0;j<5;j++){
	  if ((ii==count-1||j==4||board[i][j+1]==num)&&board[i][j]==num){
	    board[i][j]=0;
	    ii++;
	  }
	  if (ii==count)
	    break;
	}
      }
      if (check==score){
	break;
      }
    }

    cout<<score<<endl; 
  }
}

Measured memory_bytes: 1160
while True:
    a = input()
    b = a.split(' ')
    H = int(b[0])
    W = int(b[1])
    if H == 0 and W == 0:
        break
    elif H % 2 == 0:
        for i in range(H//2):
            if W % 2 == 0:
                print('#.'*int(W//2))
                print('.#'*int(W//2))
            elif W % 2 == 1:
                print('#.'*int((W-1)//2)+'#')
                print('.#'*int((W-1)//2)+'.')
    elif H % 2 == 1:
        for e in range((H-1)//2):
            if W % 2 == 0:
                print('#.'*int(W//2))
                print('.#'*int(W//2))
            elif W % 2 == 1:
                print('#.'*int((W-1)//2)+'#')
                print('.#'*int((W-1)//2)+'.')
        if W % 2 == 0:
            print('#.'*int(W//2))
        elif W % 2 == 1:
            print('#.'*int((W-1)//2)+'#')
    print()

Measured memory_bytes: 7664
#include <iostream>
#include <string>
#include <set>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 2;
int n;

void Read(){
	cin >> n;
}

void Solve(){
	cout << (ld)ceil((ld)n * 1.0 / 1000) * 1000 - n;
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Read();
	Solve();
}


Measured memory_bytes: 3800
/*
СТРОИМ СТЕНУ РАБОТЯГИ!
█▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define zhfs main
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define re return
#define forn(i, n) for (int i = 1; i <= n; i++)
const int INF = 1000 * 1000 * 1000 + 7;
int dp[47][107][107];
int a[47], b[47], c[47];
int zhfs()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	for (int i = 0; i < 47; i++)
	{
		for (int j = 0; j < 107; j++)
		{
			for (int k = 0; k < 107; k++)
			{
				dp[i][j][k] = INF;
			}
		}
	}
	dp[0][0][0] = 0;
	int n, ma, mb;
	scanf("%d %d %d", &n, &ma, &mb);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d %d", &a[i], &b[i], &c[i]);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 107; j++)
		{
			for (int k = 0; k < 107; k++)
			{
				if (dp[i][j][k] == INF) continue;
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
				dp[i + 1][j + a[i + 1]][k + b[i + 1]] = min(dp[i + 1][j + a[i + 1]][k + b[i + 1]], dp[i][j][k] + c[i + 1]);
			}
		}
	}
	int res = INF;
	for (int x = 0; x < 107; x++)
	{
		for (int y = 0; y < 107; y++)
		{
			if (x != 0 && y != 0 && ma * y == mb * x)
			{
				res = min(res, dp[n][x][y]);
			}
		}
	}
	if (res == INF) res = -1;
	printf("%d\n", res);
}



Measured memory_bytes: 2304
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    double a = sc.nextDouble();
    double b = sc.nextDouble();
    double h = sc.nextDouble();
    double m = sc.nextDouble();
    double time = h + m/60;
    double da = 30 * time;
    double db = 360 * time;
    double d = db- da;
    double c2 = Math.pow(a, 2) + Math.pow(b, 2) - 2 * a * b * Math.cos(Math.toRadians(d));
    double c = Math.sqrt(c2);
    System.out.println(c);
  }
}

Measured memory_bytes: 37536
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <valarray>
#include <vector>

#if __has_include(<string_view>)
#include <string_view>
#endif
#if __has_include(<optional>)
#include <optional>

template <class T>
constexpr const T &max(const T &a, const std::optional<T> &b)
{
    return b ? max(a, *b) : a;
}

template <class T>
constexpr const T &max(const std::optional<T> &a, const T &b)
{
    return a ? max(*a, b) : b;
}

template <class T>
constexpr const std::optional<T> &max(const std::optional<T> &a, const std::optional<T> &b)
{
    if (a && b)
        return *a > *b ? a : b;
    else if (a)
        return a;
    else
        return b;
}

template <class T>
constexpr const T &min(const T &a, const std::optional<T> &b)
{
    return b ? min(a, *b) : a;
}

template <class T>
constexpr const T &min(const std::optional<T> &a, const T &b)
{
    return a ? min(*a, b) : b;
}

template <class T>
constexpr const std::optional<T> &min(const std::optional<T> &a, const std::optional<T> &b)
{
    if (a && b)
        return *a < *b ? a : b;
    else if (a)
        return a;
    else
        return b;
}

#endif
#if __has_include(<any>)
#include <any>
#endif

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

using namespace std;

template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &pair)
{
    is >> pair.first >> pair.second;
    return is;
}

template <class T>
istream &operator>>(istream &is, vector<T> &collection)
{
    for (auto &item : collection)
        is >> item;
    return is;
}

template <class T>
istream &operator>>(istream &is, valarray<T> &collection)
{
    for (auto &item : collection)
        is >> item;
    return is;
}

template <class T>
T peak_and_pop(std::queue<T> &q)
{
    assert(!q.empty());
    T t = move(q.front());
    q.pop();
    return t;
}

template <class T>
T peak_and_pop(std::priority_queue<T> &q)
{
    assert(!q.empty());
    T t = move(q.top());
    q.pop();
    return t;
}

template <class T>
T peak_and_pop(std::stack<T> &q)
{
    assert(!q.empty());
    T t = move(q.top());
    q.pop();
    return t;
}

void solution()
{
    int64_t n;
    cin >> n;
    if (n % 2 == 1)
    {
        cout << 0 << '\n';
    }
    else
    {
        int64_t count = 0;
        int64_t x = 10;
        while (true)
        {
            count += n / x;
            x *= 5;
            if (n / x == 0)
            {
                break;
            }
        }
        cout << count << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    solution();
    return 0;
}


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

int main(){
    pair<pair<string, int>, int> p[100];
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        string name;
        int point;
        cin >> name >> point;
        p[i] = make_pair(make_pair(name, -point), i);
    }
    sort(p, p + N);
    for(int i = 0; i < N; i++){
        cout <<  p[i].second + 1 << endl;
    }
}

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

using namespace std;

int mcxi_to_int(string s);
string int_to_mcxi(int n);

int main()
{
	int n;

	scanf("%d", &n);

	while (n--){
		string a, b;
		cin >> a >> b;

		int result = mcxi_to_int(a) + mcxi_to_int(b);

		cout << int_to_mcxi(result) << endl;
	}
	
	return (0);
}

int mcxi_to_int(string s)
{
	int result = 0;
	int num = 1;

	for (int i = 0; i < s.length(); i++){
		switch (s[i]){
			case 'm':
				result += 1000 * num;
				num = 1;
				break;
			case 'c':
				result += 100 * num;
				num = 1;
				break;
			case 'x':
				result += 10 * num;
				num = 1;
				break;
			case 'i':
				result += num;
				num = 1;
				break;
			default:
				num = s[i] - '0';
		}
	}

	return (result);
}

string int_to_mcxi(int n)
{
	string result = "";
	int a[4] = {1000, 100, 10, 1};
	string mcxi("mcxi");
	stringstream ss;

	for (int i = 0; i < 4; i++){
		int v = n / a[i];

		if (v > 1){
			ss << v << mcxi[i];

			n %= a[i];
		}
		else if (v == 1){
			ss << mcxi[i];

			n %= a[i];
		}
	}

	result.append(ss.str());
	return (result);
}

Measured memory_bytes: 1256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#define FOR(i,a,n) for(i=(a);i<(n);i++)
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0)
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define LOCAL
#ifdef LOCAL
    #define DEBUG(...) printf(" "__VA_ARGS__)
#else
    #define DEBUG(...)
#endif /* LOCAL */
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
int isprime[SIZE];
int res[SIZE];
int main(void)
{
	int q,l,r,i,j;
	FOR(i,2,SIZE) isprime[i]=1;
	for(i=2;i*i<SIZE;i++){
		if(isprime[i]){
			for(j=i+i;j<SIZE;j+=i) isprime[j]=0;
		}
	}
	for(i=3;i<SIZE;i+=2) res[i]=(isprime[i]&&isprime[(i+1)/2]);
	FOR(i,1,SIZE) res[i]+=res[i-1];
	scanf("%d",&q);
	FOR(i,0,q){
		scanf("%d%d",&l,&r);
		printf("%d\n",res[r]-res[l-1]);
	}
	return 0;
}
    
    


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 100002;
ll a,b,c,d;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b>>c>>d;
	cout<<min(a,b)+min(c,d)<<endl;
	return 0;
}


Measured memory_bytes: 256
import collections
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
c = collections.Counter(prime_factorize(n))
v = list(c.values())
ans = 0
for i in v:
    j = 1
    p = 0
    count = 0
    while True:
        p += j
        j += 1
        if i<p:
            break
        count += 1
    ans += count
print(ans)


Measured memory_bytes: 65932
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    ans = 0
    used_s = {}
    for _ in range(n):
        s = "".join(sorted(input()))
        if not s in used_s.keys():
            used_s[s] = 0
        else:
            used_s[s] += 1
            ans += 1 * used_s[s]

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 17808
#include<stdio.h>

int A[500005];
int L[250002],R[250002];
int sum;

void merge(int A[], int left, int mid, int right)
{
	int n1, n2,i,j;
	n1 = mid - left;
	n2 = right - mid;
	for ( i = 0; i < n1; i++)
	{
		L[i] = A[i + left];
	}
	
	for ( i = 0; i < n2; i++)
	{
		R[i] = A[i + mid];
	}
	L[n1] = 2100000000;
	R[n2] = 2100000000;
	i = j = 0;
	for (int k = left; k < right; k++)
	{
		if (L[i] <= R[j])
			A[k] = L[i++];
		else
			A[k] = R[j++];
	}
	sum += right - left;
}

void mergeSort(int A[], int left, int right)
{
	int mid;
	if (left + 1 < right)
	{
		mid = (left + right) / 2;
		mergeSort(A,left,mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}

int main()
{
	int n,i;

	scanf("%d", &n);
	for ( i = 0; i < n; i++)
	{
		scanf("%d", &A[0] + i);
	}
	mergeSort(A, 0, n);

	printf("%d",A[0]);

	for (i = 1; i < n; i++)
	{
		printf(" %d", A[i]);
	}
	printf("\n");

	printf("%d\n",sum);

	return 0;
}


Measured memory_bytes: 6596
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
 
int main() {
  int n,a,b,c;
  cin >> n;
  a = (n/500)*1000;
  b = n - a/2;
  c = (b/5)*5;
  cout << a+c << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[]args){
      Scanner sc = new Scanner(System.in);

      int n = sc.nextInt();
      int sum = 0;

        for (int i = 1;i<=n ;i++ ) {
          sum = sum + i;
        }
        System.out.println(sum);

  }
}


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

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

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
// const int N = pow(10,9);

int main() {
  long long x;
  cin >> x;

  for (long long i = -1000; i <= 1000; i++) {
    for (long long j = -1000; j <= 1000; j++) {
      if (pow(i, 5) - pow(j, 5) == x) {
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 4012
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] d = new int[N];
		for (int i = 0; i < N; i++) {
			d[i] = sc.nextInt();
		}
		Arrays.sort(d);
		System.out.println(-d[N/2-1] + d[N/2]);
	}
}


Measured memory_bytes: 50912
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
 
  map<string, int> m;
  string s;
  int max = 0;
 
  for(int i = 0; i < N; i++){
    cin >> s;
    m[s]++;
    if (m[s] > max){
      max = m[s];
    }
  }

  for(auto x : m){
    if(x.second == max){
        cout << x.first << endl;
    }
  }
}

Measured memory_bytes: 25216
n=int(input())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
b=0
c=0
if n%2==0:
    for i in range(n//2):
        b+=a[2*i]
        c+=a[2*i+1]
else:
    for i in range(n//2):
        b+=a[2*i]
        c+=a[2*i+1]
    b+=a[n-1]
if b>c:
    print(b-c)
else:
    print(c-a)


Measured memory_bytes: 3060
use std::collections::BinaryHeap;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        aa: [u64; n],
        bb: [u64; n],
    }
    let mut heap = BinaryHeap::new();
    for (i, b) in bb.iter().enumerate() {
        heap.push((*b, i));
    }
    let mut bb = bb.clone();
    let mut count = 0;
    while let Some((mut b, i)) = heap.pop() {
        if b == aa[i] {
            continue;
        }
        let diff = bb[(i + n - 1) % n] + bb[(i + 1) % n];
        if b < aa[i] + diff {
            println!("-1");
            return;
        }
        let m = (b - aa[i]) / diff;
        count += m;
        b -= diff * m;
        bb[i] = b;
        if b > aa[i] {
            heap.push((b, i));
        }
    }
    for (a, b) in aa.iter().zip(bb) {
        assert_eq!(*a, b);
    }
    println!("{}", count);
}


Measured memory_bytes: 17524
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
char c[4]={'A','T','G','C'};
int main(){
  int N, Q;
  cin >> N >> Q;

  string S;
  cin >> S;

  int a[Q], b[Q];
  int AC[N]; //iばんめまでのAC列の数

  AC[0]=0;

  for(int i=1;i<N;i++){
    if(S[i-1]=='A' && S[i]=='C'){
      AC[i] = AC[i-1]+1;
    }else{
      AC[i] = AC[i-1];
    }
  }

  for(int i=0;i<Q;i++){
    cin >> a[i] >> b[i];
  }

  for(int i=0;i<Q;i++){
    cout << AC[b[i]-1] - AC[a[i]-1] << endl;
  }
  
  return 0;
}


Measured memory_bytes: 2176
#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>;

int main() {
  int N;
  cin >> N;
  ll ans = 0;
  for (int a = 1; a * a < N; a++)
    for (int b = a; a * b < N; b++) {
      if (a != b) ans++;
      ans++;
    }
  cout << ans << endl;
}


Measured memory_bytes: 3668
#include<stdio.h>
int main(){
int N,Z,W,a[2000],i,p,q;
scanf("%d%d%d",&N,&Z,&W);
for(i=0;i<N;i++){
scanf("%d",&a[i]);
}
if(N==1){if(W>=a[0]){printf("%d",W-a[0]);}
else{printf("%d",a[0]-W);}
return 0;}
if(W>=a[N-1]){p=W-a[N-1];}
else{p=a[N-1]-W;};
if(a[N-2]>=a[N-1]){q=a[N-2]-a[N-1];}
else{q=a[N-1]-a[N-2];};
if(p>=q){printf("%d",p);}
else{printf("%d",q);}
return 0;
}




Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll N, M; cin >> N >> M;
  ll res = 1;
  for (ll i = 1; i*i <= M; i++) {
    if (M%i == 0 && M >= i*N) {res = max(res, i);}
    if (M%i == 0 && i >= N) {res = max(res, M/i);}
  }
  cout << res << endl;
}

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

int pos[50];
int main() {
	int n, k; scanf("%d%d", &n, &k);
	rep(i, k) {
		int m; scanf("%d", &m);
		rep(j, m) {
			int u; scanf("%d", &u); u--;
			pos[u] = i;
		}
	}
	int r; scanf("%d", &r);
	set<int>se;
	rep(i, r) {
		int p, q; scanf("%d%d", &p, &q); p--; q--;
		if (pos[p] == pos[q]) {
			se.insert(p);
			se.insert(q);
		}
	}
	printf("%d\n", se.size());
}

Measured memory_bytes: 3224
def bb
    n = gets.chomp.to_i
    t,a = gets.chomp.split(/\s/).map{|x| x.to_i}
    h = gets.chomp.split(/\s/).map{|x| x.to_i}

    o = []
    for i in 0..(n-1)
        o.push((a - (t-h[i]*0.006)).abs)
    end

    puts o.index(o.min)+1
end

bb

Measured memory_bytes: 1788
import Control.Applicative
import Control.Monad
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Text.Printf
import Debug.Trace

getInts :: IO [Int]
getInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

main = do
  [sx,sy,tx,ty] <- getInts
  replicateM_ (abs $ sx-tx) (putChar $ if sx < tx then 'R' else 'L')
  replicateM_ (abs $ sy-ty) (putChar $ if sy < ty then 'U' else 'D')
  replicateM_ (abs $ sx-tx) (putChar $ if sx < tx then 'L' else 'R')
  replicateM_ (abs $ sy-ty) (putChar $ if sy < ty then 'D' else 'U')
  putChar 'D'
  replicateM_ ((+1) $ abs $ sx-tx) (putChar $ if sx < tx then 'R' else 'L')
  replicateM_ ((+1) $ abs $ sy-ty) (putChar $ if sy < ty then 'U' else 'D')
  putChar 'L'
  putChar 'U'
  replicateM_ ((+1) $ abs $ sx-tx) (putChar $ if sx < tx then 'L' else 'R')
  replicateM_ ((+1) $ abs $ sy-ty) (putChar $ if sy < ty then 'D' else 'U')
  putChar 'R'
  putStrLn ""


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

#define range 100005
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define _ <<" "<<

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair <int, int> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<ii> vii;
typedef vector<iii> viii;

int dp[4000][4000];

char papu[4000][4000];

ii ind[4000][4000];

string s,t;

int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("test.txt","r",stdin);
	cin>>s>>t;
	for(int i=0;i<=s.length();i++)
		for(int j=0;j<=t.length();j++)
			ind[i][j] = {-1,-1};
	for(int i=1;i<=s.length();i++)
	{
		for(int j=1;j<=t.length();j++)
		{
			if(dp[i-1][j]>dp[i][j])
			{
				dp[i][j] = dp[i-1][j];
				papu[i][j] = '#';
				ind[i][j] = {i-1,j};
			}
			if(dp[i][j-1]>dp[i][j])
			{
				dp[i][j] = dp[i][j-1];
				papu[i][j] = '#';
				ind[i][j] = {i,j-1};
			}
			if(s[i-1]==t[j-1])
			{
				if(dp[i-1][j-1]+1>dp[i][j])
				{
					dp[i][j] = dp[i-1][j-1] + 1;
					papu[i][j] = s[i-1];
					ind[i][j] = {i-1,j-1};
				}
			}
		}
	}
	/*for(int i=0;i<=s.length();i++)
	{
		for(int j=0;j<=t.length();j++)
		{
			cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	string ans;
	ans.clear();
	//cout<<dp[s.length()][t.length()];
	ii temp = {s.length(),t.length()};
	while(!(temp.fi==-1&&temp.se==-1))
	{
		if(papu[temp.fi][temp.se]!='#')
			ans.pb(papu[temp.fi][temp.se]);
		ii popa = temp;
		temp = ind[popa.fi][popa.se];
	}
	reverse(ans.begin(),ans.end());
	for(int i=1;i<ans.length();i++)
		cout<<ans[i];
	return 0;
}

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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second　//pairの二つ目の要素

int n, k;
vector<int> a;
//vector<bool> dp(100005);
bool dp[100005]={};


int main(){
    cin>>n>>k;
    a.resize(n);
    rep(i,n){
        cin>>a[i];
    }
    for(int i=1;i<=k;i++){
        for(int j=0;j<n;j++){
             if (i-a[j]>=0) dp[i] |= !dp[i-a[j]];
        }
    }
    cout<<(dp[k]? "First" : "Second")<<endl;
    return 0;
}

Measured memory_bytes: 384
MOD = 10**9 + 7
N = int(input())
C = [int(input()) for _ in range(N)]
dp = [0]*(N+1)
lis = [-1] * (2 * 10**5 + 1)
dp[0] = 1
lis[C[0]] = 0
for i,c in enumerate(C[1:],1):
    prev_i = lis[c]
    dp[i] = dp[i-1]
    if prev_i != i-1:
        dp[i] += dp[prev_i]
        dp[i] %= MOD
    lis[c] = i
answer = dp[N-1]
print(answer)

Measured memory_bytes: 25992
N = int(input())
INF = float('inf')
dp = [INF]* 100001
dp[0] = 0
cost = list()
cost.append(1)
i6 = 6
while(i6 <= 100000):
  cost.append(i6)
  i6 *= 6
i9 = 9
while(i9 <= 100000):
  cost.append(i9)
  i9 *= 9
cost.sort()
for i in range(1, 100001):
  for c in cost:
    if(i-c>=0):
      dp[i] = min(dp[i], dp[i-c]+1)
print(dp[N])

Measured memory_bytes: 44588
n=int(input())
A=[0]
A.extend([int(i) for i in input().split()])
A.append(0)
Sb=[0 for i in range(n+2)]
t=0

for i in range(0,n+2):
  t+=abs(A[i-1]-A[i])

for i in range(1,n+1):
  if max(abs(A[i]),abs(A[i-1]),abs(A[i+1])):
    cb=abs(A[i]-A[i-1])+abs(A[i]-A[i+1])
    ca=abs(A[i+1]-A[i-1])
    print(t-cb+ca)
  else:
    print(t)

Measured memory_bytes: 14172
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))

typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

const int large = 1e9;

struct segTree{
    bool ex = 0;
    int l = 1, r = large;
    int mid = (l+r)/2;
    ll val = 2*large+5;
    segTree *lptr = nullptr, *rptr = nullptr;
    segTree(int rl = 1, int rr = large){
        l = rl; r = rr;
        mid = (l+r)/2;
    }
    void extend(){
        if(ex) return;
        ex = 1;
        lptr = new segTree(l, mid);
        rptr = new segTree(mid+1, r);
    }
    int getMax(int rl, int rr){
        if(rl == l && rr == r) return val;
        extend();
        if(rr <= mid) return lptr->getMax(rl,rr);
        else if(rl > mid) return rptr->getMax(rl, rr);
        else{
            return min(lptr->getMax(rl, mid), rptr->getMax(mid+1, rr));
        }
    }
    void place(ll v, int pos){
        if(r == l){
            val = min(v,val);
            return;
        }
        extend();
        if(pos <= mid) lptr->place(v,pos);
        else rptr->place(v, pos);
        val = min(lptr->val, rptr->val);
    }
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    segTree Higher, Lower;
    int n; cin >> n;
    vpi pairs(n); FOR(i,n) cin >> pairs[i].f >> pairs[i].s;
    sort(pairs.begin(), pairs.end());
    Higher.place(pairs[0].f-pairs[0].s, pairs[0].s);
    Lower.place(pairs[0].f+pairs[0].s, pairs[0].s);
    ll ans = 0;
    F0R(i,1,n-1){
        pi cur = pairs[i];
        ll curans = (ll)cur.f-(ll)cur.s-(ll)Higher.getMax(cur.s, large);
        ans = max(ans, curans);
        curans = (ll)cur.f+(ll)cur.s-(ll)Lower.getMax(1, cur.s);
        ans = max(ans, curans);
        Higher.place(cur.f-cur.s, cur.s);
        Lower.place(cur.f+cur.s, cur.s);
    }
    cout << ans << "\n";
    return 0;
}


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

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int W, H;
  cin >> W >> H;
  if (W == 1&& H == 1){
    cout << 1 << "\n";
  }
  else if (W == 1) {
    cout << H-2 << "\n";
  }
  else if (H == 1) {
    cout << W-2 << "\n";
  }
  else {
    cout << 1LL*W*H-(4+2LL*((W-2)+(H-2))) << "\n";
  }
  return 0;
}


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

int main(){
  
  int n;
  cin >> n;
  
  int a;
  int res = 1000000000;
  int cnt;
  
  for(int i = 0; i < n; ++i){
    cin >> a;
    cnt = 0;
    while(!(a % 2)){
      ++cnt;
      a /= 2;
    }
    res = min(cnt, res);
  }
  
  cout << res;
  
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD1 1000000007

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  bool f = false;
  rep(i, B) {
    if ((A * i) % B == C) {
      f = true;
      break;
    }
  }
  cout << (f ? "YES" : "NO") << endl;

}


Measured memory_bytes: 256
n,m=map(int,input().split())
if n%2==1:
    x=["{} {}".format(i+1,n-i) for i in range(m)]
    #x=[f"{i+1} {n-i}" for i in range(m)]
    print(" ".join(x))
else:
    x=["{} {}".format(i+1,n-i) if i<m/2 else "{} {}".format(i+1,n-i-1) for i in range(m)]
    #x=[f"{i+1} {n-i}" if i<m/2 else f"{i+1} {n-i-1}" for i in range(m)]
    print(" ".join(x))

Measured memory_bytes: 17444
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int x,y,z,n,m,t,M,flag[2][N],fa[N],u[N],v[N],w[N];
int get(int x,int y,int z){
	return (x-1)*6+y*3+z+1;
}
int find(int x){
	if (fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&t,&M);
	int g=0;
	for (int i=1;i<=m;i++)scanf("%d%d%d",&u[i],&v[i],&w[i]);
	for (int i=2;i<=m;i++)g=__gcd(g,abs(w[i]-w[1]));
	if (!g)g=M;
	M=__gcd(M,g*3);
	for (int i=1;i<=6*n;i++)fa[i]=i;
	for (int i=1;i<=m;i++){
		int l=(w[i]-w[1]%g)/g;
		for (int p=0;p<=1;p++)
			for (int q=0;q<=2;q++){
				int nq=(2*q+l)%3;
				x=get(u[i],p,q);
				y=get(v[i],1-p,nq);
				fa[find(x)]=find(y);
				x=get(v[i],p,q);
				y=get(u[i],1-p,nq);
				fa[find(x)]=find(y);
			}
	}
	for (int i=0,j=w[1]%g;i<M*2;i++,j=j*2%M)flag[i&1][j]=1;
	while (t--){
		scanf("%d%d%d",&x,&y,&z);
		int ans=0;
		for (int p=0;p<=1;p++)
			for (int q=0;q<=2;q++)
				if (find(get(x,p,q))==find(get(y,0,0)))ans|=flag[p][(z+w[1]%g+(3-q)*g)%M];
		if (ans)puts("YES");
		else puts("NO");
	}
	return 0;
}


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

int main(){
    int n, m;
    int i, j;
    cin >> n >> m;
    long long c[n];   
    int a[n][m], b[m];
    
    for(i=0; i<n; i++){
        for(j=0; j<m; j++){
            cin >> a[i][j];
        }
    }
    for(int i=0; i<m; i++){
        cin >> b[i];
    }
    for(int i=0; i<n; ++i){
        c[i] = 0;
        for(int j=0; j<m; ++j){
            c[i] += a[i][j] * b[j];
        }
        cout << c[i] <<endl;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000;
const int MOD = (int)1e9 + 7;

signed main()
{
    int n, m;
    cin >> n >> m;
    int cl = 0;
    int cr = n + 1;
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        cl = max(cl, l);
        cr = min(cr, r);
    }
    int r = cr - cl + 1;
    cout << (r > 0 ? r : 0) << "\n";
}

Measured memory_bytes: 256
n, m = map(int, input().split())
l_list, r_list = [], []

for i in range(m):
	l, r = map(int, input().split())
	l_list.append(l)
	r_list.append(r)

limit_min = max(l_list)
limit_max = min(r_list)
cnt = 0

for i in range(1, n + 1):
	if limit_min <= i <= limit_max:
		cnt += 1

print(cnt)


Measured memory_bytes: 16880
def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i = i+1
            (A[i],A[j]) = (A[j],A[i])
    (A[i+1],A[r]) = (A[r],A[i+1])
    return i+1



if __name__ == '__main__':
    n = (int)(input())
    A = list(map(int,input().split()))

    i = partition(A,0,n-1)
    A[i] = "["+str(A[i])+"]"
    print(*A)

Measured memory_bytes: 18392